Google Developer Day 2011 に参加してきました。(基調講演編)

先日のDevQuizの結果、運良くGoogle Developer Day 2011の参加証を手に入れることが出来ましたので、Googleの最新技術に触れるべく参加してきました。

パシフィコ横浜での開催ということで、当日は新幹線を使って新横浜まで行き、そこで乗り換えて桜木町まで向かいました。
途中2度ほど道に迷いましたが、なんか見覚えのある場所だった(見覚えのある観覧車とか赤レンガ倉庫とか・・・)事もあり、無事にパシフィコ横浜まで辿り着くことができました。

開場20分前位に到着したのですが、色々あって何故か受付に並ぶ何列かの中の先頭に並んでしまいました・・・その結果、受付はスムーズに進み、そのまま基調講演の会場へと誘導されていきました。

その誘導の途中で、Tシャツ、記念品(Zeemote JS1 H)、缶バッチ等々を受け取り、メインホールに入り基調講演の開始を待ちました。
このとき表示されていた残り時間の表示が非常に凝っていて、二進数のビットでも残り時間を表していたのが印象的でした。(というか、この会場に来るような人は、普通の時間表示は不要でビットだけ並べておけば誰もが理解できたんじゃないかと思ったのは内緒です。)

基調講演開始前

そして基調講演が始まりました。
全体的にはAndroid 4.0(ICS)とHTML5が今後の主流になっていくという感じの内容で、魅力的なデモを沢山見せ付けられました。

また、その中で発表された格言があり、

なにごともエンジニアありき
「なにごともエンジニアありき」

百聞は一デモに如かず
「百聞は一デモに如かず」

日本でイケると思ったら
「日本で「イケる!」と思ったら、世界のみんなも同感するかも」

この言葉が凄く印象的でした。

特に「なにごともエンジニアありき」については、ここ最近よく感じる違和感に対しての良い回答だなという感じでした。もっとプログラマーの立場というのは向上しても良いハズなんですよね・・・

という感じで基調講演は終了。

入場が早かったせいで、メインホールの前の方に座っていた為、退場には時間が掛かってしまい、Googleが用意してくれたお弁当を受け取るまでに時間が掛かってしまった時は、「あぁ焦らずに入場すれば良かった」と少し後悔をしながら午後のセッションに向けて準備を進めていました。

ということで、午後のセッションについては次回以降のブログで・・・

Posted in イベント | Leave a comment

DevQuizのソースコード(スライドパズル編)

DevQuiz最後の難関となったスライドパズルです。

最終的にはスライドパズルの点数(0点~50点)がGoogle Developer Dayへの参加権のボーダーとなりました。(公表されているボーダーラインは101点なので、スライドパズル以外ではほぼ100点が取れていると思いますので、スライドパズルで少なくとも1点を取る必要があったと言えます。)

出題されるパズルの数は5000問、1問あたりの点数が0.01点。(最大で50点満点)
スライドパズルの盤面は縦横3~6の組み合わせで構成されており、特殊ルールとして「壁」と呼ばれる動かせないピースが存在します。また、ピースを移動する手数が制限されています。
問題文はテキストファイルで与えられ、結果は空ピースを動かした方向の上下左右をUDRLの文字に当てはめて問題番号と同じ行数のテキストファイルに出力して提出します。

私の結果は4126/5000問の回答で、回答できた部分については間違いは無しでした。(回答した行数と得点が一致していました。)

手数制限にはまだまだ余裕がありましたが、ロジックが悪かった為、6×6の盤面では回答を得るのに1日も掛かってしまうことがありました。

よって、この得点は単純にタイムオーバーとなってしまった時点での得点となります。

使用したマシンはCore i3 2100のPCで、C++で作ったEXEファイルを実行したところ2コア2スレッドの1プロセス分しか使ってくれず、CPU使用率は25%で張り付いたままでした。
(EXEファイルを全てのパワーを使い切って実行する方法があったら教えてください・・・)

既に満点を取られた方が回答PGを公開していますので、私のPGは参考になりませんが、ここで恥をさらしておけば次回のやる気に繋がるということで公開したいと思います。

