-
Notifications
You must be signed in to change notification settings - Fork 1
/
part1.py
61 lines (47 loc) · 1.16 KB
/
part1.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from collections import defaultdict
def parse_input(input):
graph = defaultdict(list)
for edge in input:
# print('--{}'.format(edge))
a,b = edge.split('-')
graph[a].append(b)
graph[b].append(a)
return graph
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if start not in graph:
return []
paths = []
for node in graph[start]:
if node not in path or node.isupper():
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
def main():
example = """start-A
start-b
A-c
A-b
b-d
A-end
b-end""".splitlines()
example2="""dc-end
HN-start
start-kj
dc-start
dc-HN
LN-dc
HN-end
kj-sa
kj-HN
kj-dc""".splitlines()
with open("input.txt") as infile:
input = [line.strip() for line in infile]
graph_example = parse_input(input)
paths = find_all_paths(graph_example, 'start', 'end')
print('paths:{}'.format(len(paths)))
if __name__ == '__main__':
main()