simanのブログ

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

OnlineExam 参戦記録

Codeforcesで開催されていたマラソンマッチに参加してました。

codeforces.com


問題文

オンラインの試験があります。問題は全部で5000問あり、各問題は「YES」または「NO」で解答を行います。採点については各問題ごとに正解不正解を判別し不正解の数が2000に達するまで採点が行われます。最終的な点数は採点が終了した時点の問題番号となります(正解数ではないので注意)。試験には最大100回までチャレンジできます、その間に問題の解答が変化することはありません。なるべく多くの点数を取れるように頑張ってください。

戦略

まず、大きな手がかりとして「採点したスコアの問題番号は不正解」というのがあります。例えば問題数が10で1問でも間違ったら採点終了の場合において、スコアが7だった場合は8問目は不正解ということになります。

f:id:simanman:20160622062424p:plain

まずこれで最大100問は不正解を正解に直すことが出来ます。

特定の範囲を指定して解答をひっくり返す

5000個の問題の中から一部を抜粋して、その部分の解答を反転させてそのスコアの増減を確認してました。

一部を抜き出して
f:id:simanman:20160622063351p:plain

解答を反転させる
f:id:simanman:20160622063427p:plain

初期の頃はこれを範囲40ぐらいで行って68000点ぐらいでした。

変化が少ない部分は分割して再調査

分割して調査していくと、特定の個所ではスコアの変動がかなり少ないところがあります。これは正解数と不正解数がその区間ではほぼ同一なことを示しているのですが、実際には図のように片方に正解が偏って、もう片方に不正解が偏っている場合があります。

f:id:simanman:20160622064122p:plain

その場合にはその区間を再度分割し片方の解答を反転させて再度スコアを計算します。

分割して
f:id:simanman:20160622064350p:plain

片方を反転させて再計算
f:id:simanman:20160622064552p:plain

図ではスコアが上昇したのでもう片方の領域については何も行いませんが、もし、スコアが低下した場合はもう片方の領域を反転させます。(その場合は正確なスコアの取得は行わず予測スコアを計算します

感想

シンプルな問題でしたが色々考察しがいのある問題でした。問題の環境としてtesterがもうちょっと充実していると良かったです。あと、提出間隔に制限が無いのはいいですね。

NYC Lightning Round 参戦記録

診断人さんのツイートで気づいて参戦しました

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16756&pm=14282


問題文

縦横長さが D のボードがあります、ボードの各ピクセルには色が割り当てられています。このゲームは2人対戦ゲームで、プレイヤー0の初期領地は左上(0,0)、プレイヤー1の初期マスは右下( D - 1, D - 1 )です。プレイヤーはなるべく多くの領地を取得することが目的です。各プレイヤーはターン毎に任意の色を指定することが出来ます。この時、現在の自分の領地の色または相手の領地の色は選択出来ません。色を指定すると以下の操作が行われます。

  • 自分の領地に隣接しており、かつ誰の領地でもなく、指定した色と同じ色のマスを自分の領地にする
  • 自分の領地の色を指定した色に塗り替える

この操作をプレイヤーが交互に行い、全てのマスがいずれかのプレイヤーの領地になるまでゲームを続けます。最終的なスコアは「自分が占領したマス / 全てのマス」となります。

戦略

最初は一直線にフィールドの中心を目指します。(むしろ中心から敵の初期位置寄り)、このゲームでは「相手の陣地は取れない」のでなるべく大きく自分の陣地を囲みに行きたいからです。そして、到達後は相手の伸びしろを消すためにボードの端っこを目指して不可侵領域を作りに行きます。最初は貪欲にマスを取っていましたが、最終的には不可侵領域を多く作るほうが効率が良かったです。

貪欲パターン

貪欲にマスを取ると領地が図のような感じで増えますが、同時に相手の領地も増えやすい形になってしまいます。

f:id:simanman:20160618003525p:plain

f:id:simanman:20160618003539p:plain

不可侵領域パターン

最初に相手に近づいて不可侵領域を作ります

f:id:simanman:20160618003815p:plain

f:id:simanman:20160618003824p:plain

この戦略が取れるのは今回の対戦するAIがランダムに色を選択するタイプだったので、比較的、敵の領地の広がり方が遅いのでこの戦略が使えました。

1日マラソン参加しましたけど集中力が全然持たないですね、もっとゆっくり参加したかったです。あと1日マラソンでtesterにバグ生えてるのは勘弁して下さい

Examples

Example scores:
0) 0.62
1) 0.7975
2) 0.7822222222222223
3) 0.9122
4) 0.8722601248366961

