読者です 読者をやめる 読者になる 読者になる

おもしろwebサービス開発日記

Ruby や Rails を中心に、web技術について書いています

Google Developer Day 2011 の Dev Quiz に挑戦した

ruby coffeescript

初めてチャレンジしてみました!以下感想。

分野別

Web Game と 一人ゲーム をやりました。Web Game は jquery の click メソッドでなぜかクリックできなくてハマりました(イベント周りの知識不足)。また試しに CoffeeScript を使ってみたら慣れてないせいでちょこちょこ躓いたりしました。

devquiz2011webgame用コード ― Gist

一人ゲームは適当にやってたらできたので本当にひどいコードです><1手で全部取り除けると仮定して実行、2手で全部取り除けると仮定して…というロジックで総当たりでやったらできました。。
devquiz2011一人ゲーム用コード ― Gist

スライドパズル

大学の時に受けたアルゴリズムの授業を思い出しながら試行錯誤しました。まず、幅優先探索で実装して実行したのですが3×3しかまともな時間で解けませんでした。いろいろな枝刈り方法を試した結果、最終的には、キューが一定までたまった場合にキューを全部調べて正解から遠いものをばっさり取り除くロジックを追加することで高速化しました。これにより、12時間ほどで970問解答することが出来ました。

あとは、上一列または左一列が揃ったら、揃った部分を固定するようなコードを付け加える予定でしたが時間が足らず中途半端な形で実装したりしています。また、直近の結果をキャッシュするような仕組みも考えましたがあまり速度が向上しなかったのでコメントアウトしています。

反省点としては、なんとなくスライドの内容を配列として管理することにしたのですが、文字列のまま操作するようにしたらもう少し速度が稼げたはずだという点。あとは複数プロセスで並列実行させて回答数を増やすロジックを追加できたらもっと解答数を増やせたのに><と思いました。来年はそのあたりを最初から実装したいと思います。

よかった点は、配列操作周りのテストコードを書いたこと。おかげで安心してロジック部分に専念することが出来ました。テストコードすばらしい!

devquiz2011スライドパズル用コード ― Gist

感想

普段webサービスを作る時には使わない筋肉を使うのが楽しかったです!今年は109.7点と、Developer Day に参加できるか微妙なラインですが、来年は満点とれるように今からちょいちょいアルゴリズム周りの勉強もしていきたいと思います。