Advent of Code 2023 - Day 8: Haunted Wasteland

:: programming, puzzle, racket

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