Last modified: 2023-12-11 @ a185fa7

# Advent of Code 2023: Day 08

*This post is part of a series: Advent of Code 2023*

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 ^{1}. 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.

I’m assuming that an

`Option<usize>`

takes up 8 bytes, the same as a`usize`

. This is probably not strictly true, but it’s good enough for me. I could have used a sentinel value like`usize::MAX`

for`None`

instead to achieve the same result. ↩︎