開発環境
- macOS Mojave - Apple (OS)
- Emacs (Text Editor)
- Windows 10 Pro (OS)
- Visual Studio Code (Text Editor)
- Python 3.7 (プログラミング言語)
問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の20章(6次の隔たり)、練習問題(問題3)の解答を求めてみる。
コード
Python 3
#!/usr/bin/env python3 def is_symmetry(graph: dict) -> bool: ''' >>> is_symmetry({}) True >>> is_symmetry({'a': ['b']}) False >>> is_symmetry({'a': ['b'], 'b': {'a'}}) True >>> is_symmetry({'a':['b', 'c'], 'b': ['a', 'c'], 'c': ['a', 'b'], 'd': ['e', 'f'], 'e': ['d', 'f'], 'f':['d', 'e']}) True >>> is_symmetry({'a':['b', 'c'], 'b': ['a'], 'c': ['a', 'b'], 'd': ['e', 'f'], 'e': ['d', 'f'], 'f':['d', 'e']}) False ''' for k, v in graph.items(): for t in v: if t not in graph or k not in graph[t]: return False return True def route(graph: dict, start: str, end: str) -> list: ''' >>> route({'a':['b'], 'b':['a']}, 'a', 'b') ['a', 'b'] >>> route({'a':['b'], 'b':['a']}, 'b', 'a') ['b', 'a'] >>> graph = {'a': ['b', 'c'], 'b': ['a', 'c', 'd'], 'c': ['a', 'b', 'e'], 'd': ['b', 'e'], 'e': ['c', 'd', 'f'], 'f': ['e']} >>> route(graph, 'a', 'f') ['a', 'c', 'e', 'f'] >>> route(graph, 'b', 'e') ['b', 'c', 'e'] ''' if start not in graph: raise Exception(f'開始地点{start}が無い') visited = {start} frontier = {start} frontiers = [frontier] while frontier: new_frontier = set() for g in frontier: if end in graph[g]: break s = set(graph[g]) - visited visited |= s new_frontier |= s frontiers.append(new_frontier) frontier = new_frontier route = [end] for frontier in frontiers[::-1]: if start in frontier: route.append(start) route.reverse() return route for g in frontier: if end in graph[g]: route.append(g) end = g break if __name__ == '__main__': import doctest doctest.testmod() graph = {'a': ['b', 'c', 'e'], 'b': ['a', 'c'], 'c': ['a', 'b', 'j'], 'd': ['e', 'f', 'g'], 'e': ['a', 'd', 'k'], 'f': ['d', 'n'], 'g': ['d', 'h', 'i'], 'h': ['g', 'm'], 'i': ['g', 'p'], 'j': ['c', 'k', 'l'], 'k': ['e', 'j', 'l'], 'l': ['j', 'k', 's'], 'm': ['h', 'n', 'o'], 'n': ['f', 'm', 'o'], 'o': ['m', 'n', 'v'], 'p': ['i', 'q', 'r'], 'q': ['p', 'w'], 'r': ['p', 'x'], 's': ['l', 't', 'u'], 't': ['s', 'u'], 'u': ['s', 't', 'v'], 'v': ['o', 'u', 'w'], 'w': ['q', 'v', 'y'], 'x': ['r', 'y', 'z'], 'y': ['w', 'x', 'z'], 'z': ['x', 'y']} print(is_symmetry(graph)) print(route(graph, 'b', 'z'))
入出力結果(cmd(コマンドプロンプト)、Terminal、Jupyter(IPython))
C:\Users\...>py -3 sample3.py -v Trying: is_symmetry({}) Expecting: True ok Trying: is_symmetry({'a': ['b']}) Expecting: False ok Trying: is_symmetry({'a': ['b'], 'b': {'a'}}) Expecting: True ok Trying: is_symmetry({'a':['b', 'c'], 'b': ['a', 'c'], 'c': ['a', 'b'], 'd': ['e', 'f'], 'e': ['d', 'f'], 'f':['d', 'e']}) Expecting: True ok Trying: is_symmetry({'a':['b', 'c'], 'b': ['a'], 'c': ['a', 'b'], 'd': ['e', 'f'], 'e': ['d', 'f'], 'f':['d', 'e']}) Expecting: False ok Trying: route({'a':['b'], 'b':['a']}, 'a', 'b') Expecting: ['a', 'b'] ok Trying: route({'a':['b'], 'b':['a']}, 'b', 'a') Expecting: ['b', 'a'] ok Trying: graph = {'a': ['b', 'c'], 'b': ['a', 'c', 'd'], 'c': ['a', 'b', 'e'], 'd': ['b', 'e'], 'e': ['c', 'd', 'f'], 'f': ['e']} Expecting nothing ok Trying: route(graph, 'a', 'f') Expecting: ['a', 'c', 'e', 'f'] ok Trying: route(graph, 'b', 'e') Expecting: ['b', 'c', 'e'] ok 1 items had no tests: __main__ 2 items passed all tests: 5 tests in __main__.is_symmetry 5 tests in __main__.route 10 tests in 3 items. 10 passed and 0 failed. Test passed. True ['b', 'a', 'e', 'd', 'g', 'i', 'p', 'r', 'x', 'z'] C:\Users\...>
0 コメント:
コメントを投稿