シンプル・ライフゲーム tailsさんコード解析
はじめに
CodeIQというところで、コードゴルフ問題「シンプル・ライフゲーム」に参加したわけですが。折角なので同じPerlで挑戦されたトップのtailsさんのコードを解析してみたいと思います。 codeiq.jp
コード
tailsさんが公開されたPerl(133)のコードです。CodeIQ環境と違い、ideoneでは“ge for”の部分の空白が省けませんが、そこ以外で大きな違いはありません。
解析
全体像
で、さて。「ライフゲーム」自体、基本的には地道に処理する、つまりセル毎に隣接セルの生き死にを調べ、その数に応じて生き死にを変化させる、そういう処理以外は多分無理だと思います。
tailさんのコードも、そういう意味では地道なものです。まずは、細部を省略したコードに直してみます。
$n=<>; # 世代数 <>; # 行数は無視 $/=<>; # 列数 @a=/./g,s##～#eg for($_=<>)x$n; # メインループ print
最初の3か所の<>でパラメータを読み込み、メインループで格子データを世代数分更新し、最後に出力と。特に変なところはありません。 ただ、行数は使わなくても何とかなるパラメータなので、ここでは読み飛ばしています。
格子データの扱い
では、実際に更新を行う格子データですが、このコードではデフォルト変数 $_ に全行分を文字列データとして格納しています。なので、最後に print を無引数で呼びだせば出力も出来て、文字数的にも優しい戦略です。
ただ、初期格子を <> を1行ずつ読み込むのは…? という所、気になります。
$/=<>; ～ for($_=<>)x$n;
実は、列数を敢えて $/ に保持することで、入力時の行区切り文字がデフォルトの「改行文字」でなくなりますから、一回の <> で残りの全行を読み込むことができます。良く、“undef $/”とかの形を見ると思うのですが、これと似たような話で一石二鳥です。
この格子データから、($_=<>)x$n のように、世代数分の要素を持つリストを作って for ループを回しているのですが、こういう書き方をすると「格子データのコピーのリスト」ではなくて「同一の格子データに対する参照のリスト」のような扱いになるのか、同じ $_ が繰り返し使われることが分かっています。なので、繰り返し $_ を更新するのに短い書き方ができます。
※実アプリを組む時でも、「値のコピーのリスト」を作るつもりで「実体が同じ複数の参照データのリスト」を作って、変な動作になってしまうことがあるので、意識したい所ですね。
格子データ更新処理概略
いよいよメインのセル更新処理ですが、forループの中身を取り出すとこのようになっています。
@a=/./g,s## 次世代のセル . !++$x#eg
@a は、更新前の格子状況をリスト化したものですね。$_ から substr や vec で抽出することもできる ( 全格子を一括更新するので、更新前後の情報が混じることを気にしなくて良い ) のですが文字数が嵩みますから、リスト化して [] で参照できるようにすると後々便利です。なお、/./ でパターンマッチしていますから、格子データに含まれる改行文字が取り除かれた、純粋な '.' と '*' だけのリストになっています。
そして、s###eg ( / の代わりに # ) で $_ を一括更新します。パターンが空ですが、その前に /./g を実行していますのでそのパターンが引き継がれ、「改行を除いた全ての文字」が更新対象となります。
そうした場合、特殊変数 $-[0] ( 実際は "@-" の形で使った方が短い ) を使えばマッチ位置が割り出せるのですが、まあ文字数的に長いですし、改行含みの位置だと扱いにくいので、別途セル位置 ( 1次元化した上での!! ) を扱うためのカウンター $x が用意されています。
“.!++$x”というのは奇妙に見えますが、これはインクリメントを後に持ってきて、なおかつセルの計算に影響を与えない工夫と思われます。! は論理否定なので !++$x は「偽」になるのですが、これは空文字列の扱いになるので、. で連結しても影響を及ぼさないのです。
更新後セルの生成
で、文字数的に一番長いのがセルの生成の部分です。
chr(46^4&6176>>grep!${$a[($x/$/%@a+$_%3-1)*$/%@a+($x+$_/3%3-1)%$/]},0..8,(4)x6)
これは、隣接セルの判定と、その結果からのセルの生成との2個の機能に大きく分かれます。
セルの生成
先にセルの生成から行きます。
chr(46^4&6176>>grep 隣接セルが生 ,0..8,(4)x6)
chr によってセルの文字を作りだす訳ですが、生/死 */. に対応した文字コードは 46/42、なので xor 演算で 46^(4 または 0) として文字コードを計算します。
^ の右側が4になる、つまり生のケースは、& 以降の 4 のbitが立っている時です。そこで隣接セルのカウントが関係します。
ここで自身の生死によって条件が変わってくるところをどうしたかと言うと、隣接セルをカウントする際に、「自身のセル」に7倍の傾斜をかけて対応しているところが面白い所です。すなわち、
- 元の条件
- 自身が生なら、隣接セル2 or 3個が生の時に限って、次世代も生
- 自身が死なら、隣接セル3個が生の時に限って、次世代も生
- 傾斜をつけて一本化した条件
- 自身の生 ( 1 or 0 ) の7倍と、隣接セルの生の数の合計が、3 or 9 or 10 の時に限って、次世代も生
マジックナンバー 6176 ( 2進数で 1100000100000 ) を、傾斜をかけたカウント数分右シフトすると、丁度生になるときに4のbitが立つ訳です。
なお、隣接セル ( 自身も含めて ) は、0～8 の数値で区別をつけています。4が自身ですね。grep は「条件にあった要素を抽出する」関数ですが、スカラコンテキストでは「条件にあった要素数」として使えますので、0～8 1個ずつと、プラス 4 6個分を対象とすることで、上記傾斜をかけたカウントが出てくるわけです。
隣接セルの判定
残りは隣接セルの判定です。 しかし、コード上には、'.' や '*' との比較、eq や ne 演算子が出てきていません。一見不思議な所です。
grep!${ 隣接セルの文字 },0..8,(4)x6
中間を省略すると、上のような形式をしていますが、実は隣接セルの文字を ${～} でスカラ変数としてデリファレンスすることで生死を判定しています。生の場合は $* であり 0、死の場合は $. であり、これは入力行番号なので非ゼロ、! で論理否定を取れば、丁度生の判定に使えるという事です。
…実は ${～} の形式って、英数でない文字でも色々使えちゃうんですね。文字数的なインパクトはそれほど大きくはないのですが、こういうネタまで動員できる所はやはり凄いです。
後は、リスト化していた格子データ @a からセルを取り出すところ、この [] の中身は単純にインデクス計算です。
$a[($x/$/%@a+$_%3-1)*$/%@a+($x+$_/3%3-1)%$/]
自身も含めた隣接セル 0～8 は、下の図のようになっていて、grep の中ですので、デフォルト変数 $_ にその数値が入っています。
行数データは読み捨てたのでありませんが、列数 $/ と、全格子数 = 列数×行数 が @a ( スカラコンテキスト ) で使えますので大丈夫です。格子位置 $x は途中リセットしていませんので、延々 ( 格子数をも超えて ) 増えていきますが、格子数 @a での mod で見ればちゃんと正しい位置を指してくれていますし問題ありません。
ただ、注意が必要なのは、Perl の除算はデフォルトで小数になってしまうこと ( 割り切れない場合 )。なので、/ の後に % をかまして整数として扱えるようにしています。…これ2箇所ありますが、後の方の $_/3%3 の部分は無くても大丈夫そうですね。なぜなら除算結果を乗算に使わない ( 小数点以下の端数が増幅されない ) から。ここで2文字縮むことになりそうです。
終わりに
真面目にコード解説すると結構大変ですね。いや、自分のコードはかなり流しましたけど、真面目にやれば同じくらいのボリュームには…なるかな??
ところで、隣接セルのカウントからセル生成を差し替えると、1文字縮むことに気付いてしまいました。$_/3%3 の %3 も削ると3文字短縮ですね。
# before
$n=<>;<>;$/=<>;@a=/./g,s##chr(46^4&6176>>grep!${$a[($x/$/%@a+$_%3-1)*$/%@a+($x+$_/3%3-1)%$/]},0..8,(4)x6).!++$x#ge for($_=<>)x$n;print
# after
$n=<>;<>;$/=<>;@a=/./g,s##(6-(grep${$a[($x/$/%@a+$_%3-1)*$/%@a+($x+$_/3-1)%$/]},0..8)&~!${$&}?'.':'*').!++$x#ge for($_=<>)x$n;print
'.' や '*' がベタに出てくるからアレかなと思ったのですが、意外と短かったんですね。
