Advent of Code 2023: Day 08

Code for solutions available on GitHub.

The next couple of posts are delayed and will be shorter because I have managed to catch covid, and am not in the best state to be solving puzzles or writing many words. However, I will still summarize the solutions here, albeit with less detail both word-wise and code-wise.

Haunted Wasteland

Today’s input consists of a list of a network of nodes, and their connections. Each node has a left connection and a right connection. The given example input looks like this:

RL

AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)

The first line is a sequence of steps to follow. The sequence repeats once it gets to the end, so we’re supposed to loop through these steps. Part 1 asks for the number of steps required to end up at node ZZZ, starting at node AAA.

A network of nodes seems like a graph theory problem, and usually an adjacency matrix is useful. However, in this case the graph is pretty sparse, each node only having two outgoing edges, so I opted for an adjacency list instead.

Each node is labelled with three letters, which can be interpreted as 3-digit base-26 numbers. A represents 0 and Z represents 26. So the adjacency list can be modelled by an array with 26^3 elements. Each element is then a pair of indices, left and right, pointing to the nodes connected to the node at that index.

type AdjacencyList = [[Option<usize>; 2]; 26 * 26 * 26];

The elements are arrays of length 2, which means L and R can be translated to 0 and 1 and used to index the elements. The elements contain Option<usize>s because not all 3-digit base-26 numbers are present in the input. Only around 750 in my case. This type takes up 8 * 2 * 26 * 26 * 26 bytes of memory, roughly 275 KiB ¹. Contrast this with an adjacency matrix, with some 1-byte enum representing left, right, and no connection. That would require (26 * 26 * 26)^2 bytes of memory, or roughly 300 MiB.

Anyway, once parsed into this type, and a cyclic iterator over the directions is created with Iterator::cycle, the problem is easily solved by starting at index 0, and following the directions to the next index until landing at index 26^3 (aka ZZZ, aka AdjacencyList::len() - 1).

Part 2

For part 2, it turns out that every node that ends with A (aka is a multiple of 26), there is a corresponding node that ends with Z (aka is one less than a multiple of 26). Starting at all nodes ending with A (multiples of 26), and following the directions for all of them simultaneously, how many steps until all paths have ended up at their corresponding node at the same time?

I fell into the rabbit hole pretty deep here. Trying to figure out questions like

• What if a path passes through multiple nodes ending with Z?
• What if two paths end up at the same node ending with Z?
• The paths must be cyclic for the problem to be solvable, how long does each path have to step until it falls into a cycle?

I investigated these questions and wrote some terrible code to try to account for it, which turned out to be unnecessary. All nodes ending with A are already in their loop from the start, and they do not pass through multiple nodes ending with Z. The solution is simply to find all the path lengths and – because the paths are all cyclic – compute their least common multiple.