Day 8 — The Haunted Wasteland

After playing cards on the camel’s back, Day 8 starts with a sandstorm approaching, and you have to figure out how to get out of the desert. If only you had a map!

Luckily, you find a pouch called "Maps", which contains a bunch of documents. One document has a list of directions to turn (left or right), while the others describe has a list of nodes and how they connect to other nodes. Each node connects to two others — one by heading left, and one by heading right. There are two special nodes — AAA which is where you start, and ZZZ which is the way out.

Starting at the node marked AAA, follow the left and right turn directions to find the next node to travel to. Keep doing that until you finally get to ZZZ. If you run out of left/right turn directions before you get to ZZZ, just keep repeating that sequence until you do.

Given this info, you are to find how many steps it takes to get from AAA to ZZZ.

Approach

This one was an exercise in storing the data in a decent format.

It may be tempting to see the fact that each node connects to two other nodes and try to use a binary tree, but that runs into issues quickly. The big problem is that while a node connects out left or right to other nodes, it may also be connected in from other nodes.

In fact, what this data represents is a graph, which is a list of nodes and the connections between them. Nodes in a graph can connect to an arbitrary number of other nodes, unlike a binary tree. There are a few ways to represent a graph in memory, but the input you are given is a pretty decent representation of the adjacency list implementation.

Adjacency Lists

In an adjacency list, each node contains a list (or array or Vec) of the nodes to which it connects. Because each node has a way to identify it in the graph (in this case, a three letter name, like AAA), these identifiers are used in the list to indicate connections from one node to another.

As mentioned above, each node in a graph can connect to as many other nodes as it wants. However, for this problem, the connections are limited and constrained to exactly two connections — one to the left, and one to the right.

Most graph implementations give you a standard way to add, remove, and modify nodes and their connections. Again, that is unnecessary for this problem, so we can have a much simpler implementation that doesn’t require us to modify the nodes at all.

So what does that all mean? Each node can be represented by a string, and its connections with a tuple. For folks who know Python, a tuple in Rust is similar. It is a sequence of values that do not need to be of the same type. Tuples cannot grow or shrink in size, which makes them perfect for this application.

Implementation

Because all I need to track for each node is its name, and a tuple with the names of the two connecting nodes, I decided to use a HashMap<String, (String, String)>. As each line of input was read from lines, I added a new entry to the HashMap<>:

// Setup the hash map for the elements
let mut elements: HashMap<String, (String, String)> = HashMap::new();

