GDD2011のDevQuizを解いてみた

![gdd2011](/media/images/gdd2011.png)

[Google Developer Day 2011](http://www.google.com/events/developerday/2011/tokyo/)に参加するための DevQuiz というクイズがあるのですが、それを解いてみました。

今年の問題は、

- ウォームアップクイズ(4 択問題)
- 分野別(4 問あって、うち 2 問を選択)
- チャレンジクイズ(5000 問のスライドパズルをひたすら解く)

という 3 本立てになっていて、スライドパズル以外は満点であたりまえ、スライドパズルをどれだけ解くか、という勝負でした。

で、どうだったかというと、いろいろトラブルがありつつも、なんとかスライドパズルを 1472 問解いて、ボーダーラインは超えたようです。

どんなトラブルがあったかというと、

- 解の判定処理がバグってて、3x3 しか解けない
- 締切 24 時間前ぐらいにメインの PC が起動しなくなる
- 盤面の評価関数がバグってて、ヒューリスティックが働かない

という感じでした。特にメイン PC が壊れたときは、どうしようかと思いました。
結局 Amazon EC2 で c1.xlarge インスタンスを作って、2 時間だけ回してパワー不足を補いました。

また、途中まで全然計画とか立てずに、闇雲に探索していたので、それでかなり時間をロスしていました。
盤面が小さい、解きやすい問題から解いていった方が良かったです。

今回の反省点は、

- 問題をよく見て、戦略を練ってから問題を解くべき
- 基本的な部分にバグがあると後で困るので、十分にテストしておく等で対処するべき

という点でした。

やっつけなコードですが、一応[アップ](/media/binary/gdd2011_src.zip)しておきます。
探索は、深さ優先の反復深化でやってます。
A\*も試したんですが、 今回のデータ構造だと Open リストが膨れてしまい、メモリに乗らなくなる感じでした。

もうちょっと時間があれば、データを切り詰めたり(std::string 使ってる時点でありえない)、
評価関数を凝ったり、いろいろできたとは思うのですが、まあ、こんなもんかなーと。