TCO 16 Round2参加記録 - StarTraveller -

TCO 16 Round2 が終了しました。

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16703&pm=14268

問題文

ある宇宙空間にN個の星とM個の宇宙船とK個のUFOが存在しています。宇宙船は星と星の間を移動する際にその星と星の間の距離の長さ分の燃料を消費します。
宇宙船は移動する際に、UFOと一緒に移動した場合は消費燃料が0.001倍になります。(UFOが複数ある場合は効果が重複されます)あなたは「全ての星を1回訪れるような宇宙船の移動計画を立てる」のが目的となります。使用する燃料が最小となるように計画を立ててください。

TSP問題(巡回セールスマン問題)がベースとなっている問題でした。(宇宙船 1でUFO 0の場合とか完全にTSPです)

戦略

自分の今回の戦略についてです。

1ターン目

1ターン目は全宇宙船に対して停止命令を出します。というのも1ターン目は星の到達判定が発生しないので、宇宙船の初期位置が訪問済みと認定されないためです

追跡するUFOを決める

今回の問題では通常移動とUFOと一緒に行動する時の燃料の消費差が1000倍あるので、基本的にはUFOと一緒に行動します。ただUFOに乗り込むタイミングが結講難しくて、その辺り苦労しました(最後もここでずっと悩んでました)。というのも UFOに乗り込むのに通常コストで燃料を消費 しないといけないので「なるべく早く乗り込みたい。。。でも距離が遠い。。。」みたいなところでトレードオフをうまく調整する必要があったからです。(あとは1つのUFOに乗る宇宙船は1台にしてました)


消費コストを考えると乗りにくい
f:id:simanman:20160526002654p:plain


かと言って、待ちすぎると今度は到達できる星の数が減ってしまう
f:id:simanman:20160526002852p:plain


自分の場合はUFOと宇宙船の遭遇率を考えてその辺りは調整しました。(例えば宇宙船1つでUFO1つのケースなら遭遇率は低いので、乗り込む閾値を高く設定、一方、宇宙船10個のUFO20個のケースであれば遭遇率は高いはずなので乗り込む閾値を低くする)

この辺りは若干、過学習させた感はあるので本番スコア下がるかも。。。

UFOを追跡する

追跡するUFOを決めたら「残り時間 - 未到達星 > 0」の間ずっとUFOを追跡します。

経路を作成する

最後に残った星を訪問する経路を作成します、自分の場合は宇宙船が1つの時と2つ以上ある場合で経路の作成方法を分けています。経路の作成には「初期解の構成」+ 「山登り法 or 焼きなまし法」を使用しました

初期経路の構成

まずは初期経路を生成します。初期経路の生成には「NN法 (Nearest Neighbor)」と「FI法 (Farthest Insertion)」の2つを使用しました(今回は制限時間が長かったので両方試してスコアが良いほうを選択しています)。個人的にNN法のほうが後半の焼きなましの時に改善しやすく、FI法は初期の精度は良いが焼きなましで改善しにくい印象を受けました。

NN法 (Nearest Neighbor)

NN法では以下の手順で経路が作成されます

1. 未到達の星の中からランダムで1つを選択

1が選択されたと仮定
f:id:simanman:20160526004150p:plain

2. 選択された星から一番近い星を求める

2番が選択される
f:id:simanman:20160526004236p:plain

3. その星に移動

1-2の経路が作成される
f:id:simanman:20160526004358p:plain

4. 未到達の星がなくなるまで2-3を繰り返す

f:id:simanman:20160526004723p:plain

f:id:simanman:20160526004734p:plain

f:id:simanman:20160526004752p:plain

こんな感じで経路を作成していきます。NN法では終盤にかなり効率の悪い経路を作成する傾向があります

FI法(Farthest Insertion)

FI法では以下の手順で経路を作成していきます

1. 既に作成している経路から一番遠い未到達の星を選択

ここでは既に1-3の経路が完成しているものとします
f:id:simanman:20160526010135p:plain

現在完成している経路から一番遠い星を選択します
f:id:simanman:20160526010218p:plain

ちなみにここで逆に一番近い星を選択するとNI法(Nearest Insertion)になります。

2. コストが最小となるように星を挿入