// Parse each line
for line in &lines[2..]{
    let split: Vec<_> = line
        .split(&[' ', '=', '(', ')', ','])
        .into_iter()
        .filter(|&s| s != "")
        .collect();

The first element in the tuple is the left connection, and the second is the right.

I’ve also saved the right and left directions in a String called instructions.

Once I have elements graph built, I find the node labelled AAA and make that the current_element. I set step = 0 to count the number of steps taken, and note which instruction I am on. Then I start a loop:

While current_element != "ZZZ"
- Get the current turn from instructions.
- Get the adjacency list as next_elements = elements.get(&current_element).
- Pick the next element based on the current turn (either next_elements.0 or next_elements.1).
- Increment step, and move to the next turn.

When the loop ends, step has the answer we are looking for.

Part 2

Of course, you’re not getting out of the desert that easy. You follow the directions, but you aren’t any closer to leaving the desert.

However, it turns out the desert is filled with ghosts — I know, the contest has an XMas theme, but now it also has a surprise Tim Burton movie twist!

Like I said, the desert has ghosts, and they know how to follow the maps to find the way out. The thing is, ghosts can move in many different directions at the same time — in fact, they can follow all the viable paths out of the desert. They also have different ways to figure where each viable path starts and where it ends…

Ghosts start at every node that ends with A, so AAA, BSA, 11A, etc. They follow every path from all these starting points simultaneously, turning left or right as directed from each new node they reach. There are several nodes that end with A in the sample data, as well as the real data.

They also don’t stop until all the paths they follow end at a node which ends with Z, like ZZZ, 11Z, and so on. Again, there are several of these ending nodes — in fact, there are an equal number of ending nodes as there are beginning nodes.

Following ghost logic of following every viable path until they all find a viable end at the same time, how many steps will it take to get out of the desert?

Part 2 Approach

The key thing here is that all the ghost paths must end simultaneously. You can track all the paths simultaneously using the part one code. However, none of us will be alive to see it finish — my final answer was somewhere in the 14 trillion step range — at one step per millisecond, it would take 444 years or so. If we could calculate a step per microsecond, it would only take 6 months or so, but still, no one has that kind of time.

However, I noticed something in the sample data provided, which had two starting points:

One path with a length of two steps.
The other path with a length of three steps.

The final answer for the sample was six steps, which was the product of each path’s length. Could that be a clue to finding the right answer? I certainly thought so.

To test this, I identified each starting point which ended with A, and ran each path through my part 1 algorithm until each reached a node which ended with Z, saving each path length. I then multiplied all those path lengths together to get my final answer.

Which was the wrong answer.

OK, so I need some more analysis.

I took another example, this time with three paths:

One path with a length of two steps.
One path with a length of three steps.
One path with a length of four steps.

Using my first guess algorithm, I multiply all those together and get $2\times\ 3\times\ 4 = 24$, which I know is wrong.

While all these paths certainly all end after 24 steps, it’s not the first time when all these paths land on a Z node.

They all land on a Z node first after only 12 steps. It turns out that 12 is the least common multiple of these three numbers.

Least Common Multiple

While there maybe a good library that has a least common multiple function in it, it’s not that hard to write one yourself.

The least common multiple (or LCM) of two numbers is the product of those numbers divided by the greatest common divisor (or GCD) of those two numbers. So first, you need to figure out the GCM.

Luckily, a gifted Greek mathematician named Euclid came up with a brilliant algorithm for figuring this out back around 300 BCE. Of course, he didn’t know Rust, so this is my interpretation of his algorithm, in just a few lines of code:

fn gcd(x: u64, y:u64) -> u64{
    // Which number is bigger
    let mut max = x;
    let mut min = y;
    if min > max {
        let val = max;
        max = min;
        min = val;
    }

    // Find the GCD
    loop {
        let res = max % min;
        if res == 0 {
            return min;
        }

        max = min;
        min = res;
    }
}

The first part of the code just figures out which of the two numbers is bigger.

After that, we start a loop, which gets the remainder of dividing max by min in res.

If it’s $res = 0$, then min is already the greatest common divisor, and we return min as the answer.
Otherwise, we recognize that res must be smaller than both max and min. So, we loop again, this time with max = min and min = res.

You can see how this works with two numbers, 12 and 9:

$12 \mod\ 9 = 3$
$9 \mod\ 3 = 0$

The GCD of 12 and 9 is 3.

It even works for primes — take 7 and 5:

$7 \mod\ 5 = 2$
$5 \mod\ 2 = 1$
$2 \mod\ 1 = 0$

Which tracks, since primes are only divisible by themselves and 1.

Anyway, once we know the GCD, we can use that to figure out the LCM:

fn lcm(x: u64, y:u64) -> u64{
    x*y / gcd(x,y)
}

That’s it.

So the new algorithm for part 2 is to run each ghost path separately and save the length. Then, taking them two at a time, I compute the least common multiple. When I’ve handled each, I have the final — and this time, correct — answer.

Summary

My code is here, if you want to comment or make suggestions!

For part 2, I could have used a different greatest common divisor calculation — the binary GCD algorithm replaces the divisions and modulo with binary shifts, which are easier and faster to compute, but trickier to grok for new coders.

That said, this algorithm runs relatively quickly, and is a clever combination of both math and data structures. Figuring out how to store data is usually the first step towards an efficient solution, and being able to apply my high school algebra was a nice twist (thanks Mrs. Cetorelli!)

Cogito Coders

I think (like a coder), therefore I am (a coder).

Day 8 — The Haunted Wasteland