Haunted Wasteland

Advent of Code 2023 Day 8

Part 1

A zig-zag puzzle I'm totally down for

The puzzle input suggests a dictionary with 2-item lists as values...and that's exactly what I intend to use to solve Part 1.

A sense Part 2 will have something to do with altering the path instructions to find some sort of shortest path. Just my hunch.

But for now, let's get cracking!

Parsing the input with regex

To extract each three-letter alias from this string:

BBB = (AAA, ZZZ)

I should just need this regex:

/\w{3}/g

I checked my puzzle input to confirm each alias is exactly three letters long, too.

Converting directions to indices

I want to turn this:

RL

Into this:

10

Because those map directly to the indices of my soon-to-exist 2-element array values.

To do that, I use two replace method calls:

instructions.replaceAll('L', '0').replaceAll('R', '1')

Constructing the array-containing dictionary

In pseudocode:

For each line, accumulate a dictionary
  Assuming each line's first three-letter alias is a new one
    Add it as a key with the second and third three-letter aliases in first and second order of a 2-element array as value

In JavaScript:

nodes.split('\n').reduce((dict, node) => {
  let [first, second, third] = [...node.matchAll(/\w{3}/g)].map(el => el[0])
  dict[first] = [second, third]
  return dict
}, {})

Running that on the first example results in this beauty:

{
  AAA: [ 'BBB', 'CCC' ],
  BBB: [ 'DDD', 'EEE' ],
  CCC: [ 'ZZZ', 'GGG' ],
  DDD: [ 'DDD', 'DDD' ],
  EEE: [ 'EEE', 'EEE' ],
  GGG: [ 'GGG', 'GGG' ],
  ZZZ: [ 'ZZZ', 'ZZZ' ]
}

How should this loop look?

Thinking in pseudocode:

Set node to AAA

Set steps to 0

Current instruction is the remainder after dividing by the length of the instruction set, starting at position 0

Do as long as the destination node is not ZZZ
  Check the node at the position referenced by the instruction
    If it is not ZZZ
      Increment steps by 1
      Update node to the one referenced
      Update instruction by calculating the remainder after incrementing

Return steps

Things I should be careful of:

• Should steps start at 0 or 1?
• Should the condition for the loop be the array look-up or the selected node?

I'm sure I'll figure these out through trial and error while writing my program.

Writing and (re-)running the loop

After a slight hiccup with setting and updating the instruction, my working algorithm looks like this:

let node = 'AAA'
let steps = 0
let instruction = 0
while (node !== 'ZZZ') {
  node = nodes[node][instructions[instruction]]
  steps++
  instruction = (instruction + 1) % instructions.length
}

Will it generate the correct answer for my much longer puzzle input??

...

YES!!!!

Woohoo!

20k+ steps. Yeesh!

Ok, Part 2, which shortest-path, change-one-thing, performance-test wrench will you throw at me?

Huh?

Huh?

Part 2

Thankfully unmet expectations

• Multiple starting nodes
• Checking the same destination node in each one's list per the current instruction
• Only finish when all destination nodes ends in a Z

That seems pretty simple!

Finding the nodes that end in A

Create an empty list
For each key in nodes
  If it ends in A, add it to the list

In JavaScript:

let path = []
for (let node in nodes) {
  if (node[2] == 'A') {
    path.push(node)
  }
}

Using map() in a while loop

Set steps to 0

Do as long as all keys in path don't end in 'Z'
  Update each key in the path to the correct destination as determined by the current instruction
  Update the instruction
  Increment steps by 1

Return steps

In JavaScript:

let steps = 0
let instruction = 0
while (!path.every(el => el[2] == 'Z')) {
  path = path.map(node => nodes[node][instructions[instruction]])
  steps++
  instruction = (instruction + 1) % instructions.length
}
return steps

This program seemingly ran forever.

Waiting...

I needed a way to prove it was at least making some progress.

I added a print statement whenever the amount of node strings ending in Z was more than 0.

That revealed a ton of 1s and an occasional 2.

I wanted to see if it ever got as high as 3.

So I altered the condition for the print statement to > 2.

After letting the program run for a minute, I saw the first 3!

It continued to run.

3s were starting to print more regularly.

I let it run for almost 10 minutes!

Only 3s ever printed. Nothing higher.

I wanted to see:

• The list of nodes when there were 3 keys ending in Z
• The amount of steps that had passed
• Which instruction position was selected

Restarting and waiting several minutes, I saw a lot of this:

