Categories

  • Android開発
    android marketで目指せ億万長者(ウソ)
  • cocos2d
    pythonでも使えるゲームフレームワーク
  • Google
    ここには未来を開くためのAPIがたくさん用意されている。
  • GoogleAppEngine
    どこまでもスケールアウトするクラウドサービス。使いこなすのが大変
  • Hack
    様々な電子機器を本来の用途とは別の用途に使ってみる。
  • iPhone開発
    app storeで目指せ億万長者(ウソ)
  • python
    LightWeightLanguageで一番難しいがLispにも通じるところがある面白い言語。
  • TIPS
    覚えておくともしかしたら役に立つかもしれないチョットしたこと。
  • うまくいきません
    やってみたけど、うまくいかなかった失敗記事
  • ネット世界
  • 夢見るソフトウェア
    こんなのいいな、できたらいいな、いつかつくろう
  • 開発環境
    開発するまえに環境を整えた記録、次に同じことをするためめの忘備録
無料ブログはココログ
My Photo

« 本棚をポケットに入れてしまおう | Main | PyPyは素晴らしい »

September 12, 2011

DevQuizに挑戦してみた

 今年のGoogle developer day のQuizはスライドパズルだった。
昔からある15個の数字が書いてあるコマを動かして順番に揃えるアレ、遠足の時にぼっちになったら黙々とやっていたトラウマとかどうでもいい。

普通のパズルと違って、制約事項が2つある。
1.盤面に動かせないコマがある。
2.上下左右に動かせる数は上限がある。上限を超えると失格
問題の数は5000問で1問解くごとに0.01点が与えられる。

1の条件により、一般的な15パズル解法プログラムは使えない。
また、上限があるということは、手数は丁度もしくは足りないため、正解数が最大になる組み合わせを探すことになるだろうと予測した。
これにより、満点ということはなく4900問前後での闘いになるだろうと読んだ。まあ、結果的には予測は大外れだったわけだが。

言語は日頃使っていないpythonを選択。数値演算が得意そうだし、googleに提出するしね。

 作戦は「空」つまり0を上下左右に動かして結果を記録して1手、次に1手で記録した盤面を全て上下左右を調べて記録、これで2手。
pythonのmapを使い、インデックスを盤面とした。検索が超早い。
 が、しかし爆発的に記憶する盤面の数が増えていく。当然、メモリが足りない。そこで、各コマについて本来の位置との距離を求め、合計が大きなものすなわち正解から遠いものを捨てた。
また、結果から逆に問題の方向へ動かすこともやった。
最大手数を100手あたりに設定して、3000問は解けた。手数が多いと何をやってもメモリ不足となる。

9月に入って結果を見ると全問正解者がいらっしゃいます。え~、目論見が外れた。

締め切り前日になって、盤面の大きなパズルは半分ずつとけばいいと気がついた。
急いで実装してみたが、半分でもまだ手数が多すぎる、じゃあ1/4とか1/16でということになるが、時すでに遅し。

計算時間を短くするために、複数のマシンで分散して処理できるようにした。8台で分散させたが、COREi7のマシン1台に負けるんだよね。

満点にはならなかったけど、pythonはプログラムしていて楽しい。他の言語に比べて、コアな部分に専念できるような感じた。
Cythonやpypyは今回試していないが、こういうものがあると知っただけでも今回参加したかいがあった。

以下ソース。ちょっと汚い。

「google-pazzle.py」をダウンロード

ちなみに提出したものの回答数は4620点。このソースではもう少したくさん解ける。

メインプログラムでは、5000問の開始場所と問題数を指定すれば部分的に処理をするので、マシンがたくさんあるときは「1〜100はあなた」というように処理を割り振っていけば分散処理できる。答えは手動で回収しないといけないけどね。
 また、一度解決した問題は2回目は食わないように作ってある。一から再計算したい時は面倒だけど。

« 本棚をポケットに入れてしまおう | Main | PyPyは素晴らしい »

python」カテゴリの記事

Comments

Post a comment

Comments are moderated, and will not appear on this weblog until the author has approved them.

(Not displayed with comment.)

TrackBack


Listed below are links to weblogs that reference DevQuizに挑戦してみた:

« 本棚をポケットに入れてしまおう | Main | PyPyは素晴らしい »