Google Dev Quizが終わって
2011-09-13 07:01
というわけでGoogle Dev Quizが終わったわけだ。
前にも書いたが、より詳細に自分が何をしたかを書いておく。
ウォームアップクイズ：Tweetを参照すると人によって表示される問題が違うのだそうな。少しググレばでてくる問題ばかりだたったので１０分くらいで終了。
分野別クイズ：
これはまず「何を解くか」について悩む。
Web Game:Chrome Extensionについて勉強しましょう
Go! : Go言語について勉強しましょう。
Android:Androidで何かを動かしてみましょう。
Google Apps Script: Scriptを勉強しましょう。
一人ゲーム：これはアルゴリズムだな
というわけで、この機会に新しいものを勉強しよう、と思う。Androidにまずとりくむが、問題文を読んで絶望する。
以下の AIDL で定義されるサービスを持つ Android アプリケーションを配布します。インターフェースを利用し、解答コードを手に入れてください。
AIDLって何？書いいとうコードを手に入れるって何？添付されているAIDLとやらをみて
「きっとAndroidアプリ間のインタフェースを規定したものに違いない」
と思い込む。あれこれ調べる。ああ、Google検索って素敵。MacにAndroidの開発環境を詰め込んで、動かして、、とやったらなぜかエミュレータが立ち上がらない。別のMacではすんなり動いたのでそちらで作業。
要領が分かってしまえば話は簡単でした。画面に表示されたコードを打ち込むと、点数が加算される。これでほっと一息。
次にGo!にトライ。pngの色数を調べるコードを書け、とのこと。
そうか。これはきっとpngのフォーマットを解析して、Decodeで、、、といきなりpngについて調べだす。
これは一筋縄ではいかない、とGo言語の仕様を見ればpngのDecodeが標準でついてるじゃん。何をやっているんだか。息子が筆算の試験で「引き算なのに、足し算と思い込んで不正解」というのをよくやっている。「ちゃんと問題を読みなさい」と言っていたのだが、他人に説教たれている場合じゃない。
というわけで書き始めるが。。パッケージ読み込みとpngのdecodeのところで何故か躓く。Quiz終了後他の人がアップロードした正解を見ると大筋あって行ったようなのだが、なぜかコンパイルが通らない。こういう時にマイナーな言語はGoolge先生の教えをうけられなくて困る。おまけにGoというのは検索語としてあまり適当ではない。もっと変な名前にしてくれればよかったものを。
というわけでGoは諦め、Web Gameに切り替え。
これは神経衰弱。最初の一面は手でも解けるがきっとそのうちものすごい数のカードがでてくるのだ。
しかしそもそもChrome Extensionってどうやるの、というとこからスタート。一番肝になるコードは与えられているので、Hello Worldが表示出来れば話は簡単である。
動かすと、どんどんページが進む。そのうちカード枚数が1024というページにつきあたる。さすがに時間がかかる。数分かかったかな？
そんなページが何枚も続く。朝出かける前に動かし始めたので、そろそろ出発の時間が気になる。そもそも総当りはあまりにも芸がない。既に裏返したカードはスキップするように改造しようか。いや、もう少しで終わる、いや時間がない。
しょうがない、と改造を決意したところで全部のゲームを解き終わった。これで１００点獲得。
----
この時点ではまだボーダーラインが７０点くらいだったような気がする。しかしそこから１００点までの間にはあまり人がいない。つまり遠からずボーダーラインが１００点を超えるに違いない。というわけでスライドパズルに取り組まざるを得ないわけか。。
スライドパズルとは、いわゆる１５ゲームのように、ボードをスライドさせて順番を揃えるものである。ひねりが二つあり
・動かせない「壁」が存在している
・各手順（左、右、等）の総数が決まっている
さて、どうするか。
まずGoogle先生にお伺いをたてるのはいつものこと。すると「幅優先ではメモリがたらなくなります」とでてくる。そうだよなあ。きっとすぐ爆発するに違いない。
というわけであれこれ探し続ける。するとA*なるアルゴリズムがあることを知る。懐かしいOperations Researchで習ったような内容だ。深く考えずこれで行こうと決める。
このアルゴリズムでは、各状態の「ゴールへの距離」を定義する必要がある。最初は単に「各ボードが最終位置からどれくらいズレているか」で計算していたが、そのうち壁の存在を考慮する方法に切り替える。
動かしてみると、まず最初の問題がいつまでたっても終わらない。１０分くらいは動かしていただろうか？各状態の「ゴールまでの距離」を表示させるのだが、さっぱり収束している気配がない。
これはいかん。そもそも問題は５０００問もあるのだ。こんな調子では前に進まない。というわけで時間制限をもうけ、数日動かせば５０００問チャレンジできるようにする。会社のマシンにこっそりと忍び込ませ動かし続ける。
とかやって得点は5.9になった。つまり５９０問解けたわけだ。Twitterを見ると
「４０００問解けた。」
とか
「ゴール」
とか景気のよい言葉が飛び交っている。実力差を感じるなあ。しかしこれ以上このクイズに時間を費やすことはできない。そこで打ち止めにする。得点分布を見ると１００点台の棒がものすごく長くなっている。他の問題は全部解けたが、このスライドパズルで止まっている人が多いのだろう。１００点台の詳細ヒストグラムなど見せてもらえないかなあ。
------------
終了後Tweetをみると、幅優先＋枝刈りでも４０００問解けたという人が多い。そうかあ。 幅優先でも結構できたのだな、と思うが後の祭りである。興味深いコメントをいくつか。
スライドパズルの探索アルゴリズムは早々に諦めて、左上から縦横潰すパズル解きを実装。壁なし約1200問のみ倒す情けない作戦だけど、回答に20秒もかからないから地球には優しかったはず(笑)
via: twitter ツイッター検索 from:superrush4x
ううむ。そういう手もあったか。
手法は結果的に焼きなまし風味を加えたA*。本当の両側A*じゃなくて、最初にゴールからある程度を完全BFSしてゴールそのものを広げる感じ。
via: Kohsuke Yatoh (kohyatoh) は Twitter を利用しています
この人は、私が前働いていた会社のスーパーインターンです。私は採用で面接などさせてもらったわけだが、この実力差はどういうことであろう。どうもゴールからもある程度探索するのが良い方法だったのだろうか。
あとAndroidの問題を解くのに、配布されていた「別のアプリ」のソースを見て、エミュレータすら立ち上げないで解いた人もいるとのこと。
これだけたくさんの人がトライする問題だと思いも寄らない「解法」があって面白い。
ちなみに一番笑ったTweet
「3*3がやられたようだな」「ククク...3*3は我らスライドパズルの中でも最弱...」「総当たりに負けるとは、パズルの面汚しよ」
via: @Ryu_Project's (りゅう) recent tweets
3*3くらいまでは総当りでも解けるのだけど、少しボードが大きくなると急に難しくなるというのが体感できた。
-----
さてボーダーラインは１０１点前後とのことだが、１０５．９点の私は参加できるでしょうか？でもあれだよね。参加賞に「総得点」とか書いてあったら泣いちゃうよね。