[観] プログラミングバックナンバー

観測気球 » プログラミング

プログラミング -- Hot Topics

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/
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つ

一人ゲーム: http://gdd-2011-quiz-japan.appspot.com/problems?problem=algorithm

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

以下の戦略で解を求めています。
    [base]
      (a) すべての数が 5 の倍数の場合 → 手数を返す
      (b) すべての数が 5 の倍数ではないものの、5 の倍数が少なくとも1つ以上含まれる場合
          (a1) 5 の倍数をすべて取り除いてみる → 再帰的に [base] を実行
          (a2) すべての数を 2 で割ってみる    → 再帰的に [base] を実行
        上記 (a1) と (a2) のうちの手数が短い方を返す
      (c) 5 の倍数が全く含まれない場合
          (c1) 2 で割ってみる                 → 再帰的に [base] を実行
slidePuzzle

チャレンジクイズの

スライドパズル: http://gdd-2011-quiz-japan.appspot.com/problems?problem=slidingpuzzle

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

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

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

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

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

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

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

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

instagram API の概要(速報版)

昨日、instagram の API が使えるようになったという連絡が届いたので、早速、ドキュメントを読んでいるところです。

とりあえず、大雑把にまとめると、以下のような感じ。

API の種類

4種類のAPIで構成される。

read 系
- 写真データ(写真、コメント、いいね)の閲覧
- ユーザーデータ(フォローしている/されているユーザーのリスト)の閲覧
comments 系
- コメントの投稿
- (自分の投稿した)コメントの削除
relationship 系
- 指定ユーザーをフォローする
- 指定ユーザーのフォローをやめる
likes 系
- 指定した写真を「いいね!」する
- 指定した写真の「いいね!」を取り消す

残念ながら、「写真を投稿する」API は非公開のまま(instagram公式アプリケーションのみが使えるAPIという扱い)。

認証

OAuth 2.0 を使う。認証時に使用する「クライアントID」と「クライアントシークレット」は、クライアントアプリケーションの登録時に発行される。

認証の手順として、Webアプリケーション向けのものと、Webサイト設置型のクライアント(クライアント本体はJavaScriptで記述されているものが想定されている)向けのものが用意されている。両者とも、認証成功時のリダイレクト先URLを前もって申請しておく必要がある。「Webサイト設置型のクライアント」というのは、Twitter でいうところの Twitter AnyWhere 的なものだと思われる。

デスクトップクライアントのように「認証成功時のリダイレクト先URL」というのを用意できない/用意するのが難しいアプリケーションや、携帯電話のようにリソースの制限がきつい環境で使うアプリケーション向けに、xauth も用意されている。ただし、なぜ xauth を使う必要があるのかをきっちり説明したメールを送って、使用許可を取る必要がある。

未確認事項

拙作の tumblen3 のように、(ローカルPC上で動く)自前のWebサーバーを内蔵しているクライアント(というかブラウザ)は、ローカルPC内の URL (例えば、127.0.0.1/foo/bar/baz) を「認証成功時のリダイレクト先URL」として申請していいのかどうか。申請が可能なら、「Webサイト設置型のクライアント」の認証手順がそのまま使える。申請不可の場合は、xauth を使うことになる。

追記: ローカルPC内の URL を「認証成功時のリダイレクト先URL」として申請して、うまく動いている、という情報をいただきました。申請できるんですね!