1. eijit

    Posted

    eijit
Changes in title
+バイバイマンを数えてみた
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,270 @@
+[バイバイマンを数えよう](https://codeiq.jp/q/2593) に挑戦してみました。コードゴルフは初めてでしたが Python で 51B ([eijit](http://d.hatena.ne.jp/keyword/Python)) と一位までもう少しのところまで行きました。試行錯誤しながら迷走して面白かったので記録を残しておこうと思います。
+
+# 素朴なアルゴリズム
+
+## 問題を解析する 1
+
+バイバイマンの増え方が想像しにくい場合は [バイバイマンの増え方](http://d.hatena.ne.jp/Ozy/20160131) もあわせてご覧ください。
+
+各サイズのバイバイマンの個体数と総数を世代ごとに追うと以下の表のようになります。
+
+|世代|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| 4|
+| 7| 0| 0| 1| 2| 0| 4|
+| 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 弱のコードを書いて提出してしまったのですがあとから気が付いて短縮してみました。
+
+```python
+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 などが入れ子にならないなら改行とインデントを省いてセミコロン ';' で代替できる
+
+```python
+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 といった五つの変数で置き換えてみました。
+
+```python
+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] 一時変数を使わずにスワップする
+
+コードゴルフの勉強をしたときに一時変数を使わずにスワップする話題があったのを思い出しました。
+
+```python
+a=1
+b=2
+a,b=b,a
+```
+
+のような構文です。これを適用して
+
+```python
+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] 共通する計算をまとめる
+
+ここでコードを眺めていて
+
+```py
+print a+b+c+d+e
+a=d+e
+b=a+e
+```
+
+と計算が重複していることに気が付きました。これを利用できないかと考えて
+
+```python
+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 増えてしまいました。
+
+```py
+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}$
+1. $c_{2, n} = c_{1, n-1} + c_{6, n-1}$
+1. $c_{4, n} = c_{2, n-1}$
+1. $c_{8, n} = c_{4, n-1}$
+1. $c_{6, n} = c_{8, n-1}$
+
+を思い出して 1. の $c_{1, n} = c_{6, n-1} + c_{8, n-1}$ をサイズ 1 の項だけで表すことを考えます。
+
+```math
+\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*}
+```
+
+
+
+```math
+c_{1, n} = c_{1, n-5} + 2c_{1, n-4}
+```
+
+で表せることが解りました。
+
+さてこれは隣接六項間の漸化式なので解いてみましょう。特性方程式は
+
+```math
+x^5 - 2x - 1 = 0
+```
+
+ですが、残念なことに五次方程式には解の公式がありません。しかしすぐわかるように $x = -1$ がこの方程式の解の一つであることが解ります。従って因数分解すれば
+
+```math
+x^5 - 2x - 1 = (x + 1)(x^4 - x^3 + x^2 - x -1)
+```
+
+と一次と四次の多項式に分解できました。後者の四次の多項式 = 0 の解は残念ながら複素数を含み、単純な有理数や整数ではないようです。おそらくこの漸化式を解いてもコードの短縮に寄与しそうにありません。今回は面倒くささに負けて計算を諦めましたが漸化式を解いて一般項を求めるのも面白いかもしれません。
+
+## [63B] 停滞
+
+脱線しましたので閑話休題して、サイズ 1 の要素数の漸化式は
+
+```math
+c_{1, n} = c_{1, n-5} + 2c_{1, n-4}
+```
+
+であったので素直にこれを実装して
+
+```py
+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] やっと前進
+
+漸化式の計算を行っているときに気が付いたのですが、他のサイズの要素数も同じ漸化式で表せて
+
+```math
+c_{s, n} = c_{s, n-5} + 2c_{s, n-4}
+```
+
+が全ての $s=1, 2, 4, 8, 6$ に対して成り立ちます。これらの総和を取り
+
+
+```math
+\sum_{s} c_{s, n} = \sum_{s} c_{s, n-5} + \sum_{s} 2c_{s, n-4}
+```
+
+総和はバイバイマンの総数であることを思い出すと
+
+```math
+s_{n} = s_{n-5} + 2s_{n-4}
+```
+
+とバイバイマンの総和をじかに計算できました。総和の漸化式に関する初項が 1, 1, 1, 1, 2 であることを合わせて実装すると
+
+```py
+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 などもやめました。なりふりを構っている場合ではありません。
+
+```py
+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 の短縮になります。
+
+```py
+a=[2]+[1]*4;exec"print a[4];a=[a[4]+2*a[3]]+a;"*100
+```
+
+これが今回の私の回答でした。
+
+# 最後に
+
+あともう一バイトを削れないかと
+
+* 標準入力で与えられる 100 を 2B で取り込めないか
+* 100 を 2B で表せないか
+
+といったことを考えたのですが、いずれもうまくいきませんでした。公開される python の回答やそのほかの言語の回答が楽しみです。
+
+最後に、このような面白い問題を提供してくださった Ozy さんと、場を提供してくださった CodeIQ に感謝します。