カメヲラボ

主にプログラミングとお勉強全般について書いてます

【コードゴルフ】シンプル・ライフゲーム【解説】

本稿はCodeIQで2015年11月5日～同年11月19日に出題された「【コードゴルフ】シンプル・ライフゲーム」という問題の解法に関する記事です。

問題文はこちら

【コードゴルフ】シンプル・ライフゲーム【解説】

◆注意

本問は「ショートコーディング」・「コードゴルフ」と呼ばれる、ソースコードをできるだけ短く書く遊びの一環として出題されたものですので、一般的なプログラミング解説とは少し異なります。

◆はじめに

今回は普段と比べてコードを短縮するのが難しい問題でしたが、素晴らしい解答をたくさんいただきました。早速紹介・解説を…という気持ちもありますが、その前に本問に挑戦しなかった方へ1つ問題です。

最短コードのサイズは、何バイトだったでしょう？

次項の基本的なアルゴリズムを見ながら予想してください。

◆アルゴリズムを考えよう

C風の疑似コードで書くと、基本的なアルゴリズムは以下のようになります。

for( N世代 ) {
  for( 縦方向 ) {
    for( 横方向 ) {

      // 近傍8方向を調べる
      for( 上下 ) {
        for( 左右 ) {
          '*'を数える // '*'を含むセルは「生」を意味する
        }
      }

      if( その位置のセルが「生」 ) {
        if( '*'の数が2個または3個 ) {
          「生」
        } else {
          「死」
        }
      } else { // その位置のセルが「死」
        if( '*' の数が3個 ) {
          「生」
        } else {
          「死」
        }
      }

    }
  }
}

世代数分、フィールドの縦・横方向、各セルの近傍走査を行うために5重のループが必要になります。生死判定のための条件分岐も必要になりますので、なかなか複雑そうですね。

また、実装上の問題として、フィールドデータを2次元配列で保持する場合、生死判定を行ったとき元の配列をすぐに書き替えてしまうと、その隣のセルの生死判定に影響してしまいます。そのために、通常はもう一つ配列を用意します。

この疑似コードは28行ですが、入出力処理の部分は省いてあります。入出力部分も含めて40行くらいと考えると、1行平均20文字程度として、40×20で800バイトくらいのコードになりそうです。

今回問題にチャレンジしなかった皆さんも、ここまでの内容を踏まえて実際にコードを書いてみてください。比較的短く書きやすいスクリプト系の言語でも、おそらく500バイトを超えると思います。

◆驚愕の最短記録

では、最初の問の答えを発表します。最短コードはtailsさんによるPerlのコードで、サイズはなんと133バイト！「入力を取るだけでも133バイト超えてるよ！」という方も多いのではないでしょうか。

$n=<>;<>;$/=<>;@a=/./g,s##chr(46^4&6176>>grep!${$a[($x/$/%@a+$_%3-1)*$/%@a+($x+$_/3%3-1)%$/]},0..8,(4)x6).!++$x#gefor($_=<>)x$n;print

あえて改行やスペースは挿入せず、そのまま掲載します。grepとかprintという単語がなければもはやプログラムには見えませんね。

このコードの中に、コード短縮のテクニックがぎっしりと詰まっているのです。 詰まり過ぎていて細かく説明すると非常に長くなってしまいますが、主要なテクニックはすべて解説します。

◆1行に秘められた10の極意

極意☆1　―　入力

Perlでは、標準入力から1行読み込む場合に「」と書きますが、「<>」でも読み込むことができます。入力フォーマットは、世代数N, フィールド縦サイズH, 横サイズW, フィールドデータ（H×Wの文字列）ですから、最初に出てくる3つの「<>」はそれぞれN, H, Wを読み込んでいることになります。

Hについては読み込んだ後変数に代入せず、要らないデータとして捨てられていることになります（理由は後述）。

極意☆2　―　組み込み変数「$/」

「$/」という変数は組み込み変数の1つで、行区切りとして扱う文字”\n”が最初から与えられています。Wを読み込む際に、「Wなんだから$wの方がわかりやすいんじゃない？」と思う方もいらっしゃるかもしれませんが、「$/」を指定することで行区切り文字を上書きしているのです。

区切り文字が見つからない場合は入力の末尾まで読み込まれるので、N行のフィールデータを1回の「<>」で読み込むことができるのです。

極意☆3　―　組み込み変数「$_」とprint関数

