バイバイマンを数えてみた

バイバイマンを数えよう に挑戦してみました。コードゴルフは初めてでしたが Python で 51B (eijit) と一位までもう少しのところまで行きました。試行錯誤しながら迷走して面白かったので記録を残しておこうと思います。

素朴なアルゴリズム

問題を解析する 1

バイバイマンの増え方が想像しにくい場合は バイバイマンの増え方 もあわせてご覧ください。

各サイズのバイバイマンの個体数と総数を世代ごとに追うと以下の表のようになります。

世代	c(1, n)	c(2, n)	c(4, n)	c(8, n)	c(6, n)	s(n)
0	1	0	0	0	0	1
1	0	1	0	0	0	1
2	0	0	1	0	0	1
3	0	0	0	1	0	1
4	1	0	0	0	1	2
5	1	2	0	0	0	3
6	0	1	2	0	0	3
7	0	0	1	2	0	3
8	2	0	0	1	2	5
9	3	4	0	0	1	8

ここで

• c(s, n) はサイズが s で第 n 世代のバイバイマンの個体数
• s(n) は第 n 世代のバイバイマンの総数

を表します。するとすぐ解るように

• c(1, n) = c(6, n-1) + c(8, n-1)
• c(2, n) = c(1, n-1) + c(6, n-1)
• c(4, n) = c(2, n-1)
• c(8, n) = c(4, n-1)
• c(6, n) = c(8, n-1)

と前の世代の一つ小さいサイズの個体数からの移動 (s = 6 は s = 1 に移動したとみなす) と、前の世代のサイズ 8, 6 の分裂からの "繰り上がり" の合計という関係が見えます。

[85B] 最初のコード

最初はコードゴルフだと気が付かずに 400B 弱のコードを書いて提出してしまったのですがあとから気が付いて短縮してみました。

c=[1]+[0]*4
for i in range(100):
 print sum(c)
 c=c[4:]+c[:4]
 c[1]+=c[0]
 c[0]+=c[4]

これで 85B でした。要素の格納に配列を使いました。工夫したのは

• [1,0,0,0,0] より [1]+[0]*4 のほうが 2B 少ない
• インデントは空白一つ
• 合計を sum で計算する
• 配列を rotate shift した

でした。結果を見てまるで歯が立たないことに愕然としてコードゴルフの勉強を始めました。

[71B] 初めてのワンライナー

ウェブの記事をあちこち見て回って以下のようなことを学びました。

• ループカウンタを使わないなら exec"コード"*ループ回数 でコードを指定回数繰り返せる
• if などが入れ子にならないなら改行とインデントを省いてセミコロン ';' で代替できる

c=[1]+[0]*4;exec"print sum(c);c=c[4:]+c[:4];c[1]+=c[0];c[0]+=c[4];"*100

これで 14B 縮みました。ですがまだ足りません。

[67B] 配列をやめる

配列の要素にアクセスするコストが高いと気が付いたので a, b, c, d, e といった五つの変数で置き換えてみました。

a=1;b=c=d=e=0;exec"print a+b+c+d+e;f=a+d;a=d+e;c=b;d=c;e=d;b=f"*100

これで更に 4B 縮みました。しかし一時変数 f を使っていて無駄です。

[64B] 一時変数を使わずにスワップする

コードゴルフの勉強をしたときに一時変数を使わずにスワップする話題があったのを思い出しました。

a=1
b=2
a,b=b,a

のような構文です。これを適用して

a=1;b=c=d=e=0;exec"print a+b+c+d+e;a,b,c,d,e=d+e,a+e,b,c,d;"*100

更に 3B 縮みました。これで何とかバッヂ獲得圏内に入ったのですがトップは 50B とまだ絶望的な差があります。

[62B] 共通する計算をまとめる

ここでコードを眺めていて

print a+b+c+d+e
a=d+e
b=a+e

と計算が重複していることに気が付きました。これを利用できないかと考えて

a=1;b=c=d=e=0;exec"a,b,c,d,e=d+e,a+e,b,c,d;print b+c+d+e;"*100

と更に 2B 縮みました。ここで

• print と個体数更新の計算の順序を入れ替える
• b=a+e を利用して (現世代の) a+b -> (次世代の) b と置き換えても結果は変わらない

ということをしています。

最適 (ではなかった) アルゴリズム

ここまでで、この方針でこれ以上はコードを削れないと思い、基本に立ち返って具体例を眺めて別の規則がないか考えました。

問題を解析する 2

すると

s(n) = s(n-1) + c(1, n)

という規則があるようでした。理由を考えてみれば当たり前の話でした。バイバイマンの個体数が増えるのは、サイズ 8 と 6 が次の世代になってサイズ 16 と 12 になりサイズ 1, 6 とサイズ 1, 2 に分裂した場合です。その際に増えた個体をサイズ 1 のものとみなせばよいわけです。

[63B] 戦略的後退

早速この解析結果に基づいて実装したところ、残念ながら総和を保持するための変数のために却って 1B 増えてしまいました。

