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

シンプル・ライフゲームに挑戦しました ( CodeIQ )

はじめに

CodeIQ というところで開催していたコードゴルフ問題、「シンプル・ライフゲーム」に挑戦しました。

d.hatena.ne.jp

出題者ozyさんの上記集計記事にある通り、Brainf**kで堂々の1位、Perlはtailsさんに次ぐ2位という結果になりました…って、いやまあ、Perlで10文字も離されましたが。

問題

ライフゲーム自体は、Wikipediaの説明を見るのが早いと思います。ただし、端は上下・左右ともループして繋がっているものとして扱います。
入力データは、

  • 1行目 … 世代数
  • 2行目 … 格子の行数 ( 高さ )
  • 3行目 … 格子の列数 ( 幅 )
  • 4行目以降 … 格子の各行、生/死は */. で表される

となっており、指定の世代数を経たのちの格子を、入力データのように */. で出力する、という問題になります。

なお、指定のケースの3番目は、格子サイズ35×40、30世代であり、無駄な処理を挟むと結構TLEしてしまいますので注意が必要でした。

提出コード

Perl(143)

まあ見たまんまですが。コメントアウトされているPerl(145)にある通り、当初は“mine sweeper”( こちらの資料 のp.30~ ) のコードにインスパイアされて、文字列のbit演算を絡めた処理を考えていました。

さて。隣接セルの状態を見る必要があるという事は、格子データをin-placeに更新し辛いという事、また、端がループしているので、素直に処理するにはインデクス計算にmodが絡んでしまうところがちょっと厄介でした。
なので、このコードでは、現在の格子状況を別途2重リスト @x にとっておくこと、その際に縦を3重、横を2重にすることで、行数・列数での mod なしで隣接セルのインデクスが得られるようにしました。
@x は、メインの格子データ @m の行が移る毎に shift で寸詰めしていくので、行アクセスのインデクスは固定、列アクセスについては検索のマッチ位置 $-[0] からのオフセットで扱えます。

なお、セル毎に、自身を含んだ隣接セル3×3の中での生存セルの個数を N、自身の生死を S ( 生:1、死:0 ) とすると、次世代で生となるのは、

  • S && ( N==3 || N==4 ) || !S && N==3

という条件ですが、勿論こんな長い式は面倒なので、

  • (N-3)&~S ( 但し、非ゼロで「死」 )

とbit演算を使って判定することにしました。コード中の grep の所が N の計算に相当します。

ところで、トップの tails さんのコードを参考に、$. と $* を文字比較の短縮に活用してみたら、4文字減って139になることが分かりました。…それでも6文字足りないですが、一応1tweetには収まるということで。

for(($n,$r,$c,@m)=<>;$n--;map{shift@x;s#.#6-(grep${$x[$r-$_/3][$-[0]+$_%3-1]},-2..6)&~!${$&}?'.':'*'#eg}@m){@x=(map[(/./g)x2],@m)x3}print@m

Brainf**k(1794)

はい、えっと。お気付きの方も多いと思いますが、これは出題ケースの答えをハードコーディングしたものです。1行目の世代数が 3,10,30 なので 3→改行 or 0、1 というパターンでどのケースかを区別する、と。ケース1,3 は2字決まり、ケース2は1字決まりですね ( 百人一首風 )。

ただ、格子データを1セル→1セルで対応づけると2,000文字を超えてしまうので、ある程度の塊をまとめるようにして圧縮しています。まあ、最適解を考えるほどでもないのでザックリと。

Brainf**k(1276)

ただまあ、ハードコーディングはあんまりなので、一応真面目に解いたものも用意しました。
見たまんま素直な実装で、隣接格子の絶対位置を計算して都度先頭からアクセスしてfetch&count、次の生死をstore ( 実際には、markだけつけておいて、世代毎のループの最後で update ) というものです。
ただし、格子サイズが大きくなると余裕でTLEなので使えませんが。なぜTLEかというと、以下でtweetした通り ( 使い回し )。

終わりに

シンプルな問題ながら、色々な工夫があって面白い問題でした。んーしかし、Rubyにも負けるとは!!