Day 8: Haunted Wasteland

https://adventofcode.com/2023/day/8

Classic AoC terrain today. We have a graph representation. Part 1 asks us to trace the path from the node ‘AAA’ to ‘ZZZ’ and count the steps.

First some house keeping – as it turns out, we’ll be dealing with large numbers, so let’s up our precision and index origin:

(⎕FR ⎕PP ⎕IO)←1287 34 0

Each node in the graph has two edges, left and right, and nodes are denoted by three upper-case letters. Let’s read the data.

data ← ⊃⎕NGET'8'1
(key left right) ← ↓⍉↑'[A-Z]+'⎕S'&'¨2↓data
ch ← left right

For part 1, all we need to do is to walk the graph following a set of left/right instructions, given in the first line of our data, repeating the instruction sequence if we need to.

[1] day8p1 ← { ⍺←0
[2]    dir ← 'R'=⍺⍺[(≢⍺⍺)|⍺]
[3]    elem ← (key⍳⊂⍵)⊃dir⊃ch
[4]    elem ≡ 'ZZZ': 1+⍺
[5]    elem ∇⍨ 1+⍺
[6] }

This is actually a monadic operator; occasionally a handy trick if you want to pass in another array. Here, ⍺⍺ is used for the instruction sequence. Line [3] follows either the left or right edge, as given by the current instruction.

      (⊃data)day8p1 'AAA'
12599

For part 2, we’re asked to simultaneously trace every node ending with an ‘A’ and find the first point where all these traces land on a node ending in ‘Z’. This isn’t computationally tractable to brute force. However, this is a fairly commonly occuring AoC problem style. The clue is that we are told to cycle the path instructions. Each trace will cycle with different periods, and we can find the conversion point using the lowest common multiple between the periods.

Our part two function is basically the same as our part one; only the recursion exit criterion differs:

day8p2 ← { ⍺←0
    dir ← 'R'=⍺⍺[(≢⍺⍺)|⍺]
    elem ← (key⍳⊂⍵)⊃dir⊃ch
    'Z'=⊢/elem: 1+⍺
    elem ∇⍨ 1+⍺
}

We now need to find all the start nodes, run this function over all of them, and then LCM the cycle periods:

    ∧/(⊃data)day8p2¨key/⍨'A'=⊢/¨key
8245452805243