blob: 7d87da7bd7152926bda17558efbdb385b219e6d9 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
from collections import defaultdict, deque
from itertools import groupby, 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]:
top = head + (neck,)
if sum(len(tuple(group)) - 1 for cave, group in groupby(sorted(top))
if cave.islower()) > 1: continue
queue.append(top)
print(sum(path[-1] == 'end' for path in paths))
|
