Disposable teleports (O'Reilly) - テレポータで巡回

どんな問題？

Disposable teleports
http://www.checkio.org/mission/disposable-teleports/

島には8個のステーションがあり、テレポータでつながっている。このテレポータは一度しか使えない。第1ステーションを出発し、すべてのステーションを通って、最後に第1ステーションに戻ってくるルートを求めよ。

引数は、テレポータのリストがコンマ区切り文字列で渡される。第1ステーションと第2ステーションをつなぐテレポータは「12」と表記される。
戻り値は、ルートをステーション番号を並べた文字列で返す。

ステーションの数は8個で固定。

例題：

checkio("12,23,34,45,56,67,78,81") == "123456781"
checkio("12,28,87,71,13,14,34,35,45,46,63,65") == "1365417821"
checkio("12,15,16,23,24,28,83,85,86,87,71,74,56") == "12382478561"
checkio("13,14,23,25,34,35,47,56,58,76,68") == "132586741"

どうやって解く？

例えば、例題の

checkio("12,23,34,45,56,67,78,81")

の場合、1からつながっているテレポータは12と81の2つある。1から2へ進むと、2からつながっているテレポータは12,23の2つだが、12は使用済みなので使えない。一度使ったテレポータは二度と使わないようにしながら、探索を進めていけばいいかな。
最短距離を聞かれているわけではないので、DFSを使って書いてみる。

まず、"12"と"21"のテレポータは同じなので、比較しやすいように{'1','2'}のようなsetに変換しておく。

teleports = [set(t) for t in teleports_string.split(',')]

すべてのステーションを通過して、最後のステーションが1なら終了。この判定はこのように書いた。

if len(set(route)) == 8 and route[-1] == '1':
    pass

DFSなのでスタックを使い、スタックには、(ステーション番号,今までのルート,使用済みのテレポータのリスト)のタプルを入れる。
現在のステーションからつながっている未使用のテレポータを探して、次の目的地をスタックに追加する。

まとめ

def checkio(teleports_string):
    # テレポータを"12"形式から {'1','2'}形式に変換
    teleports = [set(t) for t in teleports_string.split(',')]
    stack = [('1', '1', [])]  # (station, route, visited)
    while stack:
        station, route, visited = stack.pop()
        # 1～8までのステーションを通過し、最後のステーションが1なら終了
        if len(set(route)) == 8 and route[-1] == '1':
            return route
        else:
            # 現在のステーションからつながっている未使用のテレポータ
            for teleport in [t for t in teleports if station in t and t not in visited]:
                dest = (teleport - {station}).pop()  # 目的地を取り出す
                stack.append((dest, route + dest, visited + [{station, dest}]))
    return ''

http://www.checkio.org/mission/disposable-teleports/publications/natsuki/python-3/first/
これで公開～。

他の人の答え

再帰を使った解答も多かった。例えばこちら（再帰の部分だけ抜粋）

def seek(level, p0, log, use, tel):
    if p0 == '1' and len(set(log)) == 8: return log
    for p1 in '12345678':
        if (p0+p1 not in tel and p1+p0 not in tel) or p0+p1 in use or p1+p0 in use: continue
        rc = seek(level + 1, p1, log + p1, use + [p0+p1], tel)
        if rc: return rc

http://www.checkio.org/mission/disposable-teleports/publications/Sim0000/python-3/recursive/
p0が現在値、logが通ってきたルート、useが使用済みテレポータ、telがすべてのテレポータ。

再帰だと、とてもシンプルでわかりやい。
そういえば、アルゴリズムの本に「DFSは再帰を使うと簡単に書ける。」って載ってたっけ。