目次

現役のエンジニア・企業がプログラミングの問題を出してくれる CodeIQ というサイトがある。問題を解くと、正解不正解の判定や、フィードバックなどを行ってくれる。ジャンルや言語などはさまざまある。

グループを作ろう!

今回は結城浩さんの「グループを作ろう!」という問題に挑戦してみた。アルゴリズムの問題で、プログラムを使って解いても使わずに解いても構わない。プログラムを使う場合、言語は何でも良い。解答(とコメントなど)を送ると、フィードバックをもらえる。

問題の概要は以下。

Bill=Billy
Mick=Michael
Billy=William
というように、同じ人物を表すニックネームのペアが 444 個与えられる。同じ名前をすべて連結し、
Bill=Billy=Will=William=Willie=Willy
Michael=Mick=Micky=Mike=Mikey
というようにグルーピングする。ただし、各行の順番および、同一行内の名前は ASCII 順に並べなければならない。

自分の解答:STEP 1 グループ番号割り振り

C++ でプログラムを組む前提で。

どうやってグループを寄せ集めていくかと考えたとき、グループ毎の配列(vector)を用意してしまう、というのは最初に思いつくが、さすがに効率が悪い(名前を読み込む度に、すべてのグループ配列を見て、すでにグループ化されているか調べる必要がある)。

漠然と、木を使えばできるのではないかとイメージしたが、残念ながら、木を簡単に実装する方法を思いつかなかった。

CodeIQ_グループ割り振りそこで代わりに、グループ番号を割り当てていく方法を採った(右はイメージ図)。

ペアの両辺を読み込み、それぞれの名前に既にグループ番号が割り当てられているか調べる。両辺とも未割り当てであれば、新しいグループ番号を割り振る。いずれかが割り当て済みであれば、もう片方に同じグループ番号を割り当てる。

CodeIQ_グループ変更両方とも割り当て済みで、かつ、違うグループ番号であれば、今までは別のグループとして扱ってきたが、実は同じグループであることが分かったということなので、片方のグループ番号をすべて書き換える。

名前→グループ番号の対応を格納するのは、STL の map を用いた。

自分の解答:STEP 2 結合

すべてグループ分けできたら、同じグループ同士を連結していく。string 型の vector を用意しておき、1 行に 1 グループを突っ込んでいく。

CodeIQ_行番号割り振り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++;
}


模範解答

CodeIQ_木模範解答では、やはりグルーピングに木を使っていた。

面白かったのは木の実装方法。木を map で実装していた(模範解答は perl と思われる言語で実装されていたので、実際には連想配列)。

map のキーに、葉っぱの名前を入れ、値に、根っこの名前を入れる。根っこの名前は、値を空文字列にでもしておく。

こうすることで、数回 map を探索すれば、一番根っこの名前にたどりつける。1 つの根っこから出てくる名前はみな同じグループで、グループの数だけ、根っこ(空文字列)があることになる。

木をこうやって実装するのは定石なのだろうか。シンプルでいいな。

木の良い点は、グループの結合が楽ちんなこと。2 つのグループの根っこのうち、片方の空文字列をやめて、もう片方の根っこの名前を入れるだけで良い。どんなにグループが巨大でも、1 つの書き換えで済む。

感想

単にグルーピングするだけというシンプルな問題なのに、やってみるといろいろ考えることがあって面白かった。Union Find アルゴリズムとか Union Find Tree データ構造などという問題らしい。

実装言語を問わないこともあり、いろんな解答があったと聞く。なかにはエクセルで解いた人もいるとか。

他の人がどんな解答をしているのか気になっているのだが、残念ながら、ググっても自分の解答を公開している人はほとんどいないようだ。

結城さんがせっかく公開 OK に設定してくれているのだから、自分の解答を公開する人が増えてくれればいいなと思う。