Journal InTime

_ 松江Ruby会議08

今年も松江Ruby会議に参加してきた。

食後のコーヒーを飲んでいたらLTを聞き逃したが、その他のセッションはどれも楽しめた。松田さんの講演でdisられたけど。

吉岡さんに言われて参加したプログラミングコンテストでは一般部門1位でMisocaさん提供のAmazon Dash Button 1万円分（つまりボタン20個）をいただいた。

最終計測では2位のsimanさんと4msec差だったそうなので、測定誤差のような気がする。

同じようなプログラムをたくさん応募したのでどれが1位になったのかはっきりしないが、バイト数的にたぶん以下のプログラムだと思う。

m=$<.read;v=m.tr($/,?#).unpack"C*";g=/G/=~m;q=[s=/S/=~m];while(i=q.pop)!=g;v[i]=35;[1,-1,s,-s].each{|d|v[j=i+d]!=35&&q<<j&&$:[j]=i}end;m[i]=?:while(i=$:[i])!=s;$><<m

各変数は以下のような意味をもつ。

• m -> map = マップ情報
• v -> visited = 探索済みノード情報（兼壁情報）
• s -> start = スタート位置
• q -> queue = キュー（最終的にスタックになってしまった）
• i -> 探索中ノードのインデックス
• j -> 隣接ノードのインデックス
• $: -> 経路情報(最終的にマップ上に:と出力）

一文字変数のわりにわかりやすい（自画自賛）。

その後さらに削って

q=[i=s=/S/=~m=$<.read];v=m.tr$/,?#;[1,-1,s,-s].each{|d|v[j=i+d]!=(v[i]=?#)&&q<<j&&$:[j]=i}while/G/!~v[i=q.pop];m[i]=?:while(i=$:[i])!=s;$><<m

こんなのや

m=$<.read;q=[i=s=/S/=~v=m.dup];[1,-1,s,-s].each{|d|v[i]=$/;/#|
/!~v[j=i+d]&&q<<j&&$:[j]=i}while/G/!~v[i=q.pop];m[i]=?:while(i=$:[i])!=s;$><<m

こんなのも応募（ブラウザからだと改行がCRLFになってしまうので、Net::HTTPで送信）したが、文字数節約のため探索済みノードのマーク(v[i]=?#)を無駄にeachの中に押しこんだり、vが配列ではなく文字列になったりしている分遅かったかもしれない。

最初はマップによっては速くなるかもしれないと思ってA*で書いていたが、

• ヒューリスティック関数で常に0を返すようにしても本番のマップだとタイムが変わらないのでダイクストラに修正。
• 隣接ノードへの移動コストはすべて1なので単純なBFSに（priority queueやsorted arrayがいらない）。
• DFSに変更しても本番のマップ5つすべてクリアできることに気付きDFSに（shiftよりpopの方が短い）。

という感じ修正して、今回の条件だと単純な実装が一番速いという結果に。 たぶんマップが小さくて経路も少なく、A*が有利になるようなマップ（スタート・ゴールが偏っていて経路が直線的なのとか）もなかったのだろう。

工夫した点は

• マップや探索済みノードの情報を二次元配列（というかjagged array）で持つとコストが大きいので、一次元配列を採用。 座標(x, y)をx + マップ幅 * yというインデックスに変換して扱うが、単純なBFS/DFSでは座標を意識する必要すらなかったので低コストにできた。
• スタート・ゴール以外は壁で囲まれていることを利用して、インデックスが範囲外かどうかのチェックを省略。
• ただし、スタートから左に移動すると壁がないため、改行($/)を壁(#)に置換。
• 探索済みノードの情報を上記の壁情報と共通化。
• すべてのマップでスタート位置が同じで二行目先頭だったため、マップ幅の計算をスタート位置で代用。

といったところ。

変数のスコープ的にwhile修飾子が使いにくいことを実感したので何か言語仕様の変更を提案しようかとも思ったが、ゴルフとかでしか使わなさそうだ（し自分はゴルファーじゃない）からやっぱりいいか。