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!

11AL -> 11BR -> 11Z 11AL -> 11BR -> 11Z11AL -> 11BR -> 11Z (6)

22AL -> 22BR -> 22CL -> 22Z 22AL -> 22BR -> 22CL -> 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

1. loop through each of the starting nodes, counting the hops until we land on a node ending with Z
2. 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