Yak!の日記： Google Developer Day 2010 jp DevQuiz 参戦メモ
Google Developer Day とか DevQuiz が何かは説明略。ウォーミングアップ、HTML5、Maps API、OAuth、しりとり、PAC-MAN の SuperHackers コースで回答。
ウォーミングアップについては時刻表が表示されない駅を見ていて「？」となったこと以外は問題なし。HTML5 については W3C の Validator を通してしまった。
以下、プログラミング系の回答について。コードはリンク先。無修正ハードコア仕様で他人様に見せるコードになっていないがまぁ臨場感があっていいんではないかということで。
OAuth
OAuth については Perl で Net::OAuth モジュールを使って回答。前回に引き続いて CPAN 様々。
しりとり
しりとりも Perl で回答。対話的に実行できるように作成。LV1 は単純全探索(その手番の勝ち手順が見つかったら他の手は探さないが)。LV2 はメモ化(結果のキャッシュと思えば OK)して対応。
LV3 はメモ化でも単語数 70 近辺で容量不足になったのでちょっと思考。とりあえず先頭と末尾両方が同じ単語は存在しないことは分かった。また、Graphviz でグラフを書いてみたりしたけど複雑すぎてどうにもならず。で、一度手動でやってみたところ(多分、多くの人も最初そうなると思うが)同一末尾はめ殺しパターン(例えば末尾 d の単語がずっと返ってくる)で負けた。で、ひらめき。このはめ殺しパターンだが結局ループが発生しているわけである。例えば d****t と t****d など。この場合、相手が片方を選択した場合、他方を選択することで状況を変化させることなく(単語数自体は減っているが勝敗には影響せず)対応が可能である。ということでループになる単語対を存在しないものとみなしてよい。これで単語数が 60 以下になるので LV2 コードで対応可能となった。実際にはループになる単語を相手が選択した場合は対となる単語を選択し、他の場合は対話的な結果に従えばよい。ループ対を省くコードはこちら
Maps API
Maps API は JavaScript で回答。JavaScript 特有の癖にちょっと振り回された。
for(var i=0;i<data.length;++i) {
for(var j=0;j<data.length;++j) {
if(i!=j) {
directionsService.route(
{
origin: new google.maps.LatLng(data[i]['lat'], data[i]['lng']),
destination: new google.maps.LatLng(data[j]['lat'], data[j]['lng']),
travelMode: google.maps.DirectionsTravelMode.DRIVING
}
, (function(ii,jj) {
return function(res, status) {
if(status == google.maps.DirectionsStatus.OK) {
matrix[ii][jj] = res.routes[0].legs[0].distance.value;
--requests;
if(requests==0) solve(data, matrix);
}
}
})(i,j) // Just using i and j causes error because binded variable becomes 3
);
}
}
}
Maps API のコールバックは非同期に呼ばれるため、全てのコールバックが呼び出された後でないと結果が入っていることが保証できない。単純に directionsService.route() の呼び出し後に計算ルーチン solve() を呼んでも駄目である。ということでコールバック内で最後に呼ばれたコールバックであることを判定して solve() を呼んでいる。
さらにクロージャーに束縛されている変数は参照的に束縛されているため単純に
function(res, staus) { /* i と j を使ったコード */ }
と書くとコールバックで呼び出された時には変数 i の値は data.length の値になっている。従って
(function(ii, jj) { return function() { /* */ }; })(i,j)
などとして独自に変数を作る必要がある。このイディオム自体は知っていたのだがさらっと書けるレベルには達していなかった。
PAC-MAN
さて、#GDD2010jp TL を席巻した感のある PAC-MAN である。真面目に探索する必要がありそうだったので言語としては C++ を選択。敵の挙動を実装するところまでは特に語ることなし。
LV1 は「現在時刻 + 自機からマンハッタン距離で最短にあるドットまでのマンハッタン距離 + ドット数 - 1」を評価関数とする A* で実装。メンバ関数の定義が全部クラス定義内かよ、とか、関数テーブル使えよ、とか色々とあるところではあるがとりあえず動きゃいいってことで。日頃からこんな糞コードを書いている訳ではない、念のため。で、38 手で game clear になる手を無事見つけられて 41 pt。最短手数のはずなので最高点のはず。
で、試しに LV2 喰わせてみたら当然のごとく bad_alloc が飛ぶ。ここからが結構苦難の道だった。
基本的な方針は「各ドットへの距離を基にした評価関数によって幅を制限した BFS(Breadth-First Search)」である。ある深さでの幅が一定数を超えた場合に評価値をもとに一定数にまで候補を削減して次の段の処理を続ける。なお、敵機の位置は考慮していない。多分、この方針がそもそも失敗だったかな、と思っているがまぁ仕方ない。この基本方針で色々とバリエーションを作成。とりあえず N をドット数、dist[i] を各ドットへの距離(0 ベース、昇順ソート済み)として以下のような感じである。正に苦闘。
- 距離はマンハッタン距離。評価関数を Σ (N-i)*dist[i] とする。重みをかけているのは単純な和だと動いても動かなくても同じ評価値になるため。
- 距離を実際の移動距離に変更。
- あまり遠いものに影響させても意味がないかもということで、N 個全部の和ではなくて指定数を超えたら打ち切り。
- 食べたドットを自分の下にあるとして意図せず計算していた点を修正(したら結果が悪化した)
- 上の評価関数でも残りドット数が一番に効いてくるはずと思ったらそうでもなかったので評価関数を 残りドット数 * 定数 + Σ (N-i)*dist[i] に変更。
- DFS(Depth-First Search) にして経過を見てみる(で、. 連続とかが多発していてあまり評価関数がよろしくなさそうなことが分かる。が、いかんともし難く)
- 評価の良い方から連続に選んでいたものを、5 割は評価の良い方から連続に、4 割を上位 20% から、1 割を残り 80% から乱数で選択するように変更。これでランダム性が入ったので一度結果が出たらまた再度最初からやり直すように変更。
- LV3 用に行き止まり(G と e)の部分のコストを調整。
- 評価値として一つの値にするのではなく、残りドット数、最近傍のドットへの移動距離、前述評価関数の 3 つを順に比較するよう修正。
- ドットを、隣接して繋がっているドットのグループに分割、Σ(グループ中で自機から最近傍にあるドットへの移動距離 + グループのドット数 - 1) を評価関数に。今までの評価関数だと 1 ドットづつ行って戻っての手数を評価していて現実から大分離れているため、グループ単位で考えた方がまだましかもという考えから。
- 最初の動きを与えてそこから探索を継続。シミュレータ(テキスト、かつ画面クリアだけに curses を使うがっかり仕様)で手動でやった結果を与えた。なお、与えた最初の動きは e の中にある行き止まり分のドットを食った状態のもの。G の中の方がシビアな条件なのでそっちを手動でやった方が良かったかもしれないが気合いが足りなかった。手動をいれてしまい正直ちょっと敗北した感はしたものの背に腹は代えられず。
- 交差点、行き止まり以外では止まったり引き返したりせずに突き進むよう変更。
実際には順番に変更を加えていったわけではなく足し引き色々あるが詳細略。LV2 は 3 の状態のコードの結果、LV3 は 12 の状態のコードの結果でそれぞれ 222 点、457 点で最終となった。
感想
普段あまり使わない言語、アルゴリズム、モジュール、ライブラリを使えてなかなか楽しかった。あと手動の方が結果が良かったり人間ってすげぇとも。また、TL でもそんな tweet が流れていたが、実際に動いている所を見る、やってみるっていうのは何かを考える上で重要なことだなというのも痛感した。結果については一応全問回答したわけだし胸を張って良い点とは言えないところだけど悪い点でもないはずなので通るといいなぁ、といったところ。
Google Developer Day 2010 jp DevQuiz 参戦メモ More ログイン