# Advent of Code 2023 - Day 8: Haunted Wasteland

::

 ```1 2``` ```#lang iracket/lang #:require racket (require "../advent.rkt") ```

Day 8 involves navigating binary trees, and modular arithmetic, but I’m getting ahead of myself. Here is our test input:

``````RL

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

The first line is a list of directives to choose either the left `L` or right `R` child of a pair. The other block of lines give keys and a pair of keys. Let’s parse the lines of the real input file as atoms:

 ```1 2 3``` ```(define lines (parse-aoc 8 atoms)) (for ([ line (take lines 5)]) (println line)) ```
``````'("LLRLLRLRLRRRLLRRRLRRLRLRLRLRLRLRRLRRRLRLLRRLRRLRRRLLRLLRRLLRRRLLLRLRRRLLLLRRRLLRRRLRRLRLLRLRLRRRLRRRLRRLRRLRRLRLLRRRLRRLRRRLLRRRLRLRRLLRRLLRLRLRRLRRLLRLLRRLRLLRRRLLRRRLRRLLRRLRRRLRLRRRLRRLLLRLLRLLRRRLRLRLRLRRLRRRLLLRRRLRRRLRRRLRRLRLRLRLRRRLRRLLRLRRRLRLRLRRLLLRRRR")
'()
'("TFN" "SMC" "LQT")
'("JKL" "XDN" "KPK")
'("JMF" "HGP" "QKF")``````

I’d like to parse the nodes into a `hash` with the value being a `cons` cell. This will allow retrieving the left value with `car` and the right value with `cdr`.

 ```1 2 3 4 5``` ```(define nodes (for/hash ([ lst (in-list (drop lines 2)) ]) (match-let ([ (list key left right) lst ]) (values key (cons left right))))) (writeln (hash-ref nodes "TFN")) ```
``("SMC" . "LQT")``

Since I’m representing the pairs as a `cons` cell, I’ll parse each `L` character to `car` and each `R` character to `cdr`, so I can use those directly to retrieve the values from the `cons` cells:

 ```1 2 3 4 5 6 7 8 9``` ```(define directions (~> (first lines) ; First line is a list of one string first ; First element of first line i.e. the string (string->list _) ; Convert to a list of characters (map (λ (c) ; Map each L to car and each R to cdr (match c [ #\L car ] [ #\R cdr ])) _))) (writeln (take directions 5)) ```
``(#<procedure:car> #<procedure:car> #<procedure:cdr> #<procedure:car> #<procedure:car>)``

Before coding the main `solve` function, let’s define the one helper function we’ll need. `ends-with?` accepts a suffix, and returns a predicate function indicating whether a string ends with the specified suffix:

 ```1 2 3``` ```(define ends-with? (curry (flip string-suffix?))) ((ends-with? ".") "I end in a period.") ```

`#t`

The `solve` function is straightforward. It accepts a `goal?` predicate and a starting `key`. It will then cycle through the `directions`, and do the following:

1. Retrieve the accessor function (`car` or `cdr`) from the `directions` list
2. Retrieve the `cons` cell from the `hash` associated with the key
3. `get` the left or right value from the `cons` cell (using `car` or `cdr`)
4. If the value satisfies the `goal?` predicate, return the number of `steps` we used
5. Otherwise, iterate by:
1. Set the key to the value we retrieved
2. Increment the number of steps
3. Retrieve the next direction (wrapping around to the beginning of the list if necessary)
 ```1 2 3 4 5 6 7``` ```(define (solve goal? key) (for/fold ([ key key ] [ steps 0 ] #:result steps) ([ get (in-cycle directions) ]) #:break (goal? key) (values (get (hash-ref nodes key)) (add1 steps)))) ```

Part 1 simply calls `solve` with a `goal?` predicate and a starting `key`:

 ```1 2 3 4``` ```(define (part1) (solve (ends-with? "ZZZ") "AAA")) (part1) ```

`20777`

For Part 2, we need to “simultaneously” navigate from multiple starting keys until they all satisfy the `goal?` predicate. This is a classic Advent of Code puzzle where the algorithm is cyclical in nature, and the naive approach would take far too long to run.

The trick is to recognize that each starting key will loop to the goal key every `N` steps, so we need to figure out the number of steps when they all sync up. For example, let’s say one key repeats every 2 steps, and another key repeats every 3 steps, when will they both reach the goal at the same time?

``````1  1
2  2   ; step 1
1  3   ; step 2
2  1   ; step 3
1  2   ; step 4
2  3   ; step 5
1  1   ; step 6``````

We see that after 6 steps, they’re both back to 1. The mathematical operation that represents this behavior is the “least common multiple”, or `lcm`. Here is a wikipedia article.

So, we need to compute the number of steps for each of the keys individually, and compute the `lcm` of all of the results. The algorithm is as follows:

• Line 2: get a list of all the keys in the `hash`
• Line 3: filter the list to only ones ending in “A”
• Line 4: for each key, call `solve` with a `goal?` of “ends with Z”
• Line 5: compute the `lcm` on the resulting list of steps
 ```1 2 3 4 5 6 7``` ```(define (part2) (~> (hash-keys nodes) (filter (ends-with? "A") _) (map (curry solve (ends-with? "Z")) _) (apply lcm _))) (part2) ```

`13289612809129`