CodeIQ：バイバイマンを数えよう

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「バイバイマンを数えよう」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

【バイバイマン】
バイバイマンは1日毎に体の大きさが倍増します。
また、一定の大きさをこえると分裂します。

【問題】
バイバイマンのサイズを整数値で表します。
一番最初の大きさを「1」とし、1日経つと2倍の「2」、さらに1日後は「4」というように、1日毎に2倍になります。
また、バイバイマンは「1」→「2」→「4」→「8」→「16」と、大きさが10を超えたところで分裂します。
分裂後のサイズは、「16」なら「1」と「6」のように10の位の数と1の位の数になります。
分裂したバイバイマンは、再び大きくなります。
このようなルールで増えるバイバイマンの数を、1日ごとに調べて、100日目までを出力してください。

私のプログラム

Pythonで解答しています。

b=[0,1]+[0]*7
for i in[0]*100:
	print(sum(b[1:]));n=[0]*9;j=8
	while j:n[j*2%10]+=b[j];n[j*2//10]+=b[j];j-=1
	b=n

解説

この問題はショートコーディングの問題だったので少し努力して短くしています。とはいえこの程度の長さでは勝負にならないのですが。

分かりやすく書き直す

さすがに見にくいので同じコードを見やすくします。

b=[0,1,0,0,0,0,0,0,0]

for i in range(100):
	print(sum(b[1:]))

	n=[0,0,0,0,0,0,0,0,0]
	for j in range(8):
		n[j*2%10]+=b[j]
		n[j*2//10]+=b[j]
	b=n

元のコードはこれと同義です。

バイバイマンの増え方

バイバイマンは次のように増えます。

経過日数		0	1	2	3	4	5	6	7	8
数	1	1	0	0	0	1	1	0	0	2
	2	0	1	0	0	0	2	1	0	0
	4	0	0	1	0	0	0	2	1	0
	6	0	0	0	0	1	0	0	0	2
	8	0	0	0	1	0	0	0	2	1

つまり、バイバイマンは1、2、4、6、8のどれかの値しかとりません。
そして10未満の大きさの時は2倍いたサイズに数がシフトし、10以上になったら1と2か6のサイズに分裂して値がシフトします。これは現在のサイズを10で割った余りと商に等しいのでそれを利用します。サイズが1〜4の間は商が0になってサイズ0の数が増えますが、結果に利用しなければ問題ないので加算してしまいます。

あとは毎回数を出力すればOKです。

雑感

問題は簡単でしたがコードを短くするのは難しいです。最も短いコードを書いた人はPython3で50バイト前半だったと思います。
私のコードでは一時領域(n)などを使っているのでこれをなくせれば短くなるとは思うのですがこれ以上短くする方法は思いつけませんでした。私はショートコーディングには余り興味がないのですが、やってみてわかったのはコードを短くするためには言語仕様とアルゴリズムの両方に精通している必要があるということで、ショートコーディングも勉強になるものだと思いました。