今年もやってきました。DevQuizの季節。

11月1日にGoogle Developer Day 2011 Japanが開催されます。

だめもとでTop Favorites枠に応募してみたら、受かってしまった・・・。
(Androidアプリぐらいしか回答してなかったようなきがするけど。）
だけど、DevQuiz楽しいから今回も回答してみた。
点数やソースコードなどでも晒してみる。

ソースコードをgoogle codeに公開しました。
リファクタリングなどしておらず、メソッド名も適当で見辛いです。

各問題の解き方など
・クイズ
ひたすらググった・・・。

・Android
aidlを使ってサービスをバインドする問題。
aidlとかつかったことないし・・・。
ということで青本(Google Androidプログラミング入門)を見ながら、解いた。
書いてある通りにやってみると、意外に簡単。

・WebGame
神経衰弱をするゲーム。
ヒントにChrome Extentionのサンプルコードがあったので、改造して作った。
最初に全てめくり、どこにどの色があるか覚え、同じ色をめくっていくだけ。

・一人ゲーム
1,000,000以下の数字が1〜10個まであって、数を半分にするか、5の倍数の数字を取り除くかの操作ができる。
全ての数を取り除いたら終了で最短操作数を答える問題。

1,000,000以下の数字なので、最大21回操作すれば終了できる。つまり、再帰で処理しても、スタックオーバーフローの問題は起きない。
あと、5の倍数でも10の倍数だったら、その時に取り除かなくても操作回数が変わることはない。
そこで、下一桁が5の数があるときと残っている数のすべてが0のときのみ、5の倍数の数字を取り除く処理をする。
この方針ですべてのパターンを再帰で求め、操作数が最小のものを回答とした。

・スライドパズル
3×3〜6×6までの盤面で空白が1つあり、上下左右にスライドさせて目的の盤面にするゲーム。ただし壁と呼ばれる動かせないマスがある。
これの空白の動かした右左上下のそれぞれの回数をカウントし、
初めからそれぞれの操作できる回数を超えないようにする必要がある。
1問0.01点で5000問ある。

5000問無理、壁あるし。

まず、3×3の壁なし問題から着手。
解法があるので、その解法にしたがって動かすだけ。
参考にした解法：わたしの日記 ３×３スライドパズルの解き方　　２月２４日からのバクストパズル

これで3×3をすべて解く。

次に、3xN、Nx3を着手。
3xNは、一番上の行を揃えると残りは3x(N-1)になるので
一番上の行だけ揃えて3x(N-1)を解く。
同様にNx3は左端だけ揃えると(N-1)x3になるので
左端だけ揃えて(N-1)x3を解く。

それを6×6までやれば、壁なし問題は全部解ける。
ここまで解いて1135問。
探索もしないから1秒もしないで結果もすぐ出る。

さて、壁あり問題・・・。
これが厄介。
というわけで、問題としては壁を含んでいるが、もともとそろっていて
結果的に壁なし問題に帰着される物だけ解く。
これで、1183問。

次に、3×3の壁あり問題を解きにかかるのだが、
4パターンに分かれるので、回転するパターンを除いて
壁なしの2×3と3×2になるようにして、後は必勝パターン。

あとは適当に探索して、解けたものだけ提出。
探索の深さを30ぐらいだと全然終わらないので
探索深さ15、スレッド4(4問同時処理という意味)ぐらいでやったけど、そんなに伸びず
1450問。
時間切れ。

5000問全部解いた人というか2000問以上解いている人スゲー。と思う。

DevQuizに参加したみなさん、お疲れ様でした。
GDD2011JPに行かれる方は現地で〜。

最後に得点履歴。