目次
現役のエンジニア・企業がプログラミングの問題を出してくれる CodeIQ というサイトがある。問題を解くと、正解不正解の判定や、フィードバックなどを行ってくれる。ジャンルや言語などはさまざまある。
問題の概要は以下。
Bill=Billy
Mick=Michael
Billy=William
というように、同じ人物を表すニックネームのペアが 444 個与えられる。同じ名前をすべて連結し、
Bill=Billy=Will=William=Willie=Willy
Michael=Mick=Micky=Mike=Mikey
というようにグルーピングする。ただし、各行の順番および、同一行内の名前は ASCII 順に並べなければならない。
どうやってグループを寄せ集めていくかと考えたとき、グループ毎の配列（vector）を用意してしまう、というのは最初に思いつくが、さすがに効率が悪い（名前を読み込む度に、すべてのグループ配列を見て、すでにグループ化されているか調べる必要がある）。
漠然と、木を使えばできるのではないかとイメージしたが、残念ながら、木を簡単に実装する方法を思いつかなかった。
そこで代わりに、グループ番号を割り当てていく方法を採った（右はイメージ図）。
ペアの両辺を読み込み、それぞれの名前に既にグループ番号が割り当てられているか調べる。両辺とも未割り当てであれば、新しいグループ番号を割り振る。いずれかが割り当て済みであれば、もう片方に同じグループ番号を割り当てる。
両方とも割り当て済みで、かつ、違うグループ番号であれば、今までは別のグループとして扱ってきたが、実は同じグループであることが分かったということなので、片方のグループ番号をすべて書き換える。
名前→グループ番号の対応を格納するのは、STL の map を用いた。
map を先頭から読み込んでいき、同じグループ番号の文字列が既に vector にあるか調べる。あれば、文字列の末尾に新しい名前を追加する。無ければ、新しい行の先頭に名前を追加する。
グループ番号と行番号の対応も、やはり map で覚えておく（……が、今から思えば、配列の方が高速だった）。
map を使うことにより。キーが自動的に ASCII 順になっているので、新しい行ができた時は、単純に配列の末尾に加えれば良く、ソートの必要は無い。また、1 つの行に名前を追加する際も、末尾に追加するだけで良く、ソートの必要は無い。
計算量は、入力のペア数を N として、グループ統合がなければ恐らく O(NlogN) だが、グループ統合があると最悪 O(N^2) になるのだろう。
模範解答では、やはりグルーピングに木を使っていた。
面白かったのは木の実装方法。木を map で実装していた（模範解答は perl と思われる言語で実装されていたので、実際には連想配列）。
map のキーに、葉っぱの名前を入れ、値に、根っこの名前を入れる。根っこの名前は、値を空文字列にでもしておく。
こうすることで、数回 map を探索すれば、一番根っこの名前にたどりつける。1 つの根っこから出てくる名前はみな同じグループで、グループの数だけ、根っこ（空文字列）があることになる。
木をこうやって実装するのは定石なのだろうか。シンプルでいいな。
木の良い点は、グループの結合が楽ちんなこと。2 つのグループの根っこのうち、片方の空文字列をやめて、もう片方の根っこの名前を入れるだけで良い。どんなにグループが巨大でも、1 つの書き換えで済む。
実装言語を問わないこともあり、いろんな解答があったと聞く。なかにはエクセルで解いた人もいるとか。
他の人がどんな解答をしているのか気になっているのだが、残念ながら、ググっても自分の解答を公開している人はほとんどいないようだ。
結城さんがせっかく公開 OK に設定してくれているのだから、自分の解答を公開する人が増えてくれればいいなと思う。
現役のエンジニア・企業がプログラミングの問題を出してくれる CodeIQ というサイトがある。問題を解くと、正解不正解の判定や、フィードバックなどを行ってくれる。ジャンルや言語などはさまざまある。
グループを作ろう！
今回は結城浩さんの「グループを作ろう！」という問題に挑戦してみた。アルゴリズムの問題で、プログラムを使って解いても使わずに解いても構わない。プログラムを使う場合、言語は何でも良い。解答（とコメントなど）を送ると、フィードバックをもらえる。問題の概要は以下。
Bill=Billy
Mick=Michael
Billy=William
というように、同じ人物を表すニックネームのペアが 444 個与えられる。同じ名前をすべて連結し、
Bill=Billy=Will=William=Willie=Willy
Michael=Mick=Micky=Mike=Mikey
というようにグルーピングする。ただし、各行の順番および、同一行内の名前は ASCII 順に並べなければならない。
自分の解答：STEP 1 グループ番号割り振り
C++ でプログラムを組む前提で。どうやってグループを寄せ集めていくかと考えたとき、グループ毎の配列（vector）を用意してしまう、というのは最初に思いつくが、さすがに効率が悪い（名前を読み込む度に、すべてのグループ配列を見て、すでにグループ化されているか調べる必要がある）。
漠然と、木を使えばできるのではないかとイメージしたが、残念ながら、木を簡単に実装する方法を思いつかなかった。
そこで代わりに、グループ番号を割り当てていく方法を採った（右はイメージ図）。ペアの両辺を読み込み、それぞれの名前に既にグループ番号が割り当てられているか調べる。両辺とも未割り当てであれば、新しいグループ番号を割り振る。いずれかが割り当て済みであれば、もう片方に同じグループ番号を割り当てる。
両方とも割り当て済みで、かつ、違うグループ番号であれば、今までは別のグループとして扱ってきたが、実は同じグループであることが分かったということなので、片方のグループ番号をすべて書き換える。名前→グループ番号の対応を格納するのは、STL の map を用いた。
自分の解答：STEP 2 結合
すべてグループ分けできたら、同じグループ同士を連結していく。string 型の vector を用意しておき、1 行に 1 グループを突っ込んでいく。map を先頭から読み込んでいき、同じグループ番号の文字列が既に vector にあるか調べる。あれば、文字列の末尾に新しい名前を追加する。無ければ、新しい行の先頭に名前を追加する。グループ番号と行番号の対応も、やはり map で覚えておく（……が、今から思えば、配列の方が高速だった）。
map を使うことにより。キーが自動的に ASCII 順になっているので、新しい行ができた時は、単純に配列の末尾に加えれば良く、ソートの必要は無い。また、1 つの行に名前を追加する際も、末尾に追加するだけで良く、ソートの必要は無い。
注意点
注意すべきはグループの統合で、最初はこれを見逃していた。できあがった解答を眺めていて偶然気づいた。グループ統合のコードを後から付け加えたので、これだけ異質な感じがする。計算量は、入力のペア数を N として、グループ統合がなければ恐らく O(NlogN) だが、グループ統合があると最悪 O(N^2) になるのだろう。
ソースコードの抜粋
// グループ番号割り当て
while ( aInFile && getline(aInFile, aLine) ) {
get_names(aLine, &aName1, &aName2);
// 名前のペアをマップに登録していく
p1 = aGroupMap.find(aName1);
p2 = aGroupMap.find(aName2);
if ( p1 == aGroupMap.end() && p2 == aGroupMap.end() ) {
// 新規登録
aGroupMap[aName1] = aGroupIndex;
aGroupMap[aName2] = aGroupIndex;
aGroupIndex++;
} else if ( p1 != aGroupMap.end() && p2 == aGroupMap.end() ) {
// aName1 が登録済み→aName2 を同じグループに登録
aGroupMap[aName2] = p1->second;
} else if ( p1 == aGroupMap.end() && p2 != aGroupMap.end() ) {
// aName2 が登録済み→aName1 を同じグループに登録
aGroupMap[aName1] = p2->second;
} else {
// 両方登録済み
if ( p1->second != p2->second ) {
// 違うグループとして登録されているのでグループを統合
change_group(&aGroupMap, p1->second, p2->second);
}
}
}
// A=B=C=D というような結合行を作成していく
while ( aGItr != aGroupMap.end() ) {
aRItr = aResultMap.find(aGItr->second);
if ( aRItr == aResultMap.end() ) {
// 新規に結果行に登録
aResult[aResultIndex] = aGItr->first;
aResultMap[aGItr->second] = aResultIndex;
aResultIndex++;
} else {
// 既存の行に追加
aResult[aRItr->second] += "="+aGItr->first;
}
aGItr++;
}
模範解答
模範解答では、やはりグルーピングに木を使っていた。面白かったのは木の実装方法。木を map で実装していた（模範解答は perl と思われる言語で実装されていたので、実際には連想配列）。
map のキーに、葉っぱの名前を入れ、値に、根っこの名前を入れる。根っこの名前は、値を空文字列にでもしておく。
こうすることで、数回 map を探索すれば、一番根っこの名前にたどりつける。1 つの根っこから出てくる名前はみな同じグループで、グループの数だけ、根っこ（空文字列）があることになる。
木をこうやって実装するのは定石なのだろうか。シンプルでいいな。
木の良い点は、グループの結合が楽ちんなこと。2 つのグループの根っこのうち、片方の空文字列をやめて、もう片方の根っこの名前を入れるだけで良い。どんなにグループが巨大でも、1 つの書き換えで済む。
感想
単にグルーピングするだけというシンプルな問題なのに、やってみるといろいろ考えることがあって面白かった。Union Find アルゴリズムとか Union Find Tree データ構造などという問題らしい。実装言語を問わないこともあり、いろんな解答があったと聞く。なかにはエクセルで解いた人もいるとか。
他の人がどんな解答をしているのか気になっているのだが、残念ながら、ググっても自分の解答を公開している人はほとんどいないようだ。
結城さんがせっかく公開 OK に設定してくれているのだから、自分の解答を公開する人が増えてくれればいいなと思う。
