blob: 7ab0e56c05fcf75e99443ce175dc2eada17dd848 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
from collections import defaultdict, deque
from itertools import permutations
from sys import stdin
edges = defaultdict(list)
for line in stdin.read().strip().split():
for key, value in permutations(line.split('-')):
if key != 'end' and value != 'start': edges[key].append(value)
paths = set()
queue = deque([('start',)])
while queue:
if (head := queue.popleft()) in paths: continue
paths.add(head)
if (chin := head[-1]) == 'end': continue
for neck in edges[chin]:
if neck.islower() and neck in head: continue
top = head + (neck,)
queue.append(top)
print(sum(path[-1] == 'end' for path in paths))
|