「$」も組み込み変数の1つで、これを使いこなせるかどうかでコードサイズが大きく変わります。たとえば、コードの最後には「print」としか書かれていません。何をprintするのか書かれていないなら、何も表示されないのではないかと思ってしまいそうですが、print関数の引数を省略すると、「$」が持っている値を出力するようになっています。

つまり、print関数が呼び出される前に「$」に出力したい内容を代入していれば、出力時には「print」と書くだけで済みます。print関数以外にも、「$」をデフォルト引数とする関数はいくつかありますので、興味のある方は調べてみてください。

極意☆4　―　for修飾子

Perlゴルファーは、forループを

for(式) {
  ...
}

のような形で使うことはほとんどありません。通常はfor文ではなくfor修飾子、すなわち

... for 式

のような形で用い、不要な括弧を書かないようにします。

... for($_=<>)x$n

の部分を簡単に説明すると、まずフィールドデータを「$」に代入し、($, $, …, $)と、「$_」がn個あるリストを生成します。

そのリストの各要素に対して操作することができます。forループ内では「$」への参照が「$」が渡され「$_」は常にフィールドデータを指すことになります。つまり【極意3】のテクニックがループ内外で使えることになります。

極意☆5　―　パターンマッチ演算

「/./g」や「s##～中略～#ge」の部分はパターンマッチ演算で、この部分にもコード短縮テクニックが使われています。まず、マッチング対象の変数は【極意3】【極意4】で説明した「$_」ですので、

@a = $_ =~ /./g, $_ =~ s##～中略～#ge

という意味です。「$」に対してマッチングを行う場合は「$ =~」の部分を省略できるため、非常に短く書くことができます。

また、最初のマッチングで「/./g」と書いてある箇所は、「.」というパターン（改行以外の任意の一文字）になっています。ところがその後の「s##～#ge」のパターンに何も書かれていません。

本来なら「s#.#～#ge」と書かなければならないはずです。空文字列にも関わらずうまく動いているのは、パターンの部分を省略すると最後に成功したマッチングのパターンが代わりに使われるからです。

極意☆6　―　s///ge

これはパターンマッチ演算の1つで「s/置換対象/置換後の文字列/」のように使い、Perlゴルフの必須テクニックになっています。コードでは区切り文字を「/」ではなく「#」としていますが、これは置換後の文字列の中に「/」が含まれているためです。

「ge」と書かれている部分はオプションで、「g」はマッチングを行う文字列に対してマッチングを繰り返し行うという意味です。「e」は置換後の文字列を式として評価するという意味になります。これらのオプションによって、少ない記述で高度な繰り返し処理が可能になります。

各セルに対するマッチングで、全体的にはH×W回のループに相当します。置換後の文字列の部分には生死判定の処理（【極意7】以降）が書かれていて、非常に複雑になっています。

極意☆7　―　ループ代わりのgrep関数

「grep 式,リスト」のように書くと、リストの各要素（ローカルな「$_」に渡される）に対して、式の部分が評価されます。式に相当する部分は「!${～中略～}」で、リストに相当する部分は「0..8,(4)x6」です。リストの部分をもう少しわかりやすく書くと、「0,1,2,3,4,5,6,7,8,4,4,4,4,4,4」です。

0から8までは、周囲8近傍のセルのindexに変換するためのものであると想像がつきます。残りの4,4,4,4,4,4の部分が少しわかりにくいかもしれませんが、「4」という値は0,1,2,3,4,5,6,7,8のちょうど中央の値で、中心セル（生死判定の対象になるセル）のindexに相当します。

中心セルへのアクセスを6回余分すなわち7回に増やすことで、中心セルが「生」の場合と「死」の場合を区別できるようにしています。周囲の8セルがすべて「生」の場合は8カウントが増えることになりますから、状態を正しく判別するためには中心セルが「生」の場合に9を加算する必要があります。

しかしこのコードでは7しか加算しないので、

・中心セルが「死」で、周囲の7セルが「生」と

・中心セルが「生」で、周囲のセルがすべて「死」

の区別、

・中心セルが「死」で、周囲の8セルが「生」と

・中心セルが「生」で、周囲の1セルが「生」

の区別ができなくなってしまいます。しかし、いずれの場合も次世代の中心セルは「死」と判定されるため問題ありませんし、情報を圧縮することでメリットが生まれます（後述）。

極意☆8　―　配列のスカラ値利用

「@a」は配列を表す変数ですが「$/%@a」のように剰余を求める演算として、つまりスカラ値のような使い方をしています。このような使い方をすると「@a」は配列のサイズ、つまりフィールドの縦サイズ×横サイズとなります。

