Google Developer Day (GDD) 2011 DevQuiz 回答スクリプト

Google Developer Day 2011 Japan DevQuiz 通称 GDD 2011 DevQuiz に挑戦してました。
結局まとまった時間は先週の夜と週末だけだったので、なかなか思うように進みませんでした。

まず手始めにウォームアップクイズから始めたのですが、google が公開している API とか詳しくないので満点を取るのには思いのほか苦労しました。クイズは Web Game と一人ゲームを解きました。この２つは比較的難易度が低かったので時間はかかりませんでした。そして最後の難関のスライドパズルは良案が終了１時間前に思い浮かぶも時間切れ。結局 2355 問しか提出することができませんでした。というわけで採点結果は下記の通りとなりました。

最近はプログラミングから離れていたので良い刺激になりました。
さて、以下回答例を晒しておきます。必ずしも良案ではないのであしからず・・・。

- スポンサーリンク -

Web Game

Web Game はシンプルな神経衰弱ゲームで、全 64 セットを解くことで問題クリアです。カードはクリックすることでめくることができます。手作業では嫌になる枚数のカードが出てくるのでソースコードを解析して、自動化するスクリプトを作成することとなります。ここは思いっきり手を抜いて、Firefox でゲームをスタートしてカードが表示されたら firebug のコンソールから javascript を 64 回実行することで解決しました。

firebug で実行させる javascript コードはこちら：webgame.js.txt

一人ゲーム

入力データが与えられ、次の２つの処理を使って、なるべく少ない手数で数を全て取り除く問題です。
　- 全ての数を半分にする（端数は切り捨て）
　- 5 の倍数 (0 を含む) を全て取り除く

これは単純に二分探索木を作って深さ優先で探索して、数値が全てなくなるリーフまでの深さが最も浅い場所をみつけるプログラムを記述すれば解くことができます。

perl での一人ゲーム回答スクリプトはこちら：oneman_game.pl

スライドパズル

今回のチャレンジクイズはパズルが苦手な僕にとっては難題でした。決められた手数内で様々なパターンと局面数のスライドパズル 5,000 問を解くという課題でしたが、常に最適解で解くアルゴリズムはまだ確立されていない（・・・と理解しているのですが。）ため、最適解ではないにしても、如何に少ない手数で省メモリで短時間で解くか？を自分で考え抜く必要があります。

ネットで検索すれば、知識を用いて効率的に探索する方法（ヒューリスティック探索）として、A* アルゴリズム（A star algorithm）とよばれる手法が見つかります。ただネットで見つかる情報は 3x3 の 8 パズルだったり 4x4 の 15 パズルだったりするので、今回のクイズのように 6x6 の 35 パズルを "まじめ" に探索しようとするためメモリが幾らあっても足らない状況になります。

そこで LL 言語じゃなくて C 言語などで実行速度と省メモリを実現するのがベターな解法なのですが、C 言語も Java もほぼ忘れてしまっていて、結局 perl で記述することになりました。当然ながらメモリと実行速度の戦いになってしまったので、思い切った枝切りと運に任せた解法でプログラムを実装しました。
結局、まともな速度で問題を解くことができるプログラムになったのは土曜日の時点で、その後もちょっとずつチューニングしてみたのですが満点にはほど遠い結果となりました。3000 問ほど解答して決められた手順内で収まったのは 2355 問でした。

ちなみに大いに参考にしたサイトはこちら

~~書きたいことはいろいろあるけど後で追記するとして、~~　→追記しました。
取り敢えずソースを晒しておこうかと思います。メモリが 2GB ほどのマシンでも動きます。スピード的には全然満足いってませんが、今時の PC なら丸一日回していれば 3000 問ほどは解けていると思います。
下記のファイルを同一フォルダへ保存して asearch.pl を実行するだけです。answer.txt というファイルが出力されます。指定条件内に解けなかった問題はスキップされます。解答数を増やすため再実行することが可能で、その場合は answer.txt を answer_db.txt にリネームしておくと前回解答内容が引き継がれます。

クイズファイル：/pub/tools/gdd2011/problems.txt
解答スクリプト：/pub/tools/gdd2011/asearch.pl

スクリプトの実行方法

perl  asearch.pl

スクリプトの実行結果例

エントリが長くなったので、ソースコードは上記のリンクからファイルを取得して見てください。
工夫した点は下記の通りです。

ベースとなるアルゴリズムは双方向 A*
コストはいわゆるマンハッタン距離と手数。マンハッタン距離は重み付けをして計算している。この重み付け次第で解ける数が随分と変わる。
高速化のためある程度グローバル変数やむなし。
perl の sort 関数は単純な数値比較の場合は激速。ハッシュを sort させると遅いので変数の持ち方を工夫。
ゴール方向からの探索は 13 手順先までの全パターンを生成して、スタートからの A* 探索でマッチングする箇所を探し当てる。何手順まで生成しておけばよいかは手探りで 13 という数値にしている。
同コストの場合はランダムで選択。ある意味運が必要になる。
思い切った枝切りをする。見つからなくてもやむなし。
10 万手順まで探索してもゴールにたどり着けなかったら諦める。

提出時の工夫だけでは 2300 点程度が限界の解法でしたが、ここに乗せた解法は２回ほど実行させれば（まる二日ほどかかりますけど・・・）スクリプトは結構いい線まで行くと思います。

- スポンサーリンク -