GDD2011 Japan の DevQuiz を解くために書いたコードを公開してみました

観測気球

収集物の記録書庫 a data archive of collection -- collectible toys

[要旨] GDD2011 Japan の DevQuiz、私も参戦してみました。スライドパズルを手動で解こうとした人は、私以外にもいるのでしょうか? (笑)
[キーワード] Google,イベント,DevQuiz,スライドパズル

« 夏コミ(C80)、サークル参加します | トップページ | Google Drive で謎のエラー (Error: 3fa7) »

2011.09.13

GDD2011 Japan の DevQuiz を解くために書いたコードを公開してみました

Google Developer Day 2011 (GDD2011) に参加する権利を獲得するための関門として用意されている DevQuiz、去年(のGDD2010)に引き続き、今年も参加してみました。

去年は応募締め切り後に(パックマンを解くプログラムで)ちょっと恥ずかしい間違い(仕様を180度正反対に誤解したまま実装してしまってた)に気が付いてしまって、結局、ソースコードは公開しなかったんですが(それでも DevQuiz は何とか合格)、今回はちょっとくらい恥ずかしくてもいいやって感じで、ソースコードを公開してみることにしました。

Google Developer Day 2011 Japan の DevQuiz の問題を解くために作成したプログラム群です。

DevQuiz: http://gdd-2011-quiz-japan.appspot.com/

  1. GoogleAppScript

    分野別クイズの1つ

    を解くために、まず、JSON 形式で提供されているデータを入力とし、所定のスプレッドシートの元となる CSV 形式のファイルを出力するプログラムを C で書きました。

    このプログラムが出力した CSV ファイル(都市ごとに1ファイル) を Excel で読み込み(1都市1シート)、各シートの C1 に =B1/A1 という式を埋め込み、C1 を C2 ~ C20 にコピーした後、C列の単位を % にすることで、所定のスプレッドシートを得ました。

    このスプレッドシートを Google Docs にアップロードし、フル Google SpreadSheets 形式に変換することにより、解答が完成します。

  2. hitoriGame

    分野別クイズの1つ

    の問題を標準入力から読み取り、回答を標準出力に吐き出すプログラムを C で書きました。

    以下の戦略で解を求めています。

        [base]
          (a) すべての数が 5 の倍数の場合 → 手数を返す
          (b) すべての数が 5 の倍数ではないものの、5 の倍数が少なくとも1つ以上含まれる場合
              (a1) 5 の倍数をすべて取り除いてみる → 再帰的に [base] を実行
              (a2) すべての数を 2 で割ってみる    → 再帰的に [base] を実行
            上記 (a1) と (a2) のうちの手数が短い方を返す
          (c) 5 の倍数が全く含まれない場合
              (c1) 2 で割ってみる                 → 再帰的に [base] を実行
    
  3. slidePuzzle
  4. チャレンジクイズの

    の出題内容を盤面として再現し、手動で解く GUI プログラムを C♯ で書きました。
    手動で解く方式なので、このまま、プログラム(の実行形式)をパズル好きの人に提供し、パズルを楽しんでもらうことができます。

    実際に解いてみた感想として、簡単な問題なら1分かからずに解けますし、難しい問題でも10分もあれば解けるでしょう。

tsupo/GDD2011Japan_DevQuiz - GitHub

最後の「スライドパズル」は、本来、プログラムに解かせるのが狙いなんでしょうが、一般的な解法もわからないまま、いきなりプログラムは組めません。とりあえず、手動で解くプログラムを書いて、解いているうちに、一般的な解法が閃くのではないか、ということで、アプリケーションを作ってみました。

スライドパズルを手動で解くアプリケーション
スライドパズルを手動で解くアプリケーション

実際に1問目(人によって問題が違う可能性あり)を解いてみた結果が、以下のスクリーンショットになります。

スライドパズル 1問目
スライドパズルの1問目を解いてみた

あともうちょっとで一般解が閃きそうだったのですが、結局、手動で約350問目辺り(途中いくつか時間のかかりそうな問題は飛ばしてます)まで解いたところで、諦めて、回答を提出してしまいました。

いちおう、ボーダーラインの101点は超えてるけど、GDD2011 に参加できるのかどうか、どきどきしています。

投稿者: tsupo 2011.09.13 午前 12:24 | 固定リンク | このエントリーをはてなブックマークに追加 | このエントリを del.icio.us に登録 このエントリの del.icio.us での登録状況 | このエントリを Buzzurl に追加このエントリの Buzzurl での登録状況 | このエントリをlivedoorクリップに登録 このエントリのlivedoorクリップでの登録状況 このエントリをlivedoorクリップに登録している人の数 | 酢鶏巡回中

楽天市場


プログラミング」カテゴリ内の最近の記事

品揃え豊富で安い!NTT-X Store


アマゾンわくわく探検隊

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/6737/52715693

この記事へのトラックバック一覧です: GDD2011 Japan の DevQuiz を解くために書いたコードを公開してみました:

» GDD 2011 Dev Quizに挑戦してみた from 進・日進月歩
Google Developer Quiz 2011に挑戦してみたのでそのまとめをしてみたいと思います。 書いたコードはgithubにアップロードしてあります。 最終結果はこんな感じになりました。 苦戦するとすればチャレンジクイズだと思うので、その方針を簡単に。 チャレンジクイズの内容はいわゆる15パズルを解くという問題です。 ある盤面が与えられた時に、できるだけ短い手数で解くのがポイントになります。 基本的に、次の方針で考えました。$A^*$サーチに近いかもしれない。 短い手が知りたいので、幅優先... 続きを読む

受信: 2011.09.13 午後 09:41

コメント

コメントを書く




※イタズラ防止のため、メールアドレスを入力しないと投稿できません。

次からのコメント入力の手間を省くために、名前やメールアドレスをcookieに記憶しますか?


URL を入力すると、その URL にリンクがはられます。
なお、メールアドレスは公開されません。ご安心ください。


ワード

ニッセン

fujisan.co.jp

楽天市場