読者です 読者をやめる 読者になる 読者になる

「レッド・アンド・ホワイト」問題解答 ( CodeIQ )

CodeIQ 数学 Brainf**k

はじめに

CodeIQというところでプログラミング問題「レッド・アンド・ホワイト」に解答しましたので、ネタバレです。

codeiq.jp

問題

入力 n に対して、以下で定義される関数$F(n)=$「n秒後の赤色のマスの数の個数」の値を出力する、という問題です。マスは両方向に無限に延びており、1秒毎に、

  • 隣接するマスが赤・白異なる色ならば赤になる
  • 隣接するマスが赤・白同じ色ならば白になる

という変化をします。初期状態は赤1マスのみです。詳しくは、問題にあった次の図をご覧ください。

https://codeiq.jp/sites/default/files/answer_ready/2812/1.png

解説

先に実装

一言で、答えは「2の『nを2進表記した時の1の数』乗」です。

なので、Perl(31)で素直に実装したのが次です。

print 2**map/1/g,sprintf"%b",<>

(2016/5/19 更新)
tailsさんのPerl(30)とは、次のようなコードでした。

文字数のカウントなしでpopcountができてしまうという…。なんと。
(更新終わり)

Rubyだと32文字かと思っていたのですが、ciaranaさんに教えて頂いて、26文字行けることが分かりました。

まあ、色々な方が既に公開されていますが、次のような感じです。

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が使えますから、何の問題もありません。

ということで、ざっくりと実装したものが次のものになります。

終わりに

整理していくと凄く単純な式に落とし込めるというのは、やはり爽快ですね。