GDD 2010 Japan DevQuiz - y

Google Developer Day 2010 JapanのDevQuizで用いたスクリプトなど。4つともPython。

問題リストに表示されていた得点は以下のとおり。

問題	得点
Google Maps API	1.0, 2.0, 3.0
2-legged OAuth	5.0
Shiritori	1.0, 3.0, 6.0
PAC-MAN	35.0, 171.0, 未挑戦

Google Maps API

スクリプト

GDD2010Japan DevQuiz Google Maps API

itertools.permutaions()を用いて書いた。問題を解くのが目的だったのでエラーハンドリングをきちんとしていない。

入力1

東京駅 35.681382 139.766084
佐渡トキ保護センター 38.038064 138.422468
東京大学 35.712940 139.759590

入力2

三内丸山遺跡 40.811225 140.695649
兼六園 36.562070 136.662419
熊本城 32.804722 130.707835
五稜郭 41.796868 140.756794
襟裳岬 41.926490 143.246642
両国国技館 35.697080 139.792280

入力3

浅草寺 35.714777 139.796728
札幌時計台 43.062603 141.353642
兼六園 36.562070 136.662419
グラバー園 32.734348 129.869148
五条大橋 34.995682 135.767890
東大寺大仏殿 34.689023 135.839880
船の科学館 35.620168 139.772157
鈴鹿サーキット 34.847899 136.540862
両国国技館 35.697080 139.792280
鷲宮神社 36.100240 139.656800

2-legged OAuth

スクリプト

GDD2010Japan DevQuiz 2-legged OAuth

今見返してみると、ソートした後に"hello=world"を連結するところはあまりよろしくない気がする。

Shiritori

スクリプト

GDD2010Japan DevQuiz Shiritori

単語の辞書と既に用いた単語（先頭に"!"をつけて記述）のリストを入力として与え、探索する。

今回のDevQuizで一番面白く感じたのはこの問題である。3問目は与えられた辞書に含まれる単語数が187と多いため、単純な探索では時間がかかる。しかし問題を有向グラフで表現するとグラフの連結の様子が見え、問題を単純化できる。

結論を言うと、自分のターンでi, k, nから始まる単語を選び、相手にb, j, l, p, q, v, w, x, zのいずれか一つから始まる単語を選ばせ、そしてそれを続ければよい。例えば、自分がkcwdtmywxを選ぶことができれば、それ以後のターンで自分はxで終わる単語を選ぶことにより、相手にxで始まる単語を選ばせ続けることができる。

例

……
自分: kcwdtmywx
相手: xmgupwvyu
自分: uuceouqnvx
相手: xiwlnpvnvs
自分: skqnjfx
相手: xiphykcuowd
自分: dhvqrgx
相手: xfysfpl
……

この考えを突き詰めると、最終的にはectjazoからflgnmuktegまでの28単語でしりとりを行うというサブ問題に帰着する。この28単語以外を相手に選ばせることで、自分はi, k, nで始まる単語を選択できる。

1問目と2問目は、敵の動きを模倣した比較的単純な探索を用いて解いた。定められたステップ数で解が見つからないことは多々あるが、ランダムネスを用いているため、複数回実行することでカバーできる。3問目に対しては探索のアルゴリズムを複雑にするよりも手動で解いた方が時間の節約になると考え実装までは行った。しかし実際に解を提出するところまでたどり着けなかった。cursesを用いて実装した方がよりゲームらしくなるとは思うが、今回は問題を解くことが目的だったので、手をつけていない。

入力1

50
11 7
###########
#.V..#..H.#
#.##...##.#
#L#..#..R.#
#.#.###.#.#
#....@....#
###########

入力2

300
20 17
####################
###.....L..........#
###.##.##.##L##.##.#
###.##.##.##.##.##.#
#.L................#
#.##.##.##.##.##.###
#.##.##L##.##.##.###
#.................L#
#.#.#.#J####J#.#.#.#
#L.................#
###.##.##.##.##.##.#
###.##.##R##.##.##.#
#................R.#
#.##.##.##.##R##.###
#.##.##.##.##.##.###
#@....R..........###
####################

入力3

700
58 17
##########################################################
#........................................................#
#.###.#########.###############.########.###.#####.#####.#
#.###.#########.###############.########.###.#####.#####.#
#.....#########....J.............J.......###.............#
#####.###.......#######.#######.########.###.#######.#####
#####.###.#####J#######.#######.########.###.##   ##.#####
#####.###L#####.##   ##L##   ##.##    ##.###.##   ##.#####
#####.###..H###.##   ##.##   ##.########.###.#######J#####
#####.#########.##   ##L##   ##.########.###.###V....#####
#####.#########.#######.#######..........###.#######.#####
#####.#########.#######.#######.########.###.#######.#####
#.....................L.........########..........R......#
#L####.##########.##.##########....##....#########.#####.#
#.####.##########.##.##########.##.##.##.#########.#####.#
#.................##............##..@.##...............R.#
##########################################################