Google Developer Day 2010 Japan の DevQuizを一応やったわけですよ。
2-legged OAuth
http://market.android.com/details?id=net.vvakame.frothyfeed
↑俺専用FriendFeed投稿アプリ作ったときの資産があったので1時間か2時間くらいでクリア
ハマりポイントは…
- 正規化しないといけない
- 今回のソース的にはLinkedHashMapに、アルファベット順に要素を詰めていってクリア(ソートしてないw)
- Content-Length忘れて怒られる
- 接続後2XX以外が返ってきたときもBody的な部分が取れてそこに詳細なエラー原因が書いてあることに延々と気がつかなかった
しりとり
Lv.1, Lv.2 は適当に手でやってたら解けた。
Lv.3で苦戦した。一応コード書いてみたりしたんだけど、計算しきっても相手の出してくる手が特定できずにうまく計算しきる事が出来なかった…。
で、うまくアルゴリズムに起こせず
http://bit.ly/cgqwNG
↑こーゆー感じでうんうん唸りながら1時間以上困ってた。
途中で、問題が全く変わっていないことに気がつき、wordの最後の文字を選んだら死ぬものと死なないものに分けてブラックリストホワイトリストみたいにして、まだみぬ末尾を選んで適当にポチポチポチやっていったら倒せた。結局手動…
Packman
まずソース
http://gist.github.com/557303
方針
- 評価関数を作らない
- 頭良い評価関数作るの難しそう
- 深さ優先探索しない
- 進捗が把握しにくくて決断遅くなりそうだったから
に加えて、 @awaku7 さんより、「問題文見てさえないけどモンテカルロ法とか使えるんじゃね？」とのフォースを授かる。
で、実装してみた。
実装
締め切り2日前くらい
Lv.1は幅優先探索で探索 スコア41
Lv.2も幅優先探索で探索 スコア226
Lv.1はまぁ狭いし適当に探索してやったら3秒くらいで探索出来た
Lv.2も幅優先探索で20秒くらいで探索できた… んだけど、どういうパラメータでやったかメモってなくて再現できなかった…(今も再現できてない)
Lv.3幅優先探索では190くらいまでしか探索できなかった… OutOfMemoryでメモリ足りなくなって死ぬ
Wave追悼会
@t_egg さんにLv.3のお嫁さん解をグラフィカルに見せていただいた。
ここで、幅優先探索に組み込んだ制約により、長期的な最適手は早めに刈られてしまって駄目だろこれということが分かった。
締め切り前日
Lv.3は手動プレイ スコア456
モンテカルロ法をようやく実装。プレイアウトが案外低速で答え出なさそうなことがなんとなく分かる
手動でプレイできるモードの作成。e部分のヘッコミを最速で回収するとこまで手動でやって、そこらからスタートするヒント付きモンテカルロを実装して動かす。
手動で456点とか出てなんかもういいや…と涙を一雫流して終了。就寝。
朝起きたらモンテカルロもなんかエラー出して止まってた…！！制限時間終了まで生き残った場合の条件考慮不足でOutOfBoundExceptionかなんか吐いてた。俺のDevQuizは終わった。
こうすればよかった…
- 1マス単位で移動して幅優先探索は効率悪すぎた
- 交差点→交差点間の移動までを1アクションとして計算しきってしまいキューに詰める
- 1回その場で停止とかの動作も作ってキューに詰めてみる
- 最初にヒントを与えてやるのは良かったかも(計算量的な意味で)
- AI作った人(多分青山さんとかこの解き方だと思うんだけど)どーやったかｷﾆﾅﾙ…
- 枝狩りの方法もっと考えて計算量減らさないと駄目だった…
エッセー
"開発王に俺はなるっ！！" っと書いて提出。
- 採点する人が笑ったら勝ち
- ネタAnswerなので読むのに時間がかかったら悪いので短文で。
結論
お願いですから合格してください…orz
行けないとか恥ずかしくて泣いちゃう。