【極意1】で、縦のサイズ（H)を捨てているのは、「@a」をスカラ値として利用しているからなのです。

極意☆9　―　組み込み変数「$.」

grep関数で、「 !${$a[～中略～]} 」という式の部分に注目してください。「 $a[～] 」の部分は「.」か「*」です。「 ${～} 」の部分はあまり馴染みが無いかもしれませんが、たとえば「 ${a} 」のように書くと変数「$a」にアクセスすることができます。

つまり、「 ${$a[～]} 」は「 ${.} 」と「 ${} 」のいずれかであり、「$.」と「$」の2種類の変数にアクセスすることになります。

このうち「$.」は組み込み変数の1つで、ファイルハンドルの行カウンタになっています。コード内でデータの読み込みを行っている部分（<>と書いている部分）は4か所ありますから、「$.」の値は4（つまり非0）になっています。

対して「$」は未定義です。さらに「 ${～} 」の前には論理否定の「!」が付いていますから、grep関数の文脈では「!$.」はfalse、「!$」はtrueとなり、grep関数は「*」の個数分要素を持った配列を返すことになります。

極意☆10　―　6176

最後に「464&6176>>grep～」という部分について説明しておきましょう。演算の順序がわかりやすくなるように括弧を付けて書くと、「46 ^ (4 & (6176 >> (grep～)))」のようになります。

grep関数の部分は【極意9】で説明した通りで、中心セルとその8近傍のセルに含まれる「*」の数に応じてビットシフトを行います。

6176と2進表現にすると「1100000100000」となっています。この値に対して、たとえば『中心セルが「死」で周囲3セルが「生」』の場合は、grep関数が(1,1,1)というサイズ3の配列を返し、それを【極意8】のテクニックでスカラ値として用いると整数値3になります。

3ビット右シフトを行うと、「1100000100」となり、4のビット（右から3つ目）が1になります。また、46（「.」のASCIIコード）と42（「*」のASCIIコード）は4のビットをon/offすることで切り替えが可能です。

このように、次世代のセルが生存する場合だけ4のビットが1になるような値を用意し、簡単なビット演算だけで「.」と「*」を切り替えることに成功しています。

【極意3】で述べた通り、生存条件を表す情報を圧縮していますが、もし圧縮しなければ6176よりも大きな定数を用いる必要があります。そうなると数値の桁数が増え、結果としてコードサイズが1バイト増えてしまうことになります。

◆さらなる短縮を求めて

シンプル・ライフゲーム tailsさんコード解析にて、angelさんの解説記事とさらにコードを短縮するためのテクニックが紹介されています。 興味のある方は是非ご覧ください！

◆Rubyの最短コード

最も挑戦者が多いRubyで見事最短にたどり着いたsimanmanさん、rotary-oさんのコードを紹介しておきます。こちらもコードの短さに驚いてもらえるよう、改行やスペースは挿入していません。

simanmanさん（136バイト）

n,h,w,*f=*$<;n.to_i.times{z=w=w.to_i;f=f.map{|l|l.gsub(/./){(?*+$&+?.*z+=1)[(0..8).count{|e|(f*2)[~-z/w-e/3][(z-e%3)%w]<?.}-3]}}};puts f

rotary-oさん（136バイト）

n,h,w,*s=*$<;s*='';n.to_i.times{i=w=w.to_i;s.gsub!(/./){i+=1;(?*+$&+?.*5)[(0..8).count{|j|(s*2)[(i-j%3)%w-(~-i/w-j/3)*~w]<?.}-3]}};$><<s

simanmanさんの【コードゴルフ】シンプル・ライフゲーム 参加日記で詳しい説明やさらに短くするアイデアが書かれていますが、本稿でもポイントを簡単に解説しておきます。

ポイント☆1　―　入出力と組み込み変数「$<」「$>」

最初に紹介したPerlのコードと比べて入力処理が非常に短く書けているのが大きな特徴です。「$<」というのは組み込み変数で、組み込み定数ARGFの別名です。実行時引数がなければ、STDINの代わりに使えます。

「$<」のように「」をつけることで複数行の標準入力が展開されます。

rotary-oさんは「$>」も使っていますがこちらは標準出力で、「$><<値」で出力が可能です。puts関数と同じ4文字ですが、スペースを入れる必要が無いので1バイト分短縮できます。

simanmanさんも使えば良いんじゃないかと思った方もいらっしゃるかもしれません。しかしsimanmanさんのコードではフィールドデータを配列で持っているので、期待通りの出力が得られません。

puts [1,2,3]

は、