星を選択後、経路「A -> B」に挿入するとして「A -> C -> B」、この時のコスト「AC + CB - AB」が一番最小となる場所に挿入を行います

f:id:simanman:20160526010429p:plain

3. 未到達の星がなくなるまで1-2を繰り返します

4を追加
f:id:simanman:20160526010708p:plain

最後に2を追加して終了
f:id:simanman:20160526010818p:plain


FI法ではNN法に比べ、精度の高い経路が生成されます。(特に星の数が1000を超えてくると顕著です)

宇宙船が1つのとき

初期の経路の生成後、以下の操作を近傍と定義し焼きなましを行いました。

1. ある2点間の星の訪問順番を交換する

ランダムで経路から2点を選び交換します

f:id:simanman:20160525203733p:plain

2点をランダムで選択

f:id:simanman:20160525204036p:plain

交換する

f:id:simanman:20160525204150p:plain

2. 交差している経路が存在する場合に、交差部分を取り除く

下のような経路が存在している場合に

f:id:simanman:20160525235717p:plain

以下の2点を選択したとします(実際にはランダムで選択しています)

f:id:simanman:20160525235843p:plain

選択した星からスタートして、交換処理ができなくなるまで交換し続けます

f:id:simanman:20160526000141p:plain

処理が完了すると交差していた部分が解消されます

f:id:simanman:20160526000244p:plain

3. 経路から任意の場所を抜き出して、任意の場所に入れなおす

経路の中からランダムから1つ選択します

f:id:simanman:20160526000424p:plain

2が選ばれた場合
f:id:simanman:20160526000555p:plain

切り離して
f:id:simanman:20160526000815p:plain

ランダムで選択された場所に挿入します(図は4-5の間が選択された場合)

f:id:simanman:20160526000929p:plain

宇宙船が2つ以上の場合

初期経路の生成後、以下の操作を行った後にコストが減少した場合に経路の更新を行いました(山登り)

1. 任意の宇宙船の経路が交差していた場合にこれを取り除く
2. 任意の宇宙船の訪問経路から2点を選び、これを入れ替える
3. 任意の宇宙船の経路を反転する
4. ある宇宙船の経路の一部を切り取り、それを別の宇宙船の経路の最後に追加する
5. ある宇宙船の経路の一部を切り取り、それを別の宇宙船の経理の先頭に追加する


その他

他にも細かく調整したポイントについて

UFOの乗り換え

UFO追跡中に時折、他のUFOと重なるタイミングがあります。この時に重なったUFOが無人でかつ平均移動距離が今のUFOより長い場合はそこで乗り換えを行いました。(平均移動距離が長いと星の到達率が高くなる傾向があるので)、特に宇宙船が1つのケースではスコアの上昇が顕著でした。

一時離脱

UFOの行動は2ターン先まで与えられているのですが、たまにUFOが行って戻ってくる時があります。この時は次の訪問地が到達済みの場合にUFOから下りてました。(0.001倍になっていてもチリも積もればなんとやら)

2が到達済みならばUFOが戻ってくるまで1で待機しておく
f:id:simanman:20160526013553p:plain

離れすぎた宇宙船の回収

自分は1つのUFOに対して1つの宇宙船を乗せていましたが、宇宙船の数 > UFOの数のケースにおいて、UFOに乗れない宇宙船が出てきました。このケースだと、一定ターン経つと 周りに未到達の星が全く無い 状態が発生します。

f:id:simanman:20160526011820p:plain

この状態は後で星を探索する際に不利なので 、近くにUFOが来たらそれに乗っかり未到達星の近くまで移動します。

近くにUFOが来る
f:id:simanman:20160526012152p:plain

それに乗っかる(他の宇宙船が乗っていても関係なし)
f:id:simanman:20160526012201p:plain

未到達の星がある近くまで移動する
f:id:simanman:20160526012247p:plain

UFOから下りて再度停止モード
f:id:simanman:20160526012308p:plain

Examples

Example scores:
0) 2063.911340486327
1) 7700.186086852073
2) 4577.47499473865
3) 2367.5522684008797
4) 8787.464703717615
5) 5524.8693553478615
6) 8296.651085271313
7) 4765.360580919411
8) 6927.3815665480315
9) 12032.230311687837

TCO 16 Round1参加記録 - CutTheRoots -

久々の日記です、今年もTCOの季節になりました。

