「レッド・アンド・ホワイト」問題解答 ( CodeIQ )
はじめに
CodeIQというところでプログラミング問題「レッド・アンド・ホワイト」に解答しましたので、ネタバレです。
問題
入力 n に対して、以下で定義される関数$F(n)=$「n秒後の赤色のマスの数の個数」の値を出力する、という問題です。マスは両方向に無限に延びており、1秒毎に、
- 隣接するマスが赤・白異なる色ならば赤になる
- 隣接するマスが赤・白同じ色ならば白になる
という変化をします。初期状態は赤1マスのみです。詳しくは、問題にあった次の図をご覧ください。
解説
先に実装
一言で、答えは「2の『nを2進表記した時の1の数』乗」です。
なので、Perl(31)で素直に実装したのが次です。
print 2**map/1/g,sprintf"%b",<>
(2016/5/19 更新)
tailsさんのPerl(30)とは、次のようなコードでした。
@angel_p_57 Perl (30) はこんなです。
— 齊藤 (tails) (@saito_ta) May 19, 2016
print 1<<unpack"%B*",pack N,<>
文字数のカウントなしでpopcountができてしまうという…。なんと。
(更新終わり)
Rubyだと32文字かと思っていたのですが、ciaranaさんに教えて頂いて、26文字行けることが分かりました。
@angel_p_57 @codeiq Ruby(26)も行けそうですね（と言ってしまうとRuby(32)からRuby(26)への縮め方がバレそうですが・・・）
— CIARANA (@cia_rana) May 10, 2016
まあ、色々な方が既に公開されていますが、次のような感じです。
p 2**("%b"%gets).count(?1)
一応考察
私は良く知らなかったのですが、CodeIQ 挑戦の記録 :「レッド・アンド・ホワイト」問題 - ibeckuuの日記 によると、「シェルピンスキーのギャスケット」と同じものになるようですね。
問題を解いた時は次のように考えました。
- マスの位置 x ( 最初の赤の位置を 0 ) および、時刻 t におけるマスに対して、$f(x,t)=0 or 1$ ( 赤の場合に 1、白の場合に 0 )とする
- そうした場合、$f(x,t+1)=f(x-1,t)+f(x+1,t)$ ( ただし、通常の足し算ではなく、GF(2) というか mod 2 の世界における足し算 )
- ここで、$g(n,m)=f(m-n,n)$ と置くと、fの漸化式よりgの漸化式 $g(n+1,m)=g(n,m-2)+g(n,m)$ が導かれる ( なお、初期状態として $g(0,0)=1, g(0,m)=0 ( m\neq 0 )$
こうやって作った g に対して、m が奇数であれば ( 初期状態で全て値が 0 のため、帰納的に ) trivial に $g(n,m)=0$ です。
問題は m が偶数の時ですが、$m=2k$ として漸化式を見直すと $g(n+1,2k)=g(n,2(k -1))+g(n,2k)$ これはパスカルの三角形における漸化式に他なりません。( 足し算が、通常のものか GF(2) に対するものか、という違いはありますが )
というわけで、$g(n,2k)\equiv {}_n C_{k}\,\,( mod\,2 )$となります。ここから先は端折りますが、$F(n)$とは、${}_n C_{k}$の中で奇数となるものの個数にほかならず、それが冒頭で述べた「2の『nを2進表記した時の1の数』乗」ということになります。
Brainf**kもお忘れなく
というか、提出時にすっかり失念していたのですが ( どうかしている )、そういう計算ならBrainf**kで実装できますね。メモリと実行時間が許す限り、nativeで桁数無制限のBCDが使えますから、何の問題もありません。
ということで、ざっくりと実装したものが次のものになります。
終わりに
整理していくと凄く単純な式に落とし込めるというのは、やはり爽快ですね。
