/
aoc_12c.py
29 lines (25 loc) · 852 Bytes
/
aoc_12c.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
from collections import defaultdict
WAYS = defaultdict(list)
with open('input_12.txt') as fin:
for line in fin:
x,y = line.strip().split('-')
WAYS[x].append(y)
WAYS[y].append(x)
def paths_to_end(history):
paths = 0
for target in WAYS[history[-1]]:
if target == 'end':
paths += 1
elif target.isupper() or target not in history:
history.append(target)
paths += paths_to_end(history)
history.pop()
elif not history[0] and target.islower() and target != 'start':
history[0] = True # visited some cave twice
history.append(target)
paths += paths_to_end(history)
history.pop()
history[0] = False
return paths
print(paths_to_end([True,'start']))
print(paths_to_end([False,'start']))