//————————————————————–
// puzzule(スライドパズルの最短解を求める/本当のスペルはpuzzle)
//————————————————————–
// GDD/DevQuizのスライドパズル回答PG
//
// [UPDATE]:テキストファイルで与えられた問題を解析し盤配列に設定
// [UPDATE]:盤の大きさに連動した処理の変更
// [UPDATE]:壁判定の追加
// [UPDATE]:タイムアウトの追加
//————————————————————–
#include
#include
#include
using namespace std;
#define LIMIT 65 // 1問題あたりの最大手数の設定

// パズル構造体の定義
struct Puzzle{ char cont[36]; int space; };

// グローバルエリア定義
Puzzle puzzle;
int limit, path[LIMIT], MD[36][36];

// 壁情報の格納
// 盤の壁位置に0x40(@)が格納される。それ以外は0x00(null)が格納される
char kabe[36];

// 上下左右の移動定義
static const int dx[4] = {-1, 0, 1, 0};
static const int dy[4] = {0, -1, 0, 1};
static const char direction[4] = {‘U’, ‘L’, ‘D’, ‘R’};

// 現在回答中の盤の大きさ
int width = 0;
int height = 0;

// 残り手数格納
int CONTROL[4];

// タイムアウト設定
#define TIMEOUT 600 // 10分でタイムアウト設定
time_t start_time; // 問題処理開始時間
time_t now_time; // 現在の時間

//————————————————————–
// getHeuristic
//————————————————————–
// 現在位置からの総手数を算出
//
// 引数:Nothing
// 戻値:現在位置から回答までの最短総手数
//————————————————————–
int getHeuristic()
{
int sum = 0;
for ( int i = 0; i < (width * height); i++ ) { if ( puzzle.cont[i] == 'z' ) { continue; } sum += MD[i][puzzle.cont[i]-'A']; } return sum; } //-------------------------------------------------------------- // isTarget //-------------------------------------------------------------- // 完了チェック // // 引数:Nothing // 戻値:盤が完成したか否かのチェックを行う //-------------------------------------------------------------- bool isTarget() { // 盤を先頭からチェックし連続した文字コードで並んでいることをチェックする for ( int i = 0; i < ((width * height) - 1); i++ ) { // 文字コードが連続していなければ盤は完成していないと判断 if ( puzzle.cont[i] != 'A' + i ) { return false; } } // ループが最後まで回れば盤が完成していると判断 return true; } //-------------------------------------------------------------- // dfs //-------------------------------------------------------------- // 評価関数 // // 引数:深度,直前の手 // 戻値:上下左右へ動ける可能性のある位置へピースを移動させる //-------------------------------------------------------------- bool dfs(int depth, int prev) { // 盤完成チェック if ( isTarget() ) { return true; } // タイムアウトチェック time(&now_time); if ((start_time + TIMEOUT) < now_time){ return false;} // 最大手数チェック if ( depth + getHeuristic() > limit )
{
return false;
}

// ピースの移動
int px, py, tx, ty;
Puzzle tmp;

// 動かせるピースの現在位置の取得
px = puzzle.space / width;
py = puzzle.space % width;

// 上・左・下・右への移動(それぞれがrの0・1・2・3と合致する)
for ( int r = 0; r < 4; r++ ) { // 移動 tx = px + dx[r]; ty = py + dy[r]; // 直前の手を比較 if ( max(prev, r)-min(prev, r) == 2 ) { continue; } // 枠外に出る場合は動かさない if ( tx < 0 || ty < 0 || tx >= height || ty >= width )
{
continue;
}

// 壁判断
if (kabe[tx*width+ty] == 0x40)
{
continue;
}

tmp = puzzle;

// ピースの移動
puzzle.cont[px*width+py] = puzzle.cont[tx*width+ty];
puzzle.cont[tx*width+ty] = ‘z’;
puzzle.space = tx*width+ty;

// 評価関数呼び出し
if ( dfs( depth+1, r ) )
{
path[depth] = r;
return true;
}
puzzle = tmp;
}

return false;
}

