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

simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

【コードゴルフ】シンプル・ライフゲーム 参加日記

ここ数日コードゴルフという競技で遊んでいました。

codeiq.jp

題材としてはライフゲームというゲームをいかに短く書くかの勝負で、今回Ruby部門で一番短くかけました。

d.hatena.ne.jp

今回書いたコードです。(136byte)

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

ちょっと見づらいので整形します

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

1つずつ解説していきます。

n,h,w,*f=*$<;

今回は入力の形が「世代、高さ、幅、フィールド」という形で与えられていたので、「*$<」で与えられた入力を展開して、それぞれに割りふります。最初の3行を受け取れば残りはフィールドなので「*f」で回収します。

n.to_i.times{
.
.
.
}

n世代分繰り返します。ここは色々試しましたがこれが一番短かったです。

z=w=w.to_i;

wの値は後で頻繁に使用するのでここで数値化しておきます。ついでにz変数もwで初期化しておきます。(後で使用)

f=f.map{|l|
.
.
.
}

現在fの要素にはフィールド情報の各行が文字列として格納されています。ライフゲームでは次の世代のフィールド情報を作成して更新する必要があるのですが、一時変数を使用するとどうしても長くなってしまうので、fにmapを適用してその返り値を再度fに代入することで一時的な変数を使用せずに実現します。lには行の情報が入ります。

l.gsub(/./){
    (?*+$&+?.*z+=1)[(0..8).count{|e|(f*2)[~-z/w-e/3][(z-e%3)%w]<?.}-3]
}

1つずつのセルを見ていく必要があるのですが、ここで「l.chars.map」を使用した場合には最後に「*''」で終わる必要があるので、gsubで1文字ずつキャプチャし、その1文字に対して置換を行っていきます。(返り値は置換された文字列が返ってくるので「*''」もいらない!、あと本来はブロック変数にキャプチャした文字が入ってきますが、$&にも同じ値が入っているのでこれを使用することで1文字減ります)

(0..8).count{|e|(f*2)[~-z/w-e/3][(z-e%3)%w]<?.}

周囲のセルを数える処理ですが、今回は画面の端がループする仕様でした。しかしRubyでは幸運なことに-1の値は配列の後ろから数えた値を取ってくるので、負値に関しては気にすることなく参照できるのですが、(hもしくはw)の値をオーバーした場合にはnilを返してしまうので泣く泣く「%hか%w」をする必要があります。

f:id:simanman:20151119201019p:plain

そこで最初のy座標については元の配列の大きさを2倍にすることでオーバしても「%h」せずに済むようにしました。

f:id:simanman:20151119201454p:plain

これで「(hoge)%h」な記述を避けることができて良いです。

[~-z/w-e/3]

この記述ですが、通常周りのセルを参照する場合には「-y-1,-y,-y+1」なコードを書くのですが、これだと「y+e/3-1」になります、そこで、どこか事前にyを+1しておくことで「y-e/3」の記述に変更することができます。自分の場合はzの初期化の際に+1の処理を書いています。ただ、このままだと最後の値が1つ繰り上がってしまうので「~-」で実際のzの値より1小さい値にしておく必要があります。(x方向の参照も同様に事前に+1してます)

<?.

これは取得した文字を比較して「*」の時にtrueを返すようにしてます。「==?*」より1文字お得です。

最後に取得した生きているセルの値を文字列のindex参照として使ってます。rubyでは文字列に対して[]メソッドが使えるので、普通に書けば

"...*#{c}....."[index]

の記述で次の世代の文字に更新されるのですが(まず生きてる死んでるにかかわらず生きてるセルの数が3つであれば無条件で生き残ります。あとは4つパターンが生きてる状態だと生、死んでる状態だと死です。なのでこれはそのままキャプチャした値を返せばOKです)これだと少し長いので、まず左方向に3つずらして

"*#{c}........"[index]

「.」が連続するので文字に*メソッドを使って圧縮します。(5になっているのは*が9個あっても-3されて6、つまりs[6]が参照できればOKなので5にしてます)

(?*+c+?.*5)[index]

この5はzで代用します(ついでにインクリメントします)

(?*+c+?.*z+=1)

でも、これは問題があって、最大で生きてるセルが(9-3=6)出るはずなので、3x3フィールドで全部のセルが生きていた場合には、参照しきれずnilが返って、出力が異なってしまいます("*x....".size #=> 6)。が、今回のテストケースはPassしたのでスルーします。(グレー感ある


今回の個人的なキーポイントは

  • countがブロックを取れる
  • gsubがブロックを取れる

この2つでした。

取り組んだ時間は多分50hぐらいだと思います。

まだ雰囲気的に短くなりそうな感じがあるので、これより短いコードを思いついたら是非教えてください!

追記(2015/11/19 23:21:00)

自分と同率1位だった@rotary-oさんのコードが公開されました。


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

3x3のコーナケースで落ちない正統派解答です。

i+=1;(?*+$&+?.*5)

を 

(?*+$&+?.*i+=1)

に変えれば、今回の問題に関して言えば2byteさらに短くなります。(グレーゾーン解答

自分も1次元で何回かトライしてたのですが、うまくいかなくて諦めちゃったんですよね。。。

正統派で行くのであれば、減るサイズは1byteですが

"...*#$&"[(0..8).count{|j|(s*2)[(i-j%3)%w-(~-i/w-j/3)*~w]<?.}]||?.

こんな感じで書けます。

さらに追記(2015/11/24 02:18)

前回の追記で134byteが最短だと思っていたのですが、shinhさんによってさらに3byte減りました。

はじめてのにき(2015-11-24)

テクニックとしては

n.to_i.times{
.
(繰り返しの処理)
.
}

としていたところを

eval "(繰り返しの処理)"*n.to_i

こんな感じで(繰り返し行う処理)を文字列化して「*n」をしてあげることで、「n.to_i.times」と同じ処理を行っています。evalを使ったテクニックなのですが、目から鱗でした。