a=1;b=c=d=e=s=0;exec"s+=a;print s;a,b,c,d,e=d+e,a+e,b,c,d;"*100

結果が正しいことは確認したのでこの方針をもう少し突き詰めて考えます。

隣接六項間漸化式

利用する変数の削減が必要であると痛感したのでサイズ 1 の個体数だけ都合よく計算できないかと考えました。

(ここまで使っていた記号 c(1, n) などを $c_{1, n}$ に読み替えてください)

1. $c_{1, n} = c_{6, n-1} + c_{8, n-1}$
2. $c_{2, n} = c_{1, n-1} + c_{6, n-1}$
3. $c_{4, n} = c_{2, n-1}$
4. $c_{8, n} = c_{4, n-1}$
5. $c_{6, n} = c_{8, n-1}$

を思い出して 1. の $c_{1, n} = c_{6, n-1} + c_{8, n-1}$ をサイズ 1 の項だけで表すことを考えます。

\begin{eqnarray*}
c_{1, n} &= c_{6, n-1} + c_{8, n-1}\\
&=c_{8, n-2} + c_{4, n-2}\\
&=c_{4, n-3} + c_{2, n-3}\\
&=c_{2, n-4} + c_{1, n-4} + c_{6, n-4}\\
&=c_{1, n-5} + c_{6, n-5} + c_{1, n-4} + c_{8, n-5}\\
&=c_{1, n-5} + c_{1, n-4} + c_{6, n-5} + c_{8, n-5}\\
&=c_{1, n-5} + c_{1, n-4} + c_{1, n-4}\\
&=c_{1, n-5} + 2c_{1, n-4}\\
\end{eqnarray*}

と

c_{1, n} = c_{1, n-5} + 2c_{1, n-4}

で表せることが解りました。

さてこれは隣接六項間の漸化式なので解いてみましょう。特性方程式は

x^5 - 2x - 1 = 0

ですが、残念なことに五次方程式には解の公式がありません。しかしすぐわかるように $x = -1$ がこの方程式の解の一つであることが解ります。従って因数分解すれば

x^5 - 2x - 1 = (x + 1)(x^4 - x^3 + x^2 - x -1)

と一次と四次の多項式に分解できました。後者の四次の多項式 = 0 の解は残念ながら複素数を含み、単純な有理数や整数ではないようです。おそらくこの漸化式を解いてもコードの短縮に寄与しそうにありません。今回は面倒くささに負けて計算を諦めましたが漸化式を解いて一般項を求めるのも面白いかもしれません。

[63B] 停滞

脱線しましたので閑話休題して、サイズ 1 の要素数の漸化式は

c_{1, n} = c_{1, n-5} + 2c_{1, n-4}

であったので素直にこれを実装して

a=e=1;b=c=d=s=0;exec"s+=a;print s;a,b,c,d,e=b,c,d,e,a+2*b;"*100

残念ながら 63B と変わりありません。

[56B] やっと前進

漸化式の計算を行っているときに気が付いたのですが、他のサイズの要素数も同じ漸化式で表せて

c_{s, n} = c_{s, n-5} + 2c_{s, n-4}

が全ての $s=1, 2, 4, 8, 6$ に対して成り立ちます。これらの総和を取り

\sum_{s} c_{s, n} = \sum_{s} c_{s, n-5} + \sum_{s} 2c_{s, n-4}

総和はバイバイマンの総数であることを思い出すと

s_{n} = s_{n-5} + 2s_{n-4}

とバイバイマンの総和をじかに計算できました。バイバイマンの総数の漸化式に関する初項が 1, 1, 1, 1, 2 であることを合わせて実装すると

a=b=c=d=1;e=2;exec"print a;a,b,c,d,e=b,c,d,e,a+2*b;"*100

ようやく 56B まで縮みました。

[53B] 配列再び

もうひとひねりが必要なので再び配列を利用します。更に計算するのが高々 100 世代なので rotate shift などもやめました。なりふりを構っている場合ではありません。

a=[1]*4+[2];exec"print a[-5];a+=[a[-5]+2*a[-4]];"*100

これで 53B まできました。これは

1, 1, 1, 1, 2, 3, 3, 3, 5, 8, ...

と漸化式に従って次の世代の総数を追加して無制限に成長していく配列で、末尾から -5 の位置を現在の世代の総数として出力しています。

[51B] 最後の一工夫

53B のコードは配列のインデックスに負の値を使っており '-' だけ損をしています。この配列の順序を逆にして '-' を三つ削り、代わりに += を = と +a に置き換えても差し引きして 2B の短縮になります。

a=[2]+[1]*4;exec"print a[4];a=[a[4]+2*a[3]]+a;"*100

これが今回の私の回答でした。

最後に

あともう一バイトを削れないかと

• 標準入力で与えられる 100 を 2B で取り込めないか
• 100 を 2B で表せないか

といったことを考えたのですが、いずれもうまくいきませんでした。公開される python の回答やそのほかの言語の回答が楽しみです。

最後に、このような面白い問題を提供してくださった Ozy さまと、場を提供してくださった CodeIQ さまに感謝します。