1
2
3

と出力されますが、

$><<[1,2,3]

は、

[1, 2, 3]

と出力されてしまうことに注意しなければなりません。

ポイント☆2　―　map, gsub

simanmanさんは配列でフィールドデータを持っているため、map+gsubで次世代のフィールドデータを生成し、現在のフィールドデータと置き換える方法を用いています。

rotary-oさんはフィールドデータを1つの文字列として用いているため、gsub!によって現在のフィールドデータをまとめて置換しています。

ポイント☆3　―　?*+$&+?.

「?+$&+?.」の部分を見ると誤植かと思ってしまいそうですが、「?」は「*」、「?.」は「.」という文字で、「+」によって連結されます。

中央の「$&」は、それより前のgsub(/./)によってマッチする文字になりますので、「」または「.」になります。もうすこしわかりやすく書くと、この部分は「……」か「**…..」のいずれかになります（simanmanさんのコードは「.」の数が異なります）。

2文字目は「$&」の値によって変わりますが、これで生死判定を上手くクリアしています。両者共に、中心セルと周囲8近傍のセルから「*」の数をカウントし、そこから3を引いています。

つまり、文字列の先頭にある「*」は生存セルの合計が3であった場合のindexになり、この部分が

・中心セルが「生」で周囲2セルが「生」

・中心セルが「死」で周囲3セルが「生」

という条件に相当します。2文字目は中心セルによって異なり、

・中心セルが「生」で周囲3セルが「生」

の場合のみ、このindexになります。中心セルが「死」で周囲4セルが「生」の場合と上手く区別することができています。素晴らしいですね！

◆言語別の最短コード

Perl・Ruby以外の最短コードを、サイズの小さい順に紹介しておきます（※多少読みやすくするため、改行・スペースを入れさせていただきました）。

【JavaScript (spidermonkey)】Azicoreさん(178B)

r=readline;
for(b=w=r(h=r(n=~r()));n++;b=t)
  for(t=[i=h];i--;t[n?i:print(u)]=u)
    for(u=r(j=b|0);w>j;u+=1+b[i][j++]|c&&~c?'.':'*')
      for(k=-9,c=5;k++;)
        c-=1+b[~(k/3-i-h)%h][~(k%3-j-w)%w]|0

JavaScriptは実行速度のハンデが結構ありますが、その辺の条件もしっかりクリアできました。forループが多いので、もう少し短く書けるかもしれませんね。Perl・Rubyに次いで3番目に短いコードでした！

【Python】hirosuzukiさん(182B)

n,h,w=eval("input(),"*3)
exec'b=""'+'+raw_input()'*h+';b=[".*"[4<sum(b[(i/w+d/3%3-1)%h*w+(i+d%3-1)%w]<"."for d in range(5,22))<8]+i%w/~-w*"\\n"for i in range(w*h)]'*n;
print"".join(b)

改行が入れ難かったので簡単に解説しておきます。 スクリプト言語系のゴルフではよく使うテクニックですが、繰り返し処理したい部分を文字列で書き、それを複製した後evalやexecで評価することでループ処理を短く書いています。2行目が文字列の連結によってできていることに注目してください。

【C】tailsさん(194B)

i;j;
char a[1<<16];
main(n,h,w,s,t){
  for(scanf("%d%d%d %[^0]",&n,&h,&w,a),s=++w*h;i/s<n;a[i+s]=a[i++]^4&t)
    for(t=67196,j=17;j;t/=a[--j<9?i/s*s+(i/w-j/3-~h)%h*w+(i%w-j%3+w)%~-w:i]/5-7);
  j/=puts(a+i);
}

Perlで最短記録のtailsさんはCでも最短記録を達成しました。ここに詳しい解説がありますので、興味のある方はご覧ください。

【Scala】rotary-oさん(198B)

object Main extends App{
  var n,h,w=readInt
  var a=1 to h map(_=>readLine)
  1 to n map{
    _=>n=w-1
    a=a.map{
      _.map{
        c=>n+=1
        s"...*$c....."(0 to 8 count(i=>a((n/w-i/3+h)%h)((n-i%3+1)%w)<46))
      }
    }
  }
  a.map(println)
}

Rubyで最短記録のrotary-oさんです。アルゴリズム自体はRubyの場合と同じですね。

【Haskell】sysysysyさん(201B)

r=readLn
a=[-1..1]
main=do
  n<-r;h<-r;w<-r
  interact$unlines.(!!n).iterate(\f->[[".*"!!fromEnum(x==3||x==4&&'.'>f!!i!!j)|j<-[0..w-1],x<-[sum[1|k<-a,l<-a,'.'>f!!mod(i+k)h!!mod(j+l)w]]]|i<-[0..h-1]]).lines

