おまぬけ活動日誌

● ある日C言語談義がなんだかすっきりしないので始めてしまったGDD 2011 DevQuiz。いっやー、はまりました。非常に幸せな時間を過ごさせていただきました。出題してくださったみなさん、twitterで進捗をつぶやいてくださったみなさん、どうもありがとう。突破できたとしても横浜は遠いんだけどね。ひとり反省会をしてみたいと思います。

● [DevQuiz2011] ウォームアップクイズ

とりあえず手をつけてみたのはウォームアップクイズ。実はけっこう難しかった。始めたのは9月1日、全部回答できたのは2日でした。

問題に挙げられていたのは、Google Web Font API、maps API、iGoogle、Chrome、gmail。Googleの製品を知ってもらおうという意図は見えるにせよ、今まで避けて通ってきた現代風APIに触ってみる良い機会にはなりました。

gmail。Windowsのクリップボードはどうして余計なものまでペーストしてくれるのかと悩んでいた時に、Ctrl-Shift-Vでプレインテキストのみをペーストしてくれるというありがたい情報。あ、でも、GMailのwwwインターフェースだけでの話でした。残念。

ええ、iGoogleについての回答は結局ダッシュボードまで行ってみましたとも。

● [DevQuiz2011] Web Game

Chrome上に表示される神経衰弱を、Chrome拡張(Javascript)で解く、という問題。 Chrome拡張を使わなず手でカードをクリックしていっても良いので、 子どもたちの格好の遊び相手になってました。

最終的は下記のようなコードで解きました。

カードをめくりつつ色を覚えて知ってる色があれば戻ってクリックします。 原理的にはひととおりめくれば解けてるはずなのに、 手元(x86_64のMomonga Linux 7、Chromium 12.0.742.105 (O))ではそうはならない。 よく見てみると、クリックしたあとに背景色に戻ってしまうカードがありました。 決まった問題の決まったカードなのですが、原因を探すのは大変だったので、 下記のように、 対症療法で済ましちゃいました。

えーと。 同じ色を思いだしてめくったはずの2枚目のカードの色が めくった色になっていた時だけ、 次のカードに進む。

● [DevQuiz2011] Go言語で画像が何色使っているかを返す関数を実装する

好きだなあと思いつつなかなか触れないでいたGo言語。これは楽しみだわい、と思ったのですが、 PNGを読むライブラリ関数から返してくれる色を配列に入れると、 型が違っていて比較できなくなるという残念な結果に。 この辺をちゃんと理解して使いこなせるようになると楽しい言語なんだろうけどなあ。 下記の回答では、 色を覚えておく構造体をつくって愚直にRGBを比較しちゃっています。

● [DevQuiz2011] サービスとして起動されるAndroidアプリと通信する

AIDLが与えられるのでサービスと通信して答えをもらう。

入門書を見ながらアプリを作りました。 これは、まあ、誰が回答しても似たようなコードになるんだろうな。 レイアウトはもうデフォルトのまんまで。

● [DevQuiz2011] Google Apps Script

え？スプレッドシート？日頃苦しめられてるのにまた？パス。

ほんとは日頃苦しめられてるからこそ、自動化したいところなんだけどね。もとがExcelだしね。…というわけで上のスクリーンショットにもあるように回答すらしてませんデスヨ。

● [DevQuiz2011] 一人ゲーム

数列を操作してゴールにたどりつくまでの最小手数を回答するというもの。

スライドパズルに行きづまっていた時に似たような手法(全数探索)であんまりにもすんなり解けてしまったものでした。 Ruby万歳♪

Gameクラスで問題を実装して、Solverクラスがそれを解いてます。 next_stepメソッドで与えられた問題をコピーして、 可能な二種類の操作をそれぞれやってみて、 操作できた(操作の結果数列に変化があった)なら、 次の操作に進む(next_stepメソッドを再帰呼び出しする)というもの。 問題が解けた時点で、手数を記録して一気に呼び出し元に戻ります。

● [DevQuiz2011] スライドパズル

勉強不足を思い知った問題。 盤面の様子を記録しながら深さ優先探索でパネル12枚程度まで 570問をなんとかかんとか解きました。 締め切り後の回答晒しでは、 幅優先検索で回答を作った方々がたくさん回答を得ていたみたい。 場合の数が爆発するなか、最小の手数を求めるには、もちろん幅優先検索の方が良いわけで、 締め切り後の回答晒しでは、 幅優先検索で 回答を作った方々がたくさん回答を得ていたみたい。 場合の数が爆発するなか、最小の手数を求めるには、 もちろん幅優先検索の方が良いわけで、 A*検索? と一緒に勉強して実装してみたいと思いました。

