"""
find all the paths. how to fully traverse a graph?
graph is made up of nodes
first node is "start"
nodes are either large or small
small nodes cannot be visited more than once
large nodes can be visited any number of times
find all the possible paths
rules:
- don't go back to start
- path ends at end
"""
from collections import defaultdict
from rich import print
input = """\
start-A
start-b
A-c
A-b
b-d
A-end
b-end"""
# input = """\
# dc-end
# HN-start
# start-kj
# dc-start
# dc-HN
# LN-dc
# HN-end
# kj-sa
# kj-HN
# kj-dc"""
# input = """\
# fs-end
# he-DX
# fs-he
# start-DX
# pj-DX
# end-zg
# zg-sl
# zg-pj
# pj-he
# RW-he
# fs-DX
# pj-RW
# zg-RW
# start-pj
# he-WI
# zg-he
# pj-fs
# start-RW"""
# input = """\
# ma-start
# YZ-rv
# MP-rv
# vc-MP
# QD-kj
# rv-kj
# ma-rv
# YZ-zd
# UB-rv
# MP-xe
# start-MP
# zd-end
# ma-UB
# ma-MP
# UB-xe
# end-UB
# ju-MP
# ma-xe
# zd-UB
# start-xe
# YZ-end"""
graph = defaultdict(set)
for line in input.splitlines():
node1, node2 = line.split("-")
graph[node1].add(node2)
graph[node2].add(node1)
# print(graph)
def traverse_graph():
# always start at start
paths = []
node_stack = [(["start"], n) for n in graph["start"]]
while len(node_stack) > 0:
path, node = node_stack.pop()
path.append(node)
if node == "end":
paths.append(path)
continue
new_nodes = graph[node].copy()
# we don't go back to start
new_nodes -= {"start"}
# if we're trying to visit a node of lowercase more than once we terminate that path
rem_nodes = set(n for n in new_nodes if n in path and n.islower())
new_nodes -= rem_nodes
if len(new_nodes) == 0:
continue
for n in new_nodes:
node_stack.append((path.copy(), n))
return paths
paths = traverse_graph()
# print(sorted(paths))
print(len(paths))
return_value = len(paths)