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は再帰を使うと簡単に書ける。」って載ってたっけ。