Round 1の問題は「CutTheRoots 」で、簡単に説明すると植木鉢の中にある植物を根っこをなるべく切り取らないように切り分けるかの問題でした。

TopCoder


図としては下のような感じです。


最初は複数の植物がのびのび成長しています。

f:id:simanman:20160420235548p:plain:w400


これを直線を引いて各自バラバラになるように切り分けます。

f:id:simanman:20160420235828p:plain:w400

この時、下の赤、紫の部分で黒くなった部分がありますが、これは直線で切り分けた際に根っこを切り落としたことを示しています(今回のスコアではこの切落しの長さをいかに少なくするかが争われました)


今回、自分の方針としては貪欲法で

  • ランダムに線を大量に引く
  • 一番良さそうな線を残す

この2つを植物同士が完全に切り分けられるまで、ひたすら繰り返していました。

1. 与えられた植物同士で完全グラフを作る

今回、終了判定がなかなか難しくて最終的に「完全グラフの辺を全て切断したら終了」というプログラムにしました。最初はドロネー三角分割で生成した線を全部切断したら終了ってやっていたのですが、これだと全て切断しても完全に分けきれていない状態があったので諦めました。

まず最初に初期状態から

f:id:simanman:20160420233828p:plain:w300

完全グラフを作ります(と言っても長すぎる辺は無視してたりしてます)

f:id:simanman:20160420234008p:plain:w300

あとはバッサバッサ辺を切り落としていきます

f:id:simanman:20160420234125p:plain:w300

線を引いて切り落とす

f:id:simanman:20160420234154p:plain:w300

全部切り落としたら終了です

f:id:simanman:20160420234557p:plain:w300

f:id:simanman:20160420234611p:plain:w300

これで切り分け完了です。この直線を選ぶときの評価値としては

  • 直線を引いた際に切り落とした根っこの長さの合計 / 切り落としたグラフの辺の数

みたいな評価にしてました(あと、直線上に植物があると切り分け判定でバグったので、その直線は除外とかしてました)

終了後に無駄な直線の排除

切り分け後に、引いた直線を調べて「この直線を取り除いても、全ての辺が削除された状態を維持出来る」場合にその直線を排除する処理をいれました。

高速化

枝が多いと直線と枝の交差判定だけでめちゃめちゃ時間とられたので、その辺りの高速化と、あとは現在の評価値の一番いいやつより良いスコアを出せなくなったら交差判定を即終了とかやってました。

時間調整難しい

やたら自分の提出数が多いのは、今回ちょっと時間管理が難しくてその辺りの調整で迷走した結果です。

感想

本当は焼きなましを使いたいなと思っていましたが実装できませんでした。

Tシャツ欲しかったです(30位以内でもらえた年度ならワンチャンあったかも)

現在開催中 or 今後開催予定のマラソンマッチ系コンテストについて

これは 「Competitive Programming (その2) Advent Calendar 2015 」の12日目の記事です。
www.adventar.org


マラソンマッチとは、2週間から長いもので1ヶ月以上の期間をかけて行われるコンテストです。有名なところではTopcoderMarathon Matchがあります。なぜかマラソンマッチ系のコンテストは冬に集中するので、今後のリマインダー的なものとしてご活用下さい。

ハル研究所 プログラミングコンテスト 2015

www.hallab.co.jp

コンテスト期間

  • 「2015 12/15(木) - 2016 01/07(木)」

説明

スマブラ」、「カービィ」 等の開発元で有名なHAL研究所主催のコンテストです。今年は学生が対象の「学生部門」とHAL研社員対象の「HAL研部門」の2つに分かれています。

SamurAI Coding 2015 - 16

samuraicoding.info

コンテスト期間

  • 1次予選 2016年1月8日迄
  • 2次予選 2016年2月8日迄

説明

情報処理学会が主催しているAIコンテストです。今年のお題は某Splat○○nを彷彿とさせるお題となっています。

Kaggle Santa

www.kaggle.com

期間

  • 2016 1/8迄

説明

賞金総額20,000$というビックなコンテストです。

Marathon Match 90

期間

  • 12/15/2015 3:00:00 - 12/29/2015 3:00:00」

説明

TopCoder社が定期的に出題しているコンテストです。ある問題に対しての最適化を行うお題を出されることが多いです。

TENTATIVE Secret Santa Marathon Match

期間

  • 12/16/2015 3:00:00 - 12/30/2015 3:00:00

説明

こちらもTopcoderからの出題予定です。

