blob: 149749e309878da77e470f2b52f9ea200bfa1743 (
plain)
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
|
from collections import deque
def parseInput(contents):
edges = [l.split("-") for l in contents.strip().split("\n")]
edges_set = set([])
for (f, t) in edges:
edges_set.add((f, t))
if t != "end" and f != "start":
edges_set.add((t, f))
return edges_set
def visitableNeighbours(edges, path, doubleVisited):
curr = path[0]
banned = [e for e in path if e.islower()] if doubleVisited else ["start"]
for (f, t) in edges:
if f == curr and t not in banned:
yield t
edges = parseInput(open("./input").read())
locs = deque() # each element is a tuple of (double visited, list of all the visited nodes)
finished = set()
locs.append((False, ["start"]))
while len(locs) > 0:
doubleVisited, path = locs.pop()
if path[0] == "end":
finished.add("-".join(path))
else:
for neighbour in visitableNeighbours(edges, path, doubleVisited):
locs.append((doubleVisited or (neighbour.islower() and neighbour in path), [neighbour] + path))
|
