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";
}
