gdd2011

Google Developer Day 2011に参加するためのDevQuizというクイズがあるのですが、それを解いてみました。

今年の問題は、

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

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

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

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

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

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

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

今回の反省点は、

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

という点でした。

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

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