# AoC 2021 Day 12: Submarine Spider

### Source: Passage Pathing

#### Part 1: Given a list of edges in a bi-directional graph, count the number of paths from start to end such that nodes named with lowercase letters are visited once, and nodes with uppercase letters can be visited any number of times.

Interesting. First, let’s define a graph structure:

@dataclass(frozen=True)
class Node:
label: str

def is_big(self):
return self.label.isupper()

def __repr__(self):
return f'<{self.label}>'

@dataclass(frozen=True)
class Cave:
edges: Mapping[Node, Set[Node]]

@staticmethod
def from_file(file: TextIO):

edges: Dict[Node, Set[Node]] = {}

for line in file:
nodes = [Node(v) for v in line.strip().split('-')]

for node in nodes:
if node not in edges:
edges[node] = set()

for node_a in nodes:
for node_b in nodes:
if node_a != node_b:

# Convert to a dict
return Cave(edges)


Originally, I had the pathing function in this class directly, but because it changes for part 2, I extracted it into the part 1 function:

def part1(file: typer.FileText):
cave = Cave.from_file(file)

def paths(node: Node, visited: Set[Node]) -> Generator[List[Node], None, None]:
'''Yield all possible paths from the given node to <end>.'''

if node == END:
yield [END]
return

if node.is_small() and node in visited:
return

for next in cave.edges[node]:
for path in paths(next, visited | {node}):
yield [node] + path

count = 0
for _ in paths(START, set()):
count += 1

print(count)


Because the paths are short enough, we can get away with a simple recursive function. In this case, paths will take the current point in the graph and a list of nodes visited already (so that we can avoid lowercase nodes that we’ve already visited) and generate all paths from that point. It does so by recursion: each step is moving to a neighboring node in the graph, we’re assuming the recursive call will generate some number of paths (might be 0), and the base case is the end node.

Note: If there are ever two or more ‘big’ nodes adjacent to each other, this will totally blow up, since you can infinitely loop between the two. Good thing that doesn’t come up in our input. :D This could be fixed with cycle detection, but that would make teh algorithm somewhat slower…

$python3 submarine-spider.py part1 input.txt 4749  #### Part 2: Repeat Part 1, but you are allowed to visit a single lowercase node more than once (although you do not have to). Count the number of paths. Like I said, a tweak to the paths function: @app.command() def part2(file: typer.FileText): cave = Cave.from_file(file) def paths(node: Node, visited: Set[Node], used_double: bool) -> Generator[List[Node], None, None]: '''Yield all possible paths from the given node to <end>.''' if node == END: yield [END] return if node == START and START in visited: return if node.is_small() and node in visited and used_double: return for next in cave.edges[node]: for path in paths(next, visited | {node}, used_double or (node.is_small() and node in visited)): yield [node] + path count = 0 for _ in paths(START, set(), False): print(_) count += 1 print(count)  Yeah… it’s a fair bit more complicated this time, but with the code + comments, I think it makes sense. The most interesting is the last/any case. In that case, we have to check if we’ve already double visited a small node, because if so, we can’t do it again. Running it: $ python3 submarine-spider.py part2 input.txt
123054


Wow. That’s quite a lot more.

#### Performance

--- Day 12: Passage Passing ---

$python3 submarine-spider.py part1 input.txt 4749 # time 69264250ns / 0.07s$ python3 submarine-spider.py part2 input.txt
123054
# time 1300497125ns / 1.30s


So… that’s not the end of the world, but it’s still much slower than it could be. One thing that we should be able to is use memoization to ‘remember’ each path from a given point, so we can avoid computing them more than once. Unfortunately, that seems to mean that we cannot use a generator.

def part2_fast(file: typer.FileText):
cave = Cave.from_file(file)

@cache
def paths(node: Node, visited: FrozenSet[Node], used_double: bool) -> List[List[Node]]:
'''Yield all possible paths from the given node to <end>.'''

if node == END:
return [[END]]

if node == START and START in visited:
return []

if node.is_small() and node in visited and used_double:
return []

return [
[node] + path
for next in cave.edges[node]
for path in paths(next, visited | {node}, used_double or (node.is_small() and node in visited))
]

count = 0
for _ in paths(START, frozenset(), False):
count += 1

print(count)


Instead of the generator, we return the list of solutions, so we can functools.cache it. That’s pretty neat and a bit faster:

$python3 submarine-spider.py part2 input.txt 123054 # time 1300497125ns / 1.30s$ python3 submarine-spider.py part2-fast input.txt
123054
# time 564378250ns / 0.56s


It’s still doing a lot of messy list copying and appending. I think we could do better, but for now, it’s at least under a second…