« 夏コミ(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/
tsupo/GDD2011Japan_DevQuiz - GitHub
- GoogleAppScript
分野別クイズの1つ
- Google Apps Script: http://gdd-2011-quiz-japan.appspot.com/problems?problem=apps_script
を解くために、まず、JSON 形式で提供されているデータを入力とし、所定のスプレッドシートの元となる CSV 形式のファイルを出力するプログラムを C で書きました。
このプログラムが出力した CSV ファイル(都市ごとに1ファイル) を Excel で読み込み(1都市1シート)、各シートの C1 に =B1/A1 という式を埋め込み、C1 を C2 ~ C20 にコピーした後、C列の単位を % にすることで、所定のスプレッドシートを得ました。
このスプレッドシートを Google Docs にアップロードし、フル Google SpreadSheets 形式に変換することにより、解答が完成します。
- hitoriGame
分野別クイズの1つ
の問題を標準入力から読み取り、回答を標準出力に吐き出すプログラムを C で書きました。
以下の戦略で解を求めています。
[base] (a) すべての数が 5 の倍数の場合 → 手数を返す (b) すべての数が 5 の倍数ではないものの、5 の倍数が少なくとも1つ以上含まれる場合 (a1) 5 の倍数をすべて取り除いてみる → 再帰的に [base] を実行 (a2) すべての数を 2 で割ってみる → 再帰的に [base] を実行 上記 (a1) と (a2) のうちの手数が短い方を返す (c) 5 の倍数が全く含まれない場合 (c1) 2 で割ってみる → 再帰的に [base] を実行- slidePuzzle
チャレンジクイズの
の出題内容を盤面として再現し、手動で解く GUI プログラムを C♯ で書きました。
手動で解く方式なので、このまま、プログラム(の実行形式)をパズル好きの人に提供し、パズルを楽しんでもらうことができます。実際に解いてみた感想として、簡単な問題なら1分かからずに解けますし、難しい問題でも10分もあれば解けるでしょう。
最後の「スライドパズル」は、本来、プログラムに解かせるのが狙いなんでしょうが、一般的な解法もわからないまま、いきなりプログラムは組めません。とりあえず、手動で解くプログラムを書いて、解いているうちに、一般的な解法が閃くのではないか、ということで、アプリケーションを作ってみました。
実際に1問目(人によって問題が違う可能性あり)を解いてみた結果が、以下のスクリーンショットになります。
あともうちょっとで一般解が閃きそうだったのですが、結局、手動で約350問目辺り(途中いくつか時間のかかりそうな問題は飛ばしてます)まで解いたところで、諦めて、回答を提出してしまいました。
いちおう、ボーダーラインの101点は超えてるけど、GDD2011 に参加できるのかどうか、どきどきしています。
投稿者: tsupo 2011.09.13 午前 12:24
| 固定リンク
|
|
|
|
|
アマゾンわくわく探検隊
トラックバック
この記事のトラックバックURL:
この記事へのトラックバック一覧です: GDD2011 Japan の DevQuiz を解くために書いたコードを公開してみました:
» GDD 2011 Dev Quizに挑戦してみた from 進・日進月歩
Google Developer Quiz 2011に挑戦してみたのでそのまとめをしてみたいと思います。 書いたコードはgithubにアップロードしてあります。 最終結果はこんな感じになりました。 苦戦するとすればチャレンジクイズだと思うので、その方針を簡単に。 チャレンジクイズの内容はいわゆる15パズルを解くという問題です。 ある盤面が与えられた時に、できるだけ短い手数で解くのがポイントになります。 基本的に、次の方針で考えました。$A^*$サーチに近いかもしれない。 短い手が知りたいので、幅優先... 続きを読む