12345678910111213141516171819202122232425262728293031323334353637 |
- import argparse
- import functools
- from collections import defaultdict
- from typing import Set, List, Dict
- parser = argparse.ArgumentParser()
- parser.add_argument("ifile", type=argparse.FileType('r'))
- args = parser.parse_args()
- graph: defaultdict[str, Set[str]] = defaultdict(set)
- for edge in args.ifile.readlines():
- points = edge.strip().split('-')
- graph[points[0]].add(points[1])
- graph[points[1]].add(points[0])
- def depthSearch(point, path: List[str], smalls: Set[str], completedPaths: List[List[str]], graph: Dict[str, set[str]]):
- path.extend([point])
- if point == 'end':
- completedPaths.append(path)
- return
- for neighbor in filter(lambda p: p not in smalls and p != "start", graph[point]):
- if neighbor.islower():
- smalls.add(neighbor)
- depthSearch(neighbor, path, smalls, completedPaths, graph)
- smalls.remove(neighbor)
- path.pop()
- else:
- depthSearch(neighbor, path, smalls, completedPaths, graph)
- path.pop()
- done_paths = []
- depthSearch("start", [], set(), done_paths, graph)
- print(len(done_paths))
|