Meta-x Blog

Just another WordPress weblog

Google DevFest 2010 はなんとか参加証を獲得することができました。TwitterのTLをみると合格ライン前後だった様子。これまでGoogleコミュニティへの貢献がないのであれば全問正解でないと点数的に厳しかったようです。

Quiz の続きです。次のプログラム問題は「パッチワーク」。テキスト形式のデータファイルを解析して、出力を求める形式です。「漢字変換マシン」と違ってWebサイトにする必要はなく、解答の出力結果を投稿すればよいだけでした。参加者が同じデータファイルを使用するのであれば解答を共有してズルいこともできたのかもしれません。

問題

ここに “A” または “B” という文字のみを含む 600 桁、600 行のテキストがあります。これを 600 x 600 の升目状に並べ、上下左右に同じ文字がある部分をつながっているとみなします。
まず、最も多くの文字がつながっている領域をすべて “_” で塗りつぶしてください。 最も多くの文字がつながっている領域が複数存在するならば、それらすべての領域を “_”で塗りつぶすこととします。
そして、各行ごとに “_” が何個含まれているかを数え、それらの数値を改行区切りのテキスト(600 行)として答えてください。
例:

ABAAB AB__B 2
BABAA B_B__ 3
BAABB B____ 4
ABABB AB___ 3
BABAA BABAA 0

漢字変換マシン」と同様、気楽に組めるPerlで書きました。別にテキストを実際に”_”に置き換えて数える必要はないので、最大つながりがどこにあるかを調査し、各行に含まれる数を調べる方針。

前の「漢字変換マシン」に比べてソースコードが汚く、「数世代前のプログラム」って感じがしますな。

解答:

#!/usr/bin/perl
use strict;

### 準備 ###

# 入力文字列を@mapに格納して、列数・行数を取得
my @map = ();
my $x = 0;
while (<STDIN>) {
    chomp;
    for ($x = 0; $x < length($_); $x++) {
	$map[$x][$. - 1] = substr($_, $x, 1);
    }
}

# @map の 行数
my $max_y = $.;

# @map の 列数
my $max_x = $x;

### 「つながり」の調査 ###

# 最も大きい「つながり」のサイズ
my $max_size = 0;

# 最も大きい「つながり」のIDを入れる配列
my @max_size_index = ();

# 調査済みを示す2次元配列
my @checked = ();

# mapの左上から右下に向けて走査
for (my $y = 0; $y < $max_y; $y++) {
    for (my $x = 0; $x < $max_x; $x++) {

        # 調査済みであれば次へ
        if (defined($checked[$x][$y])) {
            next;
        }

        # 調査対象のIDを取得(BaseIDとする)
        my $base_index = $y * $max_x + $x;

        # サイズの初期化
        my $size = 0;

        # つながっているセルのIDを格納するキュー
        my @area_index = ();

        # キューに調査対象ID を追加
        push (@area_index, $base_index);

        # キューが空になるまで繰り返す
        while ($#area_index >= 0) {

            # キューの先頭を取り出して位置を求める
            my $index = shift(@area_index);
            my $index_x = $index % $max_x;
            my $index_y = int($index / $max_x);

            # 調査済みであれば飛ばす
            if (defined($checked[$index_x][$index_y])) {
                next;
            }

            # 上を調べ、未調査でつながっていればキューに追加
            if ($index_x > 0
                && !defined($checked[$index_x - 1][$index_y])
                && $map[$index_x][$index_y] eq $map[$index_x - 1][$index_y]) {
                push(@area_index, $index - 1);
            }

            # 下を調べ、未調査でつながっていればキューに追加
            if ($index_x < $max_x - 1
                && !defined($checked[$index_x + 1][$index_y])
                && $map[$index_x][$index_y] eq $map[$index_x + 1][$index_y]) {
                push(@area_index, $index + 1);
            }

            # 左を調べ、未調査でつながっていればキューに追加
            if ($index_y > 0
                && !defined($checked[$index_x][$index_y - 1])
                && $map[$index_x][$index_y] eq $map[$index_x][$index_y - 1]) {
                push(@area_index, $index - $max_x);
            }

            # 右を調べ、未調査でつながっていればキューに追加
            if ($index_x < $max_y - 1
                && !defined($checked[$index_x][$index_y + 1])
                && $map[$index_x][$index_y] eq $map[$index_x][$index_y + 1]) {
                push(@area_index, $index + $max_x);
            }

            # 調査済みとする(BaseIDを記録)
            $checked[$index_x][$index_y] = $base_index;

            # つながりの大きさを1増やす
            $size++;

        }
        # 「つながり」の大きさ 記録更新
        if ($max_size < $size) {
            $max_size = $size;

            # 記録リストをクリア
            @max_size_index = ();
        }
        # 「つながり」の大きさ 記録タイ
        if ($max_size == $size) {

            # 記録リストに追加
            push (@max_size_index, $base_index);
        }
    }
}

### 出力 ###

# 調べやすくするための工夫 ($maxarea[$i]==1なら最大「つながり」)
my @max_area = ();
foreach my $i (@max_size_index) {
    $max_area[$i] = 1;
}

