Determine the order (GitHub) - 文字の順番

どんな問題？

Determine the order
http://www.checkio.org/mission/determine-the-order/

独自のアルファベット順に応じて、ワードの文字が並んでいる。ワードのリストから、独自のアルファベット順を探し出せ。
ただし、順番が決定できない場合は、通常のアルファベット順（a-z）を使うこと。

引数は、ワードのリスト。ワード数は10個未満。
戻り値は、並び順を文字列で返す。

例えば、ワードが "acb","bd","zwa" の場合、

• "acb"からは、a＜c＜b という順番がわかる
• "bd"からは、b＜d
• "zwa"からは、z＜w＜a

まとめると、z＜w＜a＜c＜b＜d という順が得られるので、戻り値は"zwacbd"となる。

例題：

checkio(["acb", "bd", "zwa"]) == "zwacbd"
checkio(["klm", "kadl", "lsm"]) == "kadlsm"
checkio(["a", "b", "c"]) == "abc"
checkio(["aazzss"]) == "azs"
checkio(["dfg", "frt", "tyg"]) == "dfrtyg"

どうやって解く？

文字ごとに優先度を割りあてて、例えば、最初のワードが"acb"なら a=1.0、c=2.0、b=3.0 としておき、次のワード"bd"では、b=3.0だからd=4.0としておいて・・・最後にソートするとか？
うーん、ちょっとややこしいか。

もっと簡単な方法はないかな。
最初の文字（一番小さい文字）を探すには、「自分より左に他の文字が来ない文字」を探せばいいかな？
例えば、"acb", "bd", "zwa"なら、acbdwの左には何らかの文字が来るけど、zの左に来る文字は無い。つまりzが最初の文字となる。次はzを除いて同じ事を繰り返せば、文字の順番が判明するはず。
これは、言い換えると、「ワードに文字が含まれている場合は、必ず先頭に来る文字」を探せばいい。

まず、ワードリスト（data）に出てくる文字をアルファベット順にソートしておく。

letters = sorted(set(''.join(data)))

すべてのワードで「ワードに文字が含まれている場合は、必ずワードの先頭に来る」を満たしている文字が、最初の文字となる。sorted()することで、最初の文字が複数あるときには、a-zの順番が優先される。

def get_first_letter(words, letters, ignore):
    # 最初の文字を取得（ただしignoreは除外する）
    for l in sorted(letters - set(ignore)):
        if all(next(c for c in w if c not in ignore) == l for w in words if l in w):
            return l
    raise Exception('first letter not found')
 
def checkio(data):
    letters = set(''.join(data))  # dataに出てくる文字セットを取得
    result = ''
    while len(result) < len(letters):
        result += get_first_letter(data, letters, result)

http://www.checkio.org/mission/determine-the-order/publications/natsuki/python-3/first/

他の人の答え

いくつかの解答のコメントで、「トポロジカルソート」という単語が出てきているのだが、どういうソートなんだろう。
http://www.checkio.org/mission/determine-the-order/publications/EnCuKou/python-3/first/
http://www.checkio.org/mission/determine-the-order/publications/kvas/python-3/literal-toposort/

Wikipediaの説明に沿ってコードを書いてみた。

def checkio(data):
    # グラフ(dict)を作成
    #   key   = ノード（文字）
    #   value = 入力辺（一つ前に来る文字）のset
    graph = {node: set() for node in ''.join(data)}
    for word in data:
        for i in range(1, len(word)):
            node, prev = word[i], word[i - 1]
            if prev != node:
                graph[node].add(prev)

    l = []  # ソートの結果
    s = [node for node, inputs in graph.items() if not inputs]  # 入力辺を持たないノード
    while s:
        n = sorted(s)[0]  # アルファベット順に取り出す
        s.remove(n)
        l.append(n)
        # 入力辺にnが含まれるノード（=nからの出力先ノード）を探す
        for m in [node for node, inputs in graph.items() if n in inputs]:
            # mがn以外の入力辺を持たないならsに追加
            graph[m].remove(n)  # mの入力辺nを削除
            if not graph[m]:    # mの入力辺が空ならsに追加
                s.append(m)

    if all(not inputs for inputs in graph.values()):  # グラフが辺を持っていない
        return ''.join(l)
    else:
        raise Exception('graph has at least one cycle')  # グラフに少なくとも1つの循環がある

入力辺を持たない、というのが、もっとも左側に来る文字、ということになるんだな。なるほど。

残る島は、Mine、HubSpot、Ice Baseの3つ。じゃあ、次はMineへ。