3 0

Apparently the list has three Z-ending nodes in it only when the instruction list reaches the beginning again.

More interesting, I could see all six Z-ending nodes, and which index they were at:

['SCZ', 'DDZ', 'ZZZ', 'PTZ', 'NQZ', 'GVZ']

How long is too long to wait?

I watched my program run for 45 minutes.

It has surpassed 2.3 billion steps.

There haven't been more than 3 nodes ending in Z in the path list.

3 of the 6 Z-ending nodes above are always in the list.

I'm ready to terminate my program.

What I think I learned

There must be a calculable recurring sequence length.

Summing up enough iterations of it will result in the correct answer.

Or, maybe it's about working backwards from the Z-ending nodes.

Identifying which nodes could get to them with the same instruction direction.

Another way in: start from the end

After studying my puzzle input, I noticed:

• Six nodes are the only ones with the Z-ending nodes in their 2-element arrays
• The Z-ending nodes are all in the second index

Maybe I could work backwards to determine enough of some path that is the only one to all Z-ending nodes.

It's worth a try!

Success...then sheer intimidation

I wrote an algorithm that performs a few iterations of walking back from the Z-ending nodes.

• The first iteration, it finds the six nodes that lead to the Z-ending nodes in all the same direction: clearly the correct last step
• The second iteration, it finds the six nodes that lead to those nodes in all the same direction: clearly the second-to-last step
• The third iteration, it finds 12 nodes that lead to those nodes, all in the same direction: two source nodes for each destination node, both going the same direction, so both are viable as a previous step
• Each subsequent iteration reveals twice as many nodes with the previous rounds' nodes as destinations, split in direction: if there are 24 nodes, half go in one direction and half go in another
• And on and on, doubling possibilities each iteration

There must be an algorithm that could explore each possible prior path, branching appropriately - perhaps through recursion - to determine which paths are dead-ends.

But I won't be writing it any time soon.

This is where Day 8 and I part ways.

Part 1 was fun to solve, though!

And Part 2 was fun to explore, inspect, analyze, and realize that I don't have the patience to persist.

Returning days later with a new strategy

That new strategy:

• Determine the lowest common multiple (LCM)

Of what?

Of the interval at which each of the six A-ending nodes reaches their respective Z-ending nodes.

Determining each interval

I already know the six starting nodes:

let path = []
for (let node in nodes) {
  if (node[2] == 'A') {
    path.push(node)
  }
}

Next, I want to confirm there is a repeating interval of steps for each node.

So, I'll process 100k steps for the first node and see what I get:

let node = path[1]
let stamps = []
while (steps < 100000) {
  if (node[2] == 'Z') stamps.push([node,steps])
  node = nodes[node][instructions[instruction]]
  steps++
  instruction = (instruction + 1) % instructions.length
}
console.log(stamps)

Running it shows me this array of arrays of node-step pairs:

[
  [ 'SCZ', 13939 ],
  [ 'SCZ', 27878 ],
  [ 'SCZ', 41817 ],
  [ 'SCZ', 55756 ],
  [ 'SCZ', 69695 ],
  [ 'SCZ', 83634 ],
  [ 'SCZ', 97573 ]
]

Thankfully, each subsequent second element is exactly the same amount away as the first one!

Running it on another node reveals the same truth, but with a smaller interval:

[
  [ 'DDZ', 11309 ],
  [ 'DDZ', 22618 ],
  [ 'DDZ', 33927 ],
  [ 'DDZ', 45236 ],
  [ 'DDZ', 56545 ],
  [ 'DDZ', 67854 ],
  [ 'DDZ', 79163 ],
  [ 'DDZ', 90472 ]
]

Awesome!

Now I need to find each node's interval and then calculate the least common multiple

At least, that's what I think will be the right answer.

My working algorithm

path.map(node => {
  let steps = 0
  let instruction = 0
  while (node[2] !== 'Z') {
    node = nodes[node][instructions[instruction]]
    steps++
    instruction = (instruction + 1) % instructions.length
  }
  return steps
})

That successfully generated a list of the six intervals at which each A-ending node reaches it's matching Z-ending node.

Cheating to find the LCM

At this point, I just want the number.

I'd rather not work through calculating myself.

Thankfully, this service calculates LCM for me

I pasted in my six numbers, pressed calculate, and generated a number in the trillions!

Turns out, it was the correct answer!!!

Woohoo!!!

Finally, some closure on this Day's puzzles.

I came away with two hard-earned stars!