Google DevFest Quizをやってみました。(パッチワーク問題の回答)

すでに旧聞に属するネタですが、話題のGoogle DevFestのQuizの私の回答(に使ったプログラム)を晒してみます。間違いなどのご指摘があればコメントをお願いします。
ちなみに、こちらには他の方の回答(プログラム)がまとめられています。
いろんな解き方がありますね。

とりあえずパッチワーク問題の回答だけ。
問題文の一部を引用します。

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

例1:
入力

ABAAB
BABAA
BAABB
ABABB
BABAA

塗りつぶしたところ.

AB__B
B_B__
B____
AB___
BABAA

答え

2
3
4
3
0

私の回答

プログラムを紹介する前にまず解き方を説明します。
AやBとあるひとつひとつの文字を”Block”とします。
上下左右のBlockが同じ文字の領域を”Region”とします。
Blockは自分が所属するRegionを最大1つ保持(参照)し、Regionは同じRegionに属するすべてのBlockを保持(参照)します。

BlockとRegion

BlockとRegion

入力データを読み込むときは、左上から順に一行一行読むことになるので、ひとつBlockを作るたびに、上または左にあるBlockが同じ文字ならば、それらをくっつけて(Connectして)ひとつのRegionとする処理を行います。

e38391e38383e38381e383afe383bce382af2

Connect

またそのときに同じRegionに属するBlockの数を取得し、さらに最大のBlock数を持つRegionも(複数)保持するようにします。
入力データを読み終わったときに、もう一度左上から最大のBlock数を持つRegionに属するBlockの数を行毎にカウントすれば、回答が得られます。

プログラムはJavaで書きました。
(A、Bの2種類だけでなくcharに収まる範囲であればどんな文字でも大丈夫なはずです)

PatchWork.java
[Java]
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;

public class PatchWork {

public class Region {
public HashSet region = new HashSet();
public Region() {
}
public void add(Block block) {
region.add(block);
}
public int size() {
return region.size();
}
}
public class Block {
private Region region = null;
private char type = 0;
public Block(char type) {
this.type = type;
}
public int Connect(Block neighbor) {
if (neighbor.type == this.type) {
if (neighbor.region != null) {
// お隣がすでに誰かの領地だった場合
if (region == null) {
// 自分が誰の領地でもなければ、相手色に染まる。
region = neighbor.region;
}
else {
// 自分にすでに領地があれば、相手を自分色に染める。
for (Block block : neighbor.region.region) {
this.region.add(block);
}
for (Block block : neighbor.region.region) {
block.region = this.region;
}
}
}
else {
// お隣が誰の領地でもない場合
if (this.region == null) {
region = new Region();
}
// お隣を自分の領地にする
neighbor.region = region;
region.add(neighbor);
}
region.add(this);
return region.size();
}
return 0;
}
}

// すべてのブロック
private ArrayList< ArrayList > blocks = new ArrayList< ArrayList >();
// 最大の領域の大きさ
private int maxCount=0;
// 最大の領域(同じ大きさの領域を複数持てるようにHashSetで)
private HashSet regions = new HashSet();

public void addString(String str) {
ArrayList rowBlocks = new ArrayList();
for (int col=0; col < str.length(); col++) { Block block = new PatchWork.Block(str.charAt(col)); int thisCount = 0; if (blocks.size() > 0) {
// 真上(ひとつ前の行の同じ列)にあるブロックと接続
ArrayList preRow = blocks.get(blocks.size()-1);
Block preBlock = preRow.get(col);
thisCount = block.Connect(preBlock);
}
if (col > 0) {
// 手前(ひとつ前の列)にあるブロックと接続
Block preBlock = rowBlocks.get(col-1);
thisCount = block.Connect(preBlock);
}
if (thisCount > maxCount) {
// 領域のサイズが今までの最大より大きければ記録更新
maxCount = thisCount;
regions.clear();
regions.add(block.region);
}
else if (thisCount == maxCount) {
// 領域のサイズが今までの最大と同じなら追加
regions.add(block.region);
}
// System.out.println(“row=”+rowBlocks.size()+” col=”+col+” count=”+maxCount);
rowBlocks.add(block);
}
blocks.add(rowBlocks);
}

public String getResult() {
StringBuffer sb = new StringBuffer();
for (int row=0; row < blocks.size(); row++) { ArrayList blocks = this.blocks.get(row);
int count = 0;
for (int col=0; col < blocks.size(); col++) { Block block = blocks.get(col); // boolean isHit = false; for (Region region : regions) { if (block.region == region) { count++; // sb.append('_'); // isHit = true; break; } } // if (!isHit) { // sb.append(block.type); // } } sb.append(""+count+"\n"); // sb.append('\n'); } return sb.toString(); } /** * @param args */ public static void main(String[] args) { // String[] tbl = { // "aaabbbccc", // "aaacccbbg", // "eeefccbbb", // }; try { BufferedReader reader = new BufferedReader(new FileReader("D:\\patchworkinput.txt")); PatchWork pw = new PatchWork(); String line; while ((line = reader.readLine()) != null) { pw.addString(line); } System.out.println(pw.getResult()); } catch (IOException e) { // TODO 自動生成された catch ブロック e.printStackTrace(); } } } [/Java]

感想

仕事の納期直前だったので、やっつけで作ろうと思ったのですが、思ったより難しくて結局ちゃんと設計して作りました。
問題は面白かったのですが、おかげさまで睡眠時間がだいぶ削られました。。。
ちなみに、こういうパズル的なプログラミングの問題といえば、C Magazineを思い出しますね。
検索したらこういうサイトを見つけました。
和田維作さんのCマガ電脳クラブ

Share on FacebookTweet about this on TwitterShare on Google+Share on TumblrEmail this to someonePrint this page