Conway's Game of Life
via CodeGolf
Game of Life という有名なゲームがあることは辛うじて知っていたんですが、実装については全く分からずにいました。
個人的にこの手のクイズは大の苦手で、まともに解いたことが無いという悔しさと、「生命」というテーマが面白そうだったこともあり、挑戦してみました。
ゲームの詳細は wikipedia 記事を参照していただくとして、ルールのみ引用しておきます。
http://en.wikipedia.org/wiki/Conway%27s_game_of_life
- Any live cell with fewer than two neighbours dies, as if by loneliness.
- Any live cell with more than three neighbours dies, as if by overcrowding.
- Any live cell with two or three neighbours lives, unchanged, to the next generation.
- Any dead cell with exactly three neighbours comes to life.
孤独・過密による死、適切な環境下での誕生・生命維持というルールにより、細胞が自動的に生死を繰り返すのを見守る、というゲームです。
セルの状態をどんなデータ構造で表すのか、という点がこの問題の肝になるようです。最初は私も途方に暮れたんですが、下の Hacker Emblem を眺めながら
o o ooo
イメージを展開するうちに思い付くことが出来ました。
こちらです: GoL.htm
既存の実装は一切参考にしませんでした。これから挑戦しようという方のためにも詳しい話は控えたいと思います。
一つだけ、スポイラーにならない実装をご紹介しておきましょう。Vim のパッケージに含まれている life.vim というマクロです ($VIMRUNTIME/macros/life/life.vim)。
見た目に恐ろしく、さっぱり意味が分かりません。お持ちの方は安心して開いてみてください。
追記 [20061031]:
計算量がなるべく少なく済むようにしてみました (が、エンバグの可能性もあるかも知れません)。
あと、デフォルトの初期状態を「グライダー・ガン」にしてみました。Hacker Emblem を無限に発射し続けるというパターンです。
言い忘れましたが、入力の形式は CodeGolf の出題の形式に従っています。一行目に世代数、それ以降に初期設定のパターンを書いてください。
スペース文字は非生命状態、それ以外の文字は生きた状態と見なされます。