ブログの語源をたどってみると、ウェブ上のログという意味でウェブログと呼ばれていたのが縮められたようだ。というわけでこれはただの記録。あなたにとってなんの役に立たなくても時間の返品は出来かねます。
去る3/12にベルサール汐留で開催されたGoogle DevFest 2010 Japanに参加してきた。このイベントは参加証をゲットするためにクイズに挑戦しなければならないという斬新な試みがなされていた。
クイズの内容はいろいろなものがあったが、いくつかプログラムを書かなければ解けない問題があった。パッチワーク問題はそのひとつ。以下に問題を引用する。
ここに "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例2:
入力塗りつぶしたところ.BAABBABBBB BAABABBBBB BBAABABBBA BABBBABBAA BBABAAABAB BABABBBAAA AABBBAAAAA BAAAAAABBB AAABABBAAB AABAABBABA
答えBAABBABBBB BAABABBBBB BBAABABBB_ BABBBABB__ BBABAAAB_B B_BABBB___ __BBB_____ B______BBB ___B_BBAAB __B__BBABA
0 0 1 2 1 4 7 6 4 4
問題文を一目見て、ぷよぷよかと。
マス目毎に再帰呼び出しを行えば、とりあえず解けそうだなと思った。
何の言語で書いてみようかと思ったが、脳ミソが溶けていてJava以外の言語で書ける気がしなかったので仕方なくJavaで書いた。以下がそのプログラム。
package devfest;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.logging.Logger;
/**
* @author hideaki
*
*/
public class PatchWork {
private static final Logger logger = Logger.getLogger(PatchWork.class.getName());
private static enum Type {
A, B
}
/**
* パッチワークテーブルのマス目の一要素を表すクラス。
*/
private static final class Element {
/** この要素の一つ前の行の要素。無い場合はnull */
Element up;
/** この要素の一つ後の行の要素。無い場合はnull */
Element down;
/** この要素の一つ前の列の要素。無い場合はnull */
Element left;
/** この要素の一つ後の列の要素。無い場合はnull */
Element right;
final Type type;
/**
* 上下左右に同じ文字の要素のつながった数。
* 未調査の場合はnull。
*/
Counter counter = null;
Element(Type type) {
if (type == null)
throw new NullPointerException();
this.type = type;
}
}
/**
* 上下左右に同じタイプの要素がいくつつながっているかを表すクラス。
*/
private final class Counter {
private int count = 0;
/**
* カウントを1つ増やす。
* 親インスタンスのmaxメンバを参照し、countがmaxの値を超えた場合、更新する。
*/
void increment() {
count++;
if (count > max)
max = count;
}
int getCount() {
return count;
}
}
/** パッチワークテーブル */
private final List<List<Element>> table;
/** 最大連結数 */
private int max = 0;
/**
* @param args 第1引数はロードするファイル名
*/
public static void main(String[] args) throws Exception {
PatchWork patchWork = new PatchWork(args[0]);
patchWork.search();
patchWork.makeResult();
}
/**
* コンストラクタ。
* 指定されたファイルを読み込み、パッチワークテーブルを完成させる。
*
* @param filename ロードするファイル名
* @throws IOException ファイルのロードに失敗した場合
*/
public PatchWork(String filename) throws IOException {
List<List<Type>> typeTable = loadFile(filename);
List<List<Element>> result = new ArrayList<List<Element>>();
List<Element> lastLine = null;
for (List<Type> typeList : typeTable) {
List<Element> thisLine = new ArrayList<Element>();
Element lastElement = null;
for (int i = 0; i < typeList.size(); i++) {
Element thisElement = new Element(typeList.get(i));
if (lastElement != null) {
// 前後列の関連付け
lastElement.right = thisElement;
thisElement.left = lastElement;
}
if (lastLine != null) {
// 前後行の関連付け
Element upElement = lastLine.get(i);
upElement.down = thisElement;
thisElement.up = upElement;
}
thisLine.add(thisElement);
lastElement = thisElement;
}
result.add(Collections.unmodifiableList(thisLine));
lastLine = thisLine;
}
table = Collections.unmodifiableList(result);
}
/**
* ファイルを読み込んで、対応するTypeのテーブルを作成する。
*
* @param filename ロードするファイル名
* @return Typeテーブル
* @throws IOException ファイルのロードに失敗した場合
*/
private List<List<Type>> loadFile(String filename) throws IOException {
BufferedReader reader = null;
try {
List<List<Type>> result = new ArrayList<List<Type>>();
reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));
for (String line; (line = reader.readLine()) != null; ) {
List<Type> row = new ArrayList<Type>();
for (char c : line.toCharArray())
row.add(Type.valueOf(String.valueOf(c)));
result.add(Collections.unmodifiableList(row));
}
return Collections.unmodifiableList(result);
} finally {
if (reader != null)
reader.close();
}
}
public void search() {
for (List<Element> line : table)
for (Element element : line)
if (element.counter == null) // その要素が未判定の時
traverse(element.type, new Counter(), element);
logger.info("max:" + max);
}
/**
* 判定対象が、指定されたタイプと同じタイプのエレメントかどうかを判定する。
* 判定対象がnullの場合、判定対象が判定済みの場合、または判定対象が指定されたタイプと異なる場合は終了する。
* それ以外の場合、その上下左右の要素を再帰的に判定する。
*
* @param type 判定対象と比較するタイプ
* @param counter エレメントが保持するカウンター
* @param element 判定対象
*/
private void traverse(Type type, Counter counter, Element element) {
assert type != null && counter != null;
if (element != null && element.counter == null && element.type == type) {
element.counter = counter;
counter.increment();
traverse(type, counter, element.up);
traverse(type, counter, element.down);
traverse(type, counter, element.left);
traverse(type, counter, element.right);
}
}
/**
* 各行のmax要素を数え、標準出力する。
*/
public void makeResult() {
StringBuilder sb = new StringBuilder();
for (List<Element> line : table) {
int count = 0;
for (Element element : line) {
if (element.counter.getCount() == max) {
count++;
sb.append('_');
} else {
sb.append(element.type);
}
}
System.out.println(count);
sb.append('\n');
}
logger.info(sb.toString());
}
}
ファイルから読み込む挙動とElementリストの初期化を分けたのには、特に深い意味はない。読み込み元がファイル以外になることも考えて処理を分離しただけである。
処理としては単純で、あるElement（マス目）の上下左右が自分と同一であるかどうかチェックし、同一であればその先を再帰的に調べていくだけである。つながった領域と認識されたElement同士は、Counterインスタンスを共有する。Counterインスタンスはその領域のつながった数を表す。ついでにElementがCounterインスタンスを持つことが、そのElementがチェック済みであることを意味している。後で最大値をチェックするのが面倒だったので、ちょっとズルをしている。
この解法で気になるのは、再帰処理のスタックがどこまで積まれるか、である。最悪の場合（全マスがAまたは全マスがB）600x600=360,000スタックが積まれることになり、これは流石にオーバーフローするだろう。したがって、これは問題のマス目の性質が比較的良心的であることを期待している。
さて、DevFestで（正確にはDevFestお開き後に同じ会場で催されたGTUG主催のLightening Talkで）問題の答え合わせがあり、このパッチワーク問題にはUnion-Findと呼ばれるアルゴリズムを利用するのが良いという話があった。なので帰って早速調べてみた。
一言で言ってしまうと、このアルゴリズムは、ある集合を互いに素な部分集合に分類するのに使える。パッチワーク問題でいうある集合とは600x600のマス目すべてであり、互いに素な部分集合とは隣同士がつながっている部分である。ちなみにここで言う互いに素とは、同じ要素が複数の部分集合に含まれないことをさす。要するにある隣同士がつながった塊と、別の塊の両方に、同じマス目が含まれることが無いことを意味している。
同じ部分集合に含まれる要素をN-ary treeで保持し、root要素を使って管理することで高速に処理しようという狙いがある。
用意しなければならない関数は2つ、あるtreeのrootを見つけるfindと2つのtreeをマージするunionである。unionは片方のtreeのroot要素の直下に、もう片方のroot要素が結合されることでなされる。treeが深いほどrootを見つける処理が増えるので、treeはなるべく浅い方がいい。なのでunion時には2つのtreeの深さを比べて浅いtreeが深いtreeの下に入るようにする。
というわけで、パッチワークプログラムをUnion-Findアルゴリズムを利用するように改造したのが以下である。
package devfest;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.logging.Logger;
public class PatchWork2 {
private static final Logger logger = Logger.getLogger(PatchWork2.class.getName());
private static enum Type {
A, B
}
/**
* パッチワークテーブルのマス目の一要素を表すクラス。
*/
private static final class Element {
/** この要素の一つ前の行の要素。無い場合はnull */
final Element up;
/** この要素の一つ前の列の要素。無い場合はnull */
final Element left;
final Type type;
private final UnionFind unionFind;
Element(Type type, Element up, Element left) {
if (type == null)
throw new NullPointerException();
this.type = type;
this.up = up;
this.left = left;
unionFind = new UnionFind();
}
void union(Element element) {
unionFind.union(element.unionFind);
}
int size() {
return unionFind.size();
}
}
/** パッチワークテーブル */
private final List<List<Element>> table;
private int max;
/**
* @param args 第1引数はロードするファイル名
*/
public static void main(String[] args) throws Exception {
PatchWork2 patchWork = new PatchWork2(args[0]);
patchWork.search();
patchWork.makeResult();
}
/**
* コンストラクタ。
* 指定されたファイルを読み込み、パッチワークテーブルを完成させる。
*
* @param filename ロードするファイル名
* @throws IOException ファイルのロードに失敗した場合
*/
public PatchWork2(String filename) throws IOException {
List<List<Type>> typeTable = loadFile(filename);
List<List<Element>> result = new ArrayList<List<Element>>();
List<Element> lastLine = null;
for (List<Type> typeList : typeTable) {
List<Element> thisLine = new ArrayList<Element>();
Element lastElement = null;
for (int i = 0; i < typeList.size(); i++) {
Element upElement = (lastLine == null) ? null : lastLine.get(i);
Element thisElement = new Element(typeList.get(i), upElement, lastElement);
thisLine.add(thisElement);
lastElement = thisElement;
}
result.add(Collections.unmodifiableList(thisLine));
lastLine = thisLine;
}
table = Collections.unmodifiableList(result);
}
/**
* ファイルを読み込んで、対応するTypeのテーブルを作成する。
*
* @param filename ロードするファイル名
* @return Typeテーブル
* @throws IOException ファイルのロードに失敗した場合
*/
private List<List<Type>> loadFile(String filename) throws IOException {
BufferedReader reader = null;
try {
List<List<Type>> result = new ArrayList<List<Type>>();
reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));
for (String line; (line = reader.readLine()) != null; ) {
List<Type> row = new ArrayList<Type>();
for (char c : line.toCharArray())
row.add(Type.valueOf(String.valueOf(c)));
result.add(Collections.unmodifiableList(row));
}
return Collections.unmodifiableList(result);
} finally {
if (reader != null)
reader.close();
}
}
public void search() {
for (List<Element> line : table) {
for (Element element : line) {
compare(element, element.up);
compare(element, element.left);
}
}
logger.info("max:" + max);
}
private void compare(Element thisElement, Element otherElement) {
assert thisElement != null;
if (otherElement != null && otherElement.type == thisElement.type) {
thisElement.union(otherElement);
int tmp = thisElement.size();
if (tmp > max)
max = tmp;
}
}
/**
* 各行のmax要素を数え、標準出力する。
*/
public void makeResult() {
StringBuilder sb = new StringBuilder();
for (List<Element> line : table) {
int count = 0;
for (Element element : line) {
if (element.size() == max) {
count++;
sb.append('_');
} else {
sb.append(element.type);
}
}
System.out.println(count);
sb.append('\n');
}
logger.info(sb.toString());
}
}
package devfest;
public final class UnionFind {
/** この要素のroot。経路圧縮のためにメンバ定義する。 */
private UnionFind root = this;
/** この要素の親要素。この要素がrootの場合はnull */
private UnionFind parent;
/** この要素が含まれるtreeの深さを表す。自身がroot要素である場合に限り意味を持つ。 */
private int rank;
/** この要素が含まれるtreeの構成数を表す。自身がroot要素である場合に限り意味を持つ。 */
private int size = 1;
/**
* この要素が含まれるtreeのrootを見つけて返す。
*
* @return root要素
*/
public UnionFind find() {
while (root.parent != null)
root = root.parent;
return root;
}
/**
* この要素が含まれるtreeと引数で指定された要素が含まれるtreeを結合する。
* 但し、両者のrootが同一である場合（すでに結合されている場合）何も行わない。
*
* @param other 結合する相手のtreeに含まれる要素
*/
public void union(UnionFind other) {
UnionFind thisRoot = this.find();
UnionFind otherRoot = other.find();
if (thisRoot != otherRoot) {
if (thisRoot.rank > otherRoot.rank) {
otherRoot.parent = thisRoot;
thisRoot.size += otherRoot.size;
} else {
thisRoot.parent = otherRoot;
otherRoot.size += thisRoot.size;
if (thisRoot.rank == otherRoot.rank)
otherRoot.rank++;
}
}
}
public boolean isRoot() {
return parent == null;
}
public int size() {
return find().size;
}
}
再利用の予定は今のところないが、純粋なUnion-Findアルゴリズム部分は別クラスとしている。
このアルゴリズムの計算量は O(A(n)) となるらしい。Aはアッカーマン関数の逆関数。この辺になるとまともな文献を漁らないとなんのことか分からないが、かなりゆっくり増加する関数らしい。
UnionFindを適応してるほうの，compare(Element thisElement, Element otherElement)の片方って要素じゃなくて集合ではいってくるの？
返信削除http://bit.ly/ajS0vh
返信削除ここにでてくるUnionFindをよんでみたんだけど，treeと要素ではなく，tree同士を比較するってのが，このパッチワーク問題にどう当てはめるのかわからんかったです．
教えてください．
Union-Findアルゴリズムは、単一のrootの要素を作ること、treeに属する要素のrootをたどること、たどったroot同士を比較することでそれらが同じグループ(tree)に属しているか判定することを、素早くできるのが特徴です。
返信削除上記のプログラムでは、パッチワークの並び(Element)を最初はすべてrootだけからなる1個ずつのグループ(tree)として作成し、1つずつ隣同士を比較して、同じTypeであればtreeを結合して一つのグループ(tree)にするということをしています。
それを実際にやっているのがcompare(Element, Element)メソッドです。二つのElementのTypeが等しいとき、それぞれに対してfind()メソッドを呼び、各々のElementが所属しているtreeのroot Elementを取得します。root Elementが共通であれば、それらはすでに同じグループ(tree)に属しているので何もしません。異なっていれば、片方のtreeをもう片方のtreeの要素に組み入れる(union)ことで、それらを同じグループ（同じrootを持つtree）にします。
したがって最初の質問に対する答えは、compareメソッドの2つの引数が直接指しているのはある隣同士のElementですが、中でそれぞれのrootを取得することで実際に扱っているのは両方とも集合(tree)になります。
2つめの質問のtree同士を比較すると言うのは、おそらく上記のtreeのrootを比較することで同じtreeかどうかを判定することを指していると思います。