//————————————————————–
// solve
//————————————————————–
// 回答算出処理
//
// 引数:Nothing
// 戻値:Nothing
//————————————————————–
void solve()
{
// 最大手数までのチェック処理を行う
for ( limit = getHeuristic(); limit <= LIMIT; limit += 2 ){ if ( dfs(0, -100) ) { for ( int i = 0; i < limit; i++ ) cout << direction[path[i]]; cout << endl; return; } } // 結果が求められなかった場合は空行を表示する cout << "" << endl; } //-------------------------------------------------------------- // main //-------------------------------------------------------------- // エントリーポイント // // 引数:Nothing // 戻値:Nothing //-------------------------------------------------------------- void main(void) { // 結果ファイルの書き出し // リダイレクト出力で対応するためコメント化 /* FILE *answers_fp; if ((answers_fp = fopen("./answers.txt", "w")) == NULL) { return; } */ // 問題ファイルの読み込み変数の定義 FILE *prolems_fp; char problem[256]; // 盤サイズ格納領域([0]に横幅/[1]にカンマ/[2]に縦幅が格納される) char problem_size[4]; // 問題ファイルの読み込み if ((prolems_fp = fopen("./problems.txt", "r")) == NULL) { // 読み込み失敗時は終了 return; } // 問題を1行ずつ読み込み開始 int problem_cnt = 0; while (fgets(problem, 256, prolems_fp) != NULL) { // 問題読込数インクリメント problem_cnt++; int control_cnt = 0; // 最初の2行(総手数・問題数)の取得処理 switch(problem_cnt) { case 1: // 総手数 // スペース区切りの数字を取得する char temp_cnt[10]; char temp_temp[2]; memset(temp_cnt, 0x00 ,sizeof(temp_cnt)); // 空白区切りの総手数の取得 for (unsigned int cnt = 0 ; cnt < strlen(problem) ; cnt++ ) { if (problem[cnt] == ' ') { control_cnt++; CONTROL[control_cnt - 1] = atoi(temp_cnt); memset(temp_cnt, 0x00 ,sizeof(temp_cnt)); continue; } temp_temp[0] = problem[cnt]; temp_temp[1] = 0x00; strcat(temp_cnt, temp_temp); } CONTROL[3] = atoi(temp_cnt); // 取得した総手数の表示(リダイレクトでの出力を行う為コメントアウト) // printf("残手数 左:%d 右:%d 上:%d 下:%d\n", CONTROL[0], CONTROL[1], CONTROL[2], CONTROL[3]); continue; case 2: // 問題数 // なにもしない(現状は問題文のある限り読み込んで回答を出力している為/必要であればこの回数分だけループする処理に変更する必要あり) continue; } // 先頭3文字から問題サイズの取得 for (int cnt = 0 ; cnt < 3 ; cnt++) { problem_size[cnt] = problem[cnt]; } problem_size[3] = 0x00; width = problem_size[0] - '0'; height = problem_size[2] - '0'; // 壁情報の取得 memset(kabe ,0x00 , sizeof(kabe)); // ボードに数値を格納していく memset(puzzle.cont, 0x00 ,sizeof(puzzle.cont)); for (int cnt = 4 ; problem[cnt] != 0x00 ; cnt++) { char num = 0; // 問題の数値・英字情報を計算しやすいように文字コードに置き換える // (とりあえず小文字のzまでの大きさの盤に対応させる) if (problem[cnt] == '0'){ num = 'z'; puzzle.space = cnt - 4;} // 空白ピース if (problem[cnt] == '1'){ num = 'A'; } // 1ピース if (problem[cnt] == '2'){ num = 'B'; } // 2ピース if (problem[cnt] == '3'){ num = 'C'; } // 3ピース if (problem[cnt] == '4'){ num = 'D'; } // 4ピース if (problem[cnt] == '5'){ num = 'E'; } // 5ピース if (problem[cnt] == '6'){ num = 'F'; } // 6ピース if (problem[cnt] == '7'){ num = 'G'; } // 7ピース if (problem[cnt] == '8'){ num = 'H'; } // 8ピース if (problem[cnt] == '9'){ num = 'I'; } // 9ピース if (problem[cnt] == 'A'){ num = 'J'; } // Aピース if (problem[cnt] == 'B'){ num = 'K'; } // Bピース if (problem[cnt] == 'C'){ num = 'L'; } // Cピース if (problem[cnt] == 'D'){ num = 'M'; } // Dピース if (problem[cnt] == 'E'){ num = 'N'; } // Eピース if (problem[cnt] == 'F'){ num = 'O'; } // Fピース if (problem[cnt] == 'G'){ num = 'P'; } // Gピース if (problem[cnt] == 'H'){ num = 'Q'; } // Hピース if (problem[cnt] == 'I'){ num = 'R'; } // Iピース if (problem[cnt] == 'J'){ num = 'S'; } // Jピース if (problem[cnt] == 'K'){ num = 'T'; } // Kピース if (problem[cnt] == 'L'){ num = 'U'; } // Lピース if (problem[cnt] == 'M'){ num = 'V'; } // Mピース if (problem[cnt] == 'N'){ num = 'W'; } // Nピース if (problem[cnt] == 'O'){ num = 'X'; } // Oピース if (problem[cnt] == 'P'){ num = 'Y'; } // Pピース if (problem[cnt] == 'Q'){ num = 'Z'; } // Qピース if (problem[cnt] == 'R'){ num = 0x5b; } // Rピース if (problem[cnt] == 'S'){ num = 0x5c; } // Sピース if (problem[cnt] == 'T'){ num = 0x5d; } // Tピース if (problem[cnt] == 'U'){ num = 0x5e; } // Uピース if (problem[cnt] == 'V'){ num = 0x5f; } // Vピース if (problem[cnt] == 'W'){ num = 0x60; } // Wピース if (problem[cnt] == 'X'){ num = 'a'; } // Xピース if (problem[cnt] == 'Y'){ num = 'b'; } // Yピース if (problem[cnt] == 'Z'){ num = 'c'; } // Zピース // 壁判定 if (problem[cnt] == '=') { // 壁の位置に本来設置されるべき文字コードを設定 num = 'A' + cnt - 4; // 壁判定に壁情報の格納 kabe[cnt - 4] = 0x40; } // 値の代入 puzzle.cont[cnt - 4] = num; } // テーブルサイズから移動ピースからの移動距離一覧を算出する for ( int i = 0; i < (width * height); i++ ){ for ( int j = 0; j < (width * height); j++ ){ // 正方形テーブルの手数一覧 MD[i][j] = abs(i/width-j/width) + abs(i%width-j%width); } } // 盤番号の表示(リダイレクト表示に邪魔な為コメントアウト) // printf("%d問目\n",(problem_cnt - 2)); // 問題開始時間の取得 time(&start_time); // 解を求める solve(); // 回答出力(リダイレクトでの出力を行う為コメントアウト) //printf("%s\n", ANSWER); //printf("残手数 左:%d 右:%d 上:%d 下:%d\n", CONTROL[0], CONTROL[1], CONTROL[2], CONTROL[3]); //fprintf(answers_fp, "%s\n", ANSWER); } fclose(prolems_fp); // fclose(answers_fp); // リダイレクトでの出力を行う為コメントアウト } [/cpp] 結果ファイルの書き出し処理が面倒だった為、リダイレクトで結果を吐き出すという手段にでました。 なぜか文字コードで盤面の正解を導いていますが、数値を入れた方が良かったなぁ・・という感じです。 なお、正解確認用にPHPで確認PGも製作しました。 [php]



puzzle


stage




[/php]

twitterで見かけたコメントに「日本の電力消費量を押し上げたDevQuizのスライドパズル」というものがありましたが、まさにうちの電力消費量も上がった事でしょう。。。
でも、私の場合はロジックが悪い=処理が遅い=電力消費が高い・・・という原因なので、節電の為にはロジックを良くするという手段もあるんだなぁ・・・と思ったり思わなかったり。

ということで、今回でDevQuizのソースコード晒しは終了です。

DevQuizに参加された皆様、本当にお疲れ様でした。

Posted in プログラム | Leave a comment

DevQuizのソースコード(Android編)

DevQuizの分野別クイズAndroid編は、AIDLに関連する問題でした。
Googleが提供しているアプリをAndroid端末にインストールし、そのアプリの中の指定された命令を呼び出して結果を表示する自作アプリを作るというAIDLの基本的な動作を確認する為の問題設定になっており、これを比較的簡単な問題だったように思えます。

とは言っても、この問題をやるまでAIDLを知らなかったんですが・・・

早速問題を読んでみると、Google側から提供されているのはアプリと以下のソースコードの一部だけでした。

package com.google.android.apps.gddquiz;
interface IQuizService {
    String getCode();
}

問題として、このようなソースが提供されているということは、こちらが作成しなければならないアプリにも、この部分は絶対使わなければならないんだな・・・と思いながら早速アプリを作りました。

/res/layout/main.xml

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:orientation="vertical"
    android:layout_width="fill_parent"
    android:layout_height="fill_parent"
    >
    <TextView android:text="TextView" android:id="@+id/textView1" android:layout_width="wrap_content" android:layout_height="wrap_content"></TextView>
    <Button android:text="Button" android:id="@+id/button1" android:layout_width="wrap_content" android:layout_height="wrap_content"></Button>
</LinearLayout>

/src/SampleAIDLActivity.java(パッケージディレクトリは省略)

package jp.futuresoftware.sample50;

import com.google.android.apps.gddquiz.IQuizService;

import android.app.Activity;
import android.content.ComponentName;
import android.content.Intent;
import android.content.ServiceConnection;
import android.os.Bundle;
import android.os.IBinder;
import android.os.RemoteException;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.TextView;

public class SampleAIDLActivity extends Activity {
	
	private IQuizService quizService;
	
	private TextView textView1;
	private Button button1;

	   private ServiceConnection quizServiceConn = new ServiceConnection()
	   {
			@Override
			public void onServiceConnected(ComponentName name, IBinder service)
			{
				quizService = IQuizService.Stub.asInterface(service);
			}
			
			@Override
			public void onServiceDisconnected(ComponentName name)
			{
				quizService = null;
			}
	   };

	   /** Called when the activity is first created. */
	   @Override
	   public void onCreate(Bundle savedInstanceState) {
		   super.onCreate(savedInstanceState);
		   setContentView(R.layout.main);
    
		   Intent intent = new Intent(IQuizService.class.getName());
		   bindService(intent, quizServiceConn, BIND_AUTO_CREATE);

		   textView1 = (TextView)findViewById(R.id.textView1);
		   button1 = (Button)findViewById(R.id.button1);
        
		   button1.setOnClickListener(new OnClickListener(){
			   @Override
			   public void onClick(View v)
			   {
				   Intent intent = new Intent(IQuizService.class.getName());
				   bindService(intent, quizServiceConn, BIND_AUTO_CREATE);
				   
				   try
				   {
					   textView1.setText(quizService.getCode());
				   }
				   catch(RemoteException exp)
				   {
					   exp.printStackTrace();
					   textView1.setText(exp.getMessage());
				   }
				   catch(Exception exp)
				   {
					   exp.printStackTrace();
					   textView1.setText(exp.getMessage());
				   }
			   }
		   });
	   }

	   @Override
	   protected void onDestroy() {
		   super.onDestroy();
		   unbindService(quizServiceConn);
	   }
}

/src/IQuizService.aidl(パッケージディレクトリは省略)

package com.google.android.apps.gddquiz;

interface IQuizService {
    String getCode();
}

/AndroidManifest.xml

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
      package="jp.futuresoftware.sample50"
      android:versionCode="1"
      android:versionName="1.0">
    <uses-sdk android:minSdkVersion="8" />

    <application android:icon="@drawable/icon" android:label="@string/app_name">
        <activity android:name=".SampleAIDLActivity"
                  android:label="@string/app_name">
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />
                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
        
        <service android:name="IQuizService">
            <intent-filter>
                <action android:name="com.google.android.apps.gddquiz.IQuizService"></action>
            </intent-filter>
        </service>

    </application>
</manifest>

普段からAndroidアプリの開発をしていますが、AIDLを知らなかった自分が残念・・・

Posted in プログラム | Leave a comment

DevQuizのソースコード(Go!編)

初めて触ったGo言語ですが、環境構築の方が手間取ったくらい簡単に回答できました。
LinuxかMacでの環境構築が可能という情報を見つけたので、とりあえず手持ちのMacに環境をインストール後にプログラムを開始。

Go言語の仕様として、if文等の波括弧(中括弧)の位置が固定されており、C言語ほど構文の自由度が無い事が不満でしたが、それ以外は使いやすいというか、結構Objective-Cっぽいというか・・・
後は未使用変数の縛りが厳しかったり(これはコンパイルオプション等で回避できるのかな?)、初期値の代入方法にクセがあったりしたのも印象的でした。

今回の解法ですが、pngファイルから色情報を取得し、その色情報を連結したものをキーとした連想配列を生成し、その数を数えることで画像の色数としました。
(連想配列は同一のキーは上書きされるという特性を利用しています。)
連想配列の総数の取得方法が分からなかった為、連想配列を回しながらインクリメントしていますが、これは標準命令(count的な関数)で効率的にできるはずです。

が、それを調べる間もなくうまくプログラムが動いてしまったので、このまま提出して合格となりました。

package main

import (
    "fmt"
    "io"
    "strings"
    /* add more */
    "image/png"
)

func CountColor(png2 io.Reader) int {
    img, e := png.Decode(png2);
    if e != nil {
        return -1
    }

    m := make(map[string]int)

    for i:=0; i<img.Bounds().Size().X; i++ {
        for j:=0; j<img.Bounds().Size().Y; j++ {
            r,g,b,_ :=img.At(i,j).RGBA()
            m[fmt.Sprint(r) + "-" + fmt.Sprint(g) + "-" + fmt.Sprint(b)] = 1
        }
    }

    cnt := 0
    for _, value := range m {
        cnt = cnt + value
    }

    return cnt
}

この問題については、解答をWEBの入力フォームから提出すると、結果がWEB画面に表示されました。
面白い仕組みだなぁ。。と思いながら、とりあえずGo!は完了。

次回はAndroid編です。

Posted in プログラム | Leave a comment

DevQuizのソースコード(WebGame編)

Google Developer Day 2011 に参加する為にDevQuizに参加させて頂きました。
合計得点は141.26点でボーダーラインよりは上にいるので参加は出来るかと思います。

ということで早速ソースの晒しです。
分野別クイズでは以下の3つを選択しました。
・WebGame
・Go!
・Android

その中で今回は「WebGame」のソースコードを公開していきます。

var main_cnt = 0;
var target_cnt = 0;
var main_color = "";

var main_element = document.getElementById('card' + main_cnt);
var target_element = null;

var myevent = document.createEvent('MouseEvents');
myevent.initEvent('click', false, true);

// main loop
while (main_element != null)
{
 if (main_element.style.backgroundColor == "")
 {
  main_element.dispatchEvent(myevent);

  main_color = main_element.style.backgroundColor;

  target_cnt = main_cnt + 1;
  target_element = document.getElementById('card' + target_cnt);

  while(target_element != null)
  {
   if (target_element.style.backgroundColor == "")
   {
    target_element.dispatchEvent(myevent);

    if (main_color == target_element.style.backgroundColor)
    {
     // 同一色が見つかった
     break;
    }
    else
    {
     main_element.dispatchEvent(myevent);
    }
   }

   target_cnt++;
   target_element = document.getElementById('card' + target_cnt);
  }
 }

 // next card
 main_cnt++;
 main_element = document.getElementById('card' + main_cnt);
}

ロジックとしては単純明快で、上からパネルを1枚ずつ開き、その隣のパネルから最後までを一気にめくり、色が合致した時点で次のパネルをめくって・・・の繰り返しです。
よって、既に開いたパネルを色を覚えておく等の頭の良いロジックは組んでおりません。
このロジックでも結構良い速度で回答していけたので、Chrome Extensionは凄いなぁ・・・と思いました。

今回、初めてChrome Extensionを触ったのですが、基本的にJavaScriptと同じだったので迷うことなくプログラムを組むことができました。
DevQuizが無ければ、この技術に触れることが無かったかと思うと、挑戦してみてよかったと思います。

次回はGo!のソースを晒します。

Posted in プログラム | Leave a comment