シンプル・ライフゲームに挑戦しました ( CodeIQ )
はじめに
CodeIQ というところで開催していたコードゴルフ問題、「シンプル・ライフゲーム」に挑戦しました。
出題者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した通り ( 使い回し )。
さてまあ。BFも最初はマジメに組もうとは思っていただけど。多分2,000文字程度でいけると思うんだけど。圧倒的に処理時間が…ということで断念。少なくとも領域サイズ固定にでもしないと、1秒以内は無理な気がする。( シンプル・ライフゲーム ) #CodeIQ
— angel-p57 (@angel_p_57) November 19, 2015
終わりに
シンプルな問題ながら、色々な工夫があって面白い問題でした。んーしかし、Rubyにも負けるとは!!