# 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:

- Retrieve the accessor function (
`car`

or`cdr`

) from the`directions`

list - Retrieve the
`cons`

cell from the`hash`

associated with the key `get`

the left or right value from the`cons`

cell (using`car`

or`cdr`

)- If the value satisfies the
`goal?`

predicate, return the number of`steps`

we used - Otherwise, iterate by:
- Set the key to the value we retrieved
- Increment the number of steps
- 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`