スライドパズルは1手ごとに空白を4方向に動かす可能性があるので、 全数探索すると訪問するべき場合の数は手数をnとして だいたい4ⁿとなります。 さらに盤面の状態を記録するとすると、パネルの数をnとしてn!の状態が あらわれる。 ポイントはいかにこれを回避するか、 というところにあのだろうと思って始めたコーディング。

最初は、ヒューリスティックに、1から順番にパネルを詰めていこうとしたのですが、 6問解いたところでコードの複雑さに挫折しました。 その後、全数検索に切りかえて、少ないながらも手持ちの物量を使う方向に。 盤面の状態を記録しつつ再帰的に深さ優先探索。 盤面の記録を線形リストからハッシュテーブルに切り替えて、 速さに感動したりもしました。 この時解けたのは98問。 手数のかからない問題も深く検索しちゃうのは手数リミットを 順次変えていけばいいんだろうな、などと思っていたところに、 zakiさんから 「IDDFS」というありがたいキーワードをいただきました。 なるほどそう呼ぶのか！ 計算機科学をちゃんと勉強しておくと、 ぼんやり思いついた概念にちゃんと名前を付けられるんですよね。

というわけで最初浅い探索から始めるコードにして何日か走らせた結果、 570問。 最初はファイルをDropboxに管理してもらいながら作業してたのですが、 簡単にdiffを取る方法を見つけられなくて、 このあたりからさらにgit initをするようになりました。 最初からやっておけばよかった。

まだまだ遅いなあ、というところで再帰していたコードをどうにかこうにか開いて、 本質的ではなかった移動経路の記録もやめ、すべて盤面に記録するようにしたのが 最終的に回答をつくったコードでした。

game_sというオブジェクにスタート、ゴール、訪れた盤面の管理をしてもらいつつ、 可能な手を試していってもらいます。 訪れられる盤面がなくなるまでこれを繰り返す。 訪れた盤面の管理は ハッシュテーブルにやってもらいます。 同じハッシュになった盤面は線形リストにどんどんぶらさがります。 このコードはなかなか解を見つけられない場合は LiunxのOOM Killerに殺してもらって諦めることになってしまっていました。 スワップを無効にしておくのが重要です。 たぶんメモリをどんどん食べてたのはこの部分。 ハッシュ関数自体は悪いものではなかったと思っています[要検証]。 それぞれの移動が有効かどうかは、ハッシュテーブルに記録されていくことになる board_sというオブジェクトに 判断してもらっていました。 有効なら次に進む、 無効なら戻る。 進んだら、 ゴールに着いたか確かめ、 着いてなければ 残りの手数え着けるか確かめ、 着けそうなら、また次の手を試す。 このコード自体は1問につき1プロセスとして走り、 5000問の問題から解くものを決めれプロセスを起動する仕事は Rubyのスクリプトにお願いしました。 同時に起動するプロセス数は昔作った ruby-nforkというライブラリで管理しつつ、 Drubyで同時起動数を変化させたり最大手数を変化させたりできます。

このコードで問題を解きはじめたのは9月10日9:44HSTごろ、 締め切りの前に最後に570個目の回答が得られたのが、9月11日12:52HSTでした。 Xeon 3GHzの4つのコア、4GBほどの物理メモリで、 パネル数の少ない問題から、1時間あたり20問ほどの回答が得られたことになりますね。

あ、この記事で参照されているコードには著作権表示がありません。 再利用される際は、このページに掲載されているコードと同じく、 下記の表示とライセンスの適用をお願いします。

Copyright 2011 zunda <zunda at freeshell.org>

Permission is granted for use, copying, modification, distribution, and distribution of modified versions of this work as long as the above copyright notice is included.

● [DevQuiz2011] このページに掲載されているコードの利用許諾

(追記) 需要があるかどうかは別として、コードのためにも、利用許諾をはっきりさせました。

● 最後になりましたが、いろいろなコードや技術と戯れる幸せな数日間でした。問題を提供してくださったGoogleの皆さん、twitterで悩みと楽しみを共有してくれたみなさん、どうもありがとう！これからもがんばるる！