Module advent_of_code_2021::day_12 [−][src]
Expand description
This is my solution for Advent of Code - Day 12 - Passage Pathing
Today was graph traversing. The puzzle was to find all the paths to traverse a set of caves, some of which could be visited any number of times (large), and only once-ish (small). I say ish, because part two’s extension was that exactly one (1) small cave could be revisited in the path. I’ve previously struggled with graph representation in Rust, and today was tricky, but I was able to apply the learnings from previous years and get the borrow checker happy pretty quickly. This was a more impressive feat with my original solution that used the string representation and a hash map rather than a vector and mapping the labels to indices.
There are two main structs used in today’s solutions. Cave represents a node in the graph, tracking if it is
large or small (or one of the special types start and end), and the other cave(s) linked to that cave.
parse_input takes the puzzle input and converts it into a Vec<Cave>, using get_index to manage the
mapping of label -> index. Path tracks an in progress path using a set of the visited nodes (using a usize
as a bitmap), the current position of the head of the path, and (for part two) a flag tracking whether it has used
its one-off repeat visit.
build_paths and Path::with_cave handle the logic for solving both parts. build_paths taking a flag to
control which part it is solving. The strategy is to have a stack of paths to analyse, pop one at a time, append
each linked cave to that path in turn using Path::with_cave, and push the valid paths into the completed list
if we’ve appended ‘end’, otherwise back onto the stack of pending paths - so doing depth first search. Using a
queue would give breadth first search, but it’s a moot point as we need the exhaustive list of paths anyway.
Today was the worst in terms of initial performance. It was taking ~400ms to run both parts, compared to ~100ms
to run all of days 1 to 11. My initial implementation was using a HashSet<&str> for the visited nodes, and a
HashMap<&str, Cave> for the cave list. Switching this over to a usize bitmap, and Vec<Cave> brought it down
to ~130ms, better but still slower than the other days combined. The second optimisation was that I had
previously been tracking the full path up to that point as a Vec<usize> (originally Vec<&str>.) Because the
paths branch, adding a new cave to a path needs to copy it, so the original is left as is to have the next linked
cave appended. This had been useful for debugging, esp. when it was using &strs to track the caves, but wasn’t
actually needed to calculate the solution - the visited set and current position are sufficient. Removing this
Vec and associated copying brought it down to ~10ms 🎉. I was very glad for the unit tests that let me refactor
each step with confidence. Getting Path::with_cave right took a few attempts, and the tests quickly helped me
identify where I’d gone wrong.
Structs
Represents a node (cave) in the graph (cave system)
Represents a path from the start to the node at Path::position.
Enums
Track the four possible node types that dictate how they can be visited
Functions
Find the start and end indices, initialise a single path at the start position, and an empty list of complete paths. Take nodes from the stack, iterating through the linked caves and pushing all valid new paths back onto the stack (if incomplete) or into the list of complete paths if their updated position is the end node, repeat until the stack is exhausted and return the completed path.
Helper for parse_input that handles mapping a label to an index in the cave vector, initialising a cave and dding it to the vector and lookup table if it’s a new cave.
Split each line into the two ends of the edge, lookup/create the cave for each, and add each to the opposite end’s list of links.
The entry point for running the solutions with the ‘real’ puzzle input.