# 上の行から下へ走査
for (my $y = 0; $y < $max_y; $y++) {
    my $count = 0;
    # 各行を左から右へ走査
    for (my $x = 0; $x < $max_x; $x++) {
        # 最大「つながり」の一部ならカウントアップ
        if ($max_area[$checked[$x][$y]] == 1) {
            $count++;
        }
    }
    # 出力
    print "$count\n";
}

今回のGoogle DevFest 2010 の参加証をもらうためにはGoogleからのQuizに正解する必要が
あり、その中の何問かはプログラムを組んで解答します。僕はPerlを使って解答しました。

25日の締切を過ぎたので自分の解答を貼ります。まず「漢字変換マシン」の解答。
Googleからのhttpリクエストに対して正しいレスポンスを返す問題です。

漢字変換マシン

数字を漢数字に変換するアプリケーションを作ってください。

http://[あなたのアプリケーションのURL]?n=[数字] にアクセスすると、 text/plain でその数字を漢数字に変換した結果を返すウェブサーバを作ってください。 ただし、漢字はすべて以下の表の通りにアルファベットに変換して出力してください。

零 → A 一 → T 二 → Y 三 → C
四 → L 五 → S 六 → R 七 → Z
八 → N 九 → U 十 → P 百 → X
千 → B 万 → D 億 → M 兆 → Q

注意:

  • 「千万」「千億」「千兆」の前に「一」がつかないようにしてください。
  • 入力は負でない整数で、大きさは高々9999兆9999億9999万9999までです。
  • 標準のポート番号80番のみ扱えます。

解答:

#!/usr/bin/perl
use strict;
use CGI;

my $query = new CGI;

# 入力値を16桁ゼロパディングに変換
my $numstr = sprintf("%016d",$query->param('n'));

# 出力文字列
my $ansstr = "";

# 一万ごとの桁「兆」「億」「万」「(空)」
my @man_keta = ('Q','M','D','');
# 「千」「百」「十」「(空)」
my @keta = ('B', 'X', 'P','');
# 「零」「一」「二」「三」「四」「五」「六」「七」「八」「九」
my @kazu = ('A','T', 'Y', 'C', 'L', 'S', 'R', 'Z', 'N', 'U');

for (my $i = 0; $i < 4; $i++) {
  # 4桁(一万)ずつの処理
  my $substr = "";
  for (my $j = 0; $j < 4; $j++) {
    # 1桁ずつの処理
    my $k = substr($numstr, $i*4+$j,1);
    if ($k ne '0') {
      # 数字が0でなければ文字を出力
      if ($k eq '1' && $j ne '3') {
        # 「一千」「一百」「一十」を避ける
        $substr .= $keta[$j];
      } else {
        # 数字と位取りを連結
        $substr .= $kazu[$k] . $keta[$j];
      }
    }
  }
  if ($substr ne ''){
    # 4桁のうちに数字があれば「兆」「億」「万」を連結
    $ansstr .= $substr . $man_keta[$i];
  }
}

if ($ansstr eq '') {
  # 出力される文字がなければ「零」
  $ansstr = 'A';
}

# 出力文字列
print "Content-Type: text/plain\n";
print "\n";
print $ansstr."\n";

動作の例:

Syntax Highlighter for WordPress を使ってソースコードを投稿するテストです。
Androidのアプリのコードを掲載してみます。

	@Override
	public void onCreate() {
		super.onCreate();
		Toast.makeText(this, "Service.onCreate()", Toast.LENGTH_LONG).show();
		/** NotificationManagerの取得 */
		nm = (NotificationManager) getSystemService(Context.NOTIFICATION_SERVICE);
		notif.icon = R.drawable.status_0;
		/** 通知領域をタップした際にMainActivityに遷移させる*/
		piMainActivity = PendingIntent.getActivity(
				this,
				0,
				new Intent(GeoTweetService.this, MainActivity.class),
				0);
	}

Twitterでプロフィール画像に画像を重ねる(クリスマスのときに赤い帽子が流行ったやつ)方法を知りたくて、調べ始めたらいろいろな方向に発散していく。

認証機構:OAuth
画像編集:ImageMagick
開発環境整理:Eclipse Plugin(SFTP, PHPeclipse)
etc…

調べて出てきた要素をスタックに積んで、下ろしていく作業。
これが面白いんだよなぁ。

会社の人とサイクリング。

二子玉川に集合して、多摩川サイクリングロード経由で調布飛行場、さらに上流の府中の自転車店、その後二子玉川に戻る行程でした。多摩サイは景色があまり単調でなく、結構色々変わっていたのが面白い。

二子玉川の解散後、最初は電車で帰ろうと思ってたけど、結局市川の家まで自走した。トータルで85キロ。最後は足が攣りそうになりました。

iPod版アルカノイドが意外と面白い。指で直接自機を操作できる。ステージ最初の曲も昔と同じで懐かしい。

アーケード版は大山のぶ代が得意らしい。意外な趣味だ。

最近iPod Touchを同期すると、音楽とビデオが全部消えて「内容がありません」と表示されてしまうことがある。

通勤時にPodcastを聴こうと思った時に限って消えていることに気づく。ガックリ。

Wordpress を入れてみました。

iPod Touchからの投稿テストです。