ここ数日コードゴルフという競技で遊んでいました。
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」をする必要があります。
そこで最初のy座標については元の配列の大きさを2倍にすることでオーバしても「%h」せずに済むようにしました。
これで「(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したのでスルーします。(グレー感ある
今回の個人的なキーポイントは
この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を使ったテクニックなのですが、目から鱗でした。