1234567891011121314151617181920212223242526272829303132333435363738394041 |
- 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]], twiced: bool):
- path.extend([point])
- if point == 'end':
- completedPaths.append(path)
- return
- for neighbor in filter(lambda p: p != "start", graph[point]):
- if neighbor.islower():
- if neighbor in smalls:
- if not twiced:
- depthSearch(neighbor, path, smalls, completedPaths, graph, True)
- else:
- smalls.add(neighbor)
- depthSearch(neighbor, path, smalls, completedPaths, graph, twiced)
- smalls.remove(neighbor)
- path.pop()
- else:
- depthSearch(neighbor, path, smalls, completedPaths, graph, twiced)
- path.pop()
- done_paths = []
- depthSearch("start", [], set(), done_paths, graph, False)
- print(len(done_paths))
|