53 lines
1.1 KiB
Python
53 lines
1.1 KiB
Python
class Node(object):
|
|
def __init__(self, name):
|
|
self.name = name
|
|
self.links = []
|
|
self.small = self.name == self.name.lower()
|
|
|
|
def __repr__(self):
|
|
return "<{}>".format(self.name)
|
|
|
|
|
|
nodes = {}
|
|
|
|
|
|
# with open("sample.txt") as f:
|
|
with open("input.txt") as f:
|
|
for line in f.readlines():
|
|
a, b = line.strip().split("-")
|
|
if a not in nodes:
|
|
nodes[a] = Node(a)
|
|
if b not in nodes:
|
|
nodes[b] = Node(b)
|
|
nodes[a].links.append(nodes[b])
|
|
nodes[b].links.append(nodes[a])
|
|
|
|
|
|
paths = []
|
|
|
|
|
|
def step(node, path, visited):
|
|
# append node to the path
|
|
path.append(node)
|
|
|
|
# if we just hit the end, emit the path
|
|
if node.name == "end":
|
|
paths.append(path)
|
|
return
|
|
|
|
# append node to visited
|
|
if node.small:
|
|
visited.update([node.name])
|
|
|
|
# look for legal next nodes
|
|
legal = [n for n in node.links if n.name not in visited]
|
|
|
|
# call step for each
|
|
for next_step in legal:
|
|
step(next_step, path[:], set(visited))
|
|
|
|
|
|
step(nodes["start"], [], set())
|
|
|
|
print(len(paths))
|