Prostate Cancer Foundation Stupski Prize Challenge - Computational Oncology

期間

  • 12/16/2015 3:00:00 - 12/30/2015 3:00:00

説明

こちらもTopcoder社からの出題となります。同時に3つとはスゴイですね

CODERS STRIKE BACK

www.codingame.com

期間

  • 2016 2/21から8日間

説明

CodinGameというフランスにあるプログラミング学習サイトが開催しているコンテストです。大体の傾向としてはゲームAIを参加者同士で対戦させる形式が多いです。

恐らく開催(個人の感想

CODE VS

codevs.jp

期間 (追記 2015/12/14)

  • 風の噂で来年の3月にやるとかやらないとか。(公式で発表があったらリンクはります)

説明

日本最大級のAI対戦型コンテストです。恐らく今月中には何かしらのアナウンスがあるんじゃないかなーと勝手に想像してます。


以上、駆け足でしたが自分が把握している中でのマラソン系のコンテスト一覧です。他にも「こんなコンテストがあるぜ!」という方はコメントかリプライで教えてください!

「Code Festival A If you cannot solve this」参加記録

CodeFestivalの短縮王の事前公開問題があったのでそれをやっていました。

anarchy golf - Code Festival A If you cannot solve this

問題としては

クラスメイトのテストの点が与えられる。
クラスの平均点の半分以下である点数を赤点と定義する。
s1が赤点ならFail 、赤点でなければ Passを出力する(s1とはクラスの1人目の人) 

というものでした。そして、今回書いたコードはこれです。

#!ruby -apl
$_=eval$F*'+~'+">-2*%d*%d?:Pass:'Fail'"%$F

ちょっとだけ解説します。

#!ruby -apl

この謎の記述ですが、これは「Rubyを実行オプション-a -p -lを有効にして実行するぞ!」という宣言です。

pオプションが有効になっている場合はプログラム全体が

while gets
    .
    .
    .
  print $_
end

のように動作します。ここで$_はgetsしたときの値が入っています。

aオプションはpオプションが有効になっている状態で各whileループで

$F = $_.split

を実行してくれます。

lオプションはpオプションが指定されているときに、各行に対してchop!を実行し、また$_の出力時に改行をつけてくれます。

他のオプションについては Rubyの起動 (Ruby 1.9.3) に詳しく書かれています。

今回は入力形式として以下のように与えられていました。

# クラスの人数 1人目の点数 2人目の点数 3人目の点数 4人目の点数
4 42 1 90 77

そのまま書くとこんな感じになるのですが

# クラスの人数と点数リストを分ける
n,*a=$F.map(&:to_f)
# 平均点の半分より大きければPass
a[0]>a.inject(:+)/n/2?:Pass:'Fail'

これをベースにどんどん変化させます。まず

a[0]>a.inject(:+)/n/2

この部分ですが、to_fに依存しない形に変形します。(後々evalを使った式に変形するため)

2*n*a[0]>a.inject(:+)

次に数値化していた部分のコードをevalを使って省きます。

eval"2*#{$F[0]}*#{$F[1]}>#{$F[1..-1]*'+'}?:Pass:'Fail'"

このままだと長過ぎるので、String#%を使って左側の値は%dに置き換えます。

eval"2*%d*%d>#{$F[1..-1]*'+'}?:Pass:'Fail'"%$F

ここまで来ると「$F[1..-1]*'+'」の部分も消し去りたくなります。今はクラスの合計値を出すために

$F[1..-1]*'+' #=> 42+1+90+77

になっていますがこれを

$F*'+~' #=> 4+~42+~1+~90+~77

に置き換えます。この状態は、クラスの人数をn、合計点数をSとすると

n+(-S-n) => -S

とクラスの合計点数にマイナスをかけた値が出ます。これは「~n」が「~n == -n-1」を表すため、

n + ~s1 + ~s2 + ~s3 + ~s4
n + (-s1-1) + (-s2-1) + (-s3-1) + (-s4-1)
n - (s1 + s2 + s3 + s4) - 4
-S

となり、ちょうどいい感じにnを消し去ることができます。

あとは、これを条件が崩れないように変形してあげると最後の

#!ruby -apl
$_=eval$F*'+~'+">-2*%d*%d?:Pass:'Fail'"%$F

になります。「$F*'+~'」の記述をみつけるのに10hぐらい使った気がします。

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

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

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を使ったテクニックなのですが、目から鱗でした。