# Advent of Code 2023 — Day 8

Another fun one!

Today's puzzle had us navigating a sandstorm. Our map, a set of directions, through what looked like a graph.

Starting at `AAA`

, we want to get to `ZZZ`

following the `R`

, then `L`

item each iteration — starting from `R`

again if we've landed on a node that is not `ZZZ`

.

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

## Part 1

Given the above input, if we start at `AAA`

, then follow the right-most node, we land on `CCC`

. From `CCC`

, we need to follow the left-most node, which happens to be `ZZZ`

. So we're able to complete this in `2`

steps.

Our puzzle's test input does have needing to restart the loop of directions, as the first pass only gets us to `BBB`

, but a 2nd pass gets us to `ZZZ`

.

```
LLR
AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)
```

This puzzle has graphs written all over it. I didn't build a full graph class, but a tiny implementation using a Hash:

```
def build_graph(nodes)
nodes.each do |text_node|
node, left, right = text_node.scan(/(\w{3})/).flatten
insert_node(node)
add_edge(node, left)
add_edge(node, right)
end
end
def insert_node(node)
@nodes[node] = []
end
def add_edge(node1, node2)
@nodes[node1] << node2
end
def neighbors(node)
@nodes[node]
end
```

Then, we can prepare our graph from the puzzle input like so:

```
@nodes = {}
directions = input[0]
text_nodes = input.slice(2..-1)
build_graph(text_nodes)
```

This results in something like from our test input:

```
{
"AAA"=>["BBB", "BBB"],
"BBB"=>["AAA", "ZZZ"],
"ZZZ"=>["ZZZ", "ZZZ"]
}
```

With the `0th`

element being the left, and the `1st`

being the right.

Next, we want to loop over our directions until we land on `ZZZ`

.

```
current_node = "AAA"
hops = 0
while current_node != "ZZZ" do
directions.chars.each do |direction|
current_node = direction == "L" ? neighbors(current_node)[0] : neighbors(current_node)[1]
hops += 1
end
end
hops
```

To do this, we take each character, and find the next node based on if the character is an `L`

or an `R`

. We then repeat infinitely or until we land on `ZZZ`

, incrementing the number of hops with each loop.

This gets us our first star!

⭐️ Success!

## Part 2

Again, we take a closer look at our input.

This time, we find out that its meant for ghosts! And since ghosts don't follow any rules of physics, they're able to traverse multiple paths at once. What we want to know now is, starting from all nodes ending in `A`

, and travelling to the next node simultaneously, how many moves would need to be made before our ecoplasmic friends landed on all nodes ending in `Z`

.

This one seemed too easy, like there would be a gotcha waiting for us the moment we tried to run it.

I adjusted my solution slightly to start with `current_nodes`

(all nodes ending in `A`

) and map over them all, progressing the list of current nodes, then checking if all nodes ended in `Z`

.

Tests passed, first try — woo!

But the puzzle calculation was running for a while, and it kept running. I stopped it, added some logging to print the number of moves, and started again. For 10 mins, it was running, and got to a count of `~450,000,000`

. At this point I stopped and decided to rethink my solution.

In *theory*, once a ghost starts at say `11A`

, and ends on `22Z`

, the length of that path is known. When we start our loop again, we start at the start of our direction list, even if we ended on `22Z`

part way through our direction list.

So, given our test input:

```
LR
11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)
```

`11A`

-> `L`

-> `11B`

-> `R`

-> `11Z`

(2)`22A`

-> `L`

-> `22B`

-> `R`

-> `22C`

-> `L`

-> `22Z`

(3)

We find that following directions from `11A`

gets us to a node ending with `Z`

in 2 steps, and starting at `22A`

gets us to a node ending with `Z`

in 3 steps.

If we were to look at multiples for these numbers, we would find they intersect at `6`

:

```
2: 2, 4, 6, 8, ...
3: 3, 6, 9, 12, ...
```

This should mean that we would need to make 6 steps through our graph with each ghost to have them land on `11Z`

and `22Z`

at the same time. Let's try it!

`11A`

`L`

-> `11B`

`R`

-> `11Z`

`11A`

`L`

-> `11B`

`R`

-> `11Z`

`11A`

`L`

-> `11B`

`R`

-> `11Z`

(6)

`22A`

`L`

-> `22B`

`R`

-> `22C`

`L`

-> `22Z`

`22A`

`L`

-> `22B`

`R`

-> `22C`

`L`

-> `22Z`

(6)

Maybe better visualised with an image:

So now, instead of praying that we land on nodes ending with `Z`

all at once, we can instead perform 6 calculations through from `A`

to `Z`

(6 because in my starting input, there are 6 nodes that end with A), and then find the lowest common multiple amongst them all.

The setup is the same as part 1, so this is all that needs to change:

```
total_hops = start_nodes.map do |node|
hops = 0
while !node.end_with?("Z") do
directions.chars.each do |direction|
node = direction == "L" ? neighbors(node)[0] : neighbors(node)[1]
hops += 1
end
end
hops
end
total_hops.inject do |sum, number|
sum * number / sum.gcd(number)
end
```

- loop through each of the starting nodes, counting the hops until we land on a node ending with
`Z`

- find the lowest comment multiple, by using the greatest common divisor

⭐️ Success!

Code: https://github.com/dNitza/advent-of-code/tree/main/2023/08

## Performance

In doing some googling to see if I could speed up the lowest common multiple bit, I found that Ruby has a built in lowest common multiple method, which yielded almost identical performance.

```
day 08
├─ part 1 — 0.002344s
├─ part 2 — 0.012820s
╰─ part 2 (ruby lcm) — 0.012787s
```

in posts

Tagged