こちらも改行が入れ難かったので簡単に説明しておきます。 大まかに見ると世代ごとに、

[ [ “.”または”*” | 横方向jとして(i,j)のセル＋8近傍の”*”の数] | 縦方向i ]

のような内包表記が入れ子になった形でリストを生成しています。除算の文字数が多い言語では無理に1次元化しない方が短く書ける上にわかりやすいですね。

◆オマケ

明らかにコードゴルフに向いていない感じの言語であるにも関わらず、激しくゴルフされているコードを紹介しておきます。

【C#】chatさん, えちごやえちぜんさん(いずれも320B)

Rubyでの挑戦者が多い中、chatさんとえちごやえちぜんさんがC#で激しく競り合い、最終的に同サイズで終了しました。両者のコードを載せておきますので、よくよく見比べてみてください！

・chatさんのコード

using C=System.Console;
class M{
  static void Main(){
    System.Func<int>p=()=>int.Parse(C.ReadLine());
    string s="",t;
    int n=p(),h=p(),w=p(),W=w+1,i=h,j,a;
    for(;i-->0;)s+=C.ReadLine()+"\n";
    for(;n-->0;s=t)
      for(t="",i=0;i<h*W;t+=++i%W*a!=0?".*"[2>>a]:s[i-1])
        for(a=4,j=9;j-->0;)a-=42/s[(h-1+j%3+i/W)%h*W+(w-1+i%W+j/3)%w];
    C.Write(s);
  }
}

・えちごやえちぜんさんのコード

using S=System.Console;
class M{
  static void Main(){
    System.Func<int>R=()=>int.Parse(S.ReadLine());
    int k,p,c,N=R(),H=R(),W=R();
    string A,B="";
    while(B!=(B+=S.ReadLine()));
    for(;N-->0;)
      for(A=B,B="",k=0;k<H*W;B+=c==6|c*A[k]==210?"*":".",B+=++k%W>-N?"":"\n")
        for(c=p=0;p<9;)c+=A[(k/W+p/3+H-1)%H*W+(p++%3+k+W-1)%W]/46;
    S.Write(B);
  }
}

【Fortran】だいじゅさん(323B)

実はだいじゅさんはPython 3の方でもトップを取ってらっしゃる強者ですが、こちらを紹介させていただきます。 剰余を求める場合のコストやenddoの存在が嫌な感じですが、それでもここまで短くなりました。

characterc*99
integer s(99,99),q(99,99),h,w
read*,l,h,w
do i=1,h
  read*,c
  s(:,i)=(/(1-ichar(c(j:j))/46,j=1,w)/)
enddo
do k=1,l
  do i=1,h
    do j=1,w
      b=sum((/((s(mod(j+n,w)+1,mod(i+m,h)+1),m=h-2,h),n=w-2,w)/))
      q(j,i)=transfer(b>2.and.b<4+s(j,i),1)
    enddo
  enddo
  s=q
enddo
do i=1,h
  print"(99a)",(char(46-s(j,i)*4),j=1,w)
enddo
end

【Pascal (fpc)】pikさん(393B)

Fortranもなかなかですが、Pascalも負けていません。無駄に長い予約語で私はイライラするのですが、pikさんは忍耐強いですね。以下のコードはペースを入れてありますが、数値とdoやtoの間はスペースを取り除くことができます。

var N,H,W,C,X,Y,Z,i:Int32;
S,B:AnsiString;
begin Readln(N,H,W);
repeat B:=B+S;Readln(S)until''=S;
S:=B;
repeat for i:=0 to W*H-1
  do begin C:=0;
    Y:=i div W;Z:=i-Y*W;
    for Y:=Y-1 to Y+1 do
      for X:=Z-1 to Z+1 do
        C:=C+Ord(B[Ord(X<W)*X-Ord(X<0)*(X-W+1)+(Ord(Y<H)*Y-Ord(Y<0)*(Y-H+1))*W+1]='*');
        S[i+1]:=('.*')[1+Ord((C=3)or(C*10+2=Ord(B[i+1])))]
      end;
    B:=S;
    Dec(N)
  until N=0;
  for Y:=0 to H-1 do Writeln(Copy(B,1+Y*W,W))
end.

他にも紹介したいコードはありますが、文章量の都合でここまでとさせていただきます。たくさんの挑戦ありがとうございました！