Advent of Code 2024: Day 21

For day 20, we are entering a combination on a numeric keypad. But we cannot just enter the combination, we have to direct a robot to enter the combination by entering the directions to move the robot. But we cannot enter the directions directly, we have to get another robot to enter the directions to move the first robot. Part 1 of the problem has two layers of robots, but part 2 has a cascade of 25 layers of robots.

The door we need to unlock has a numeric keypad, but each robot has a directional keypad. The A key is an ’enter’ key.

;;; -*- Lisp -*-

(in-package "ADVENT2024/DAY21")

(defparameter *numeric-keypad* #2a(( 7  8  9)
                                   ( 4  5  6)
                                   ( 1  2  3)
                                   (nil 0  A)))

(defparameter *directional-keypad* #2a((nil |^| A)
                                       ( <  |v| >)))

(defun read-input (input-pathname)
  (collect ’list
    (#M(lambda (line)
         (collect ’list
           (#M(lambda (c)
                (or (digit-char-p c)
                    (intern (string c) (find-package "ADVENT2024/DAY21"))))
              (scan ’string line))))
       (scan-file input-pathname #’read-line))))

Given a keypad, we can find the coordinates of a key by scanning for it.

(defun key-coords (keypad key)
  (let ((coords (scan-grid-coords keypad)))
    (collect-first
     (choose
      (#Meql
       (#Mgrid-ref (series keypad) coords)
       (series key))
      coords))))

To move the robot arm, we’ll jog it vertically or horizontally by pressing keys on the directional keypad.

(defun jog-x (dx)
  (make-list (abs dx) :initial-element (if (minusp dx) ’< ’>)))

(defun jog-y (dy)
  (make-list (abs dy) :initial-element (if (minusp dy) ’|^| ’|v|)))

A valid two-dimensional jog must never go over the dead key.

(defun valid-jog? (keypad from jog)
  (let iter ((current from)
             (jog jog))
    (cond ((null (grid-ref keypad current)) nil)
          ((null jog) t)
          (t (iter (ecase (car jog)
                     (|^| (coord-north current))
                     (|v| (coord-south current))
                     (>   (coord-east  current))
                     (<   (coord-west  current)))
               (cdr jog))))))

Given the coords of a from key and a to key on a keypad, we can compute the ways to jog the arm from to to. There may be more than one way, so we return a list of the ways to jog the arm. Zig-zag jogging is never going to be optimal, so we omit that option.

(defun jog-xy (keypad from to)
  (let ((dx (jog-x (- (column to) (column from))))
        (dy (jog-y (- (row to) (row from)))))
    (cond ((null dx) (list dy))
          ((null dy) (list dx))
          (t (let ((column-first (append dx dy))
                   (row-first    (append dy dx)))
               (cond ((and (valid-jog? keypad from column-first)
                           (valid-jog? keypad from row-first))
                      (list column-first row-first))
                     ((valid-jog? keypad from column-first)
                      (list column-first))
                     (t (list row-first))))))))

In the general case, we’ll get a list of two possibilities. Either we move vertically first or we move horizontally first. One of these possibilities will lead to the shortest sequence of inputs. Oftentimes we can prune this to one possibility, e.g. we are keeping in the same row or column, or one possibility would take us over the dead key.

Instead of using coords, we would like to specify the key names.

(defun step-paths (keypad start-key end-key)
  (jog-xy keypad (key-coords keypad start-key) (key-coords keypad end-key)))

Given a target sequence we want a robot to enter into a keypad, we want to compute sequences on the robots directional keypad that we can enter to cause the robot to enter the target sequence. There will be multiple possibilities, and we want any of the shortest ones. Notice that last thing entered in a sequence is the A key, so we can assume the robot is starting from that key having pressed A in the prior sequence.

This is where we insert a memoization cache to control the combinatoric explosion that will occur when we cascade robots.

(defparameter seq-paths-cache (make-hash-table :test #’equal))

(defun seq-paths (keypad sequence)
  (if (eql keypad *numeric-keypad*)
      (seq-paths-1 keypad sequence)
      (let* ((key sequence)
             (probe (gethash sequence seq-paths-cache :not-found)))
        (if (eq probe :not-found)
            (let ((answer (seq-paths-1 keypad sequence)))
              (setf (gethash key seq-paths-cache answer) answer)
              answer)
            probe))))

(defun seq-paths-1 (keypad sequence)
  (cartesian-product-list
   (butlast (maplist (lambda (tail)
                       (cond ((null tail) nil)
                             ((null (cdr tail)) nil)
                             (t (revmap (lambda (jog)
                                          (append jog (list ’a)))
                                        (jog-xy keypad
                                                (key-coords keypad (first tail))
                                                (key-coords keypad (second tail)))))))
                     (cons ’a sequence)))))

Given the ultimate sequence we want to end up typing on the ultimate keypad, we want to move up through the cascade of robots generating meta sequences that drive the robot on the next level down. This produces a combinatoric explosion. But the puzzle doesn’t care about the actual sequence of keys, only that the number of keystrokes, is minimal, so we keep at each level the keystrokes for each target key, but we can ignore the order in which the robot presses the target keys. At each level of the robot cascade, we will know, for example, that we have to enter "move up, press A" some thirty-two times in total. This means that the robot one level up will have thirty-two copies of the "move left, press A, move right, press A" meta-sequence.

The meta sequences can be fragmented at each press of the A key and then we can count each fragment individually. So we only need to know the meta sequence for a handful of fragments to determine the number of keystrokes needed to enter a sequence. This is kept in our memoization table.

But there are multiple meta-sequences that can be expanded from a sequence. If they have different lengths, we want one of the shortest ones, but even among the shortest ones of the same length, the next level of expansion may produce meta-meta-sequences of different lengths. We can use a clever trick to prune the longer meta-meta-sequences. We pre-load the memoization cache to avoid returning alternatives that create large expansions two level up in the cascade. So now when we compute the meta-sequence we won’t compute so many alternative possibilities, but only possibilites that do not expand to longer solutions if run through the computation twice. There are eleven of these:

(defun preload-cache ()
  (clrhash seq-paths-cache)
  (setf 
   (gethash ’(|v| A)     seq-paths-cache) ’(((<  |v| A)   (^ > A)))
   (gethash ’( <  A)     seq-paths-cache) ’(((|v| < < A) (> > ^ A)))

   (gethash ’(|^|  >  A) seq-paths-cache) ’(((< A)     (|v| > A) (^ A)))
   (gethash ’(|v|  >  A) seq-paths-cache) ’(((< |v| A)     (> A) (^ A)))
   (gethash ’( >  |^| A) seq-paths-cache) ’(((|v| A)     (< ^ A) (> A)))
   (gethash ’( <  |^| A) seq-paths-cache) ’(((|v| < < A) (> ^ A) (> A)))
   (gethash ’( <  |v| A) seq-paths-cache) ’(((|v| < < A)   (> A) (^ > A)))

   (gethash ’(|v|  <   <  A) seq-paths-cache) ’(((< |v| A)     (< A)       (A) (> > ^ A)))
   (gethash ’( >   >  |^| A) seq-paths-cache) ’(((|v| A)         (A)   (< ^ A) (> A)))

   (gethash ’( >  |v| |v| |v| A) seq-paths-cache) ’(((|v| A)   (< A) (A)   (A) (^ > A)))
   (gethash ’(|v| |v| |v|  >  A) seq-paths-cache) ’(((< |v| A)   (A) (A) (> A) (^ A)))))

With the cache preloaded with these values, we always generate meta-sequences that have minimal keystrokes, but furthermore, the meta-meta-sequences will also have minimal keystrokes.

The rest of the file generates meta sequences up the cascade of robots.

(defun next-seq-tables (seq-table)
  (remove-duplicates (collapse-seq-tables (next-seq-tables-1 seq-table)) :test #’equal))

(defun collapse-seq-tables (seq-tables)
  (revmap #’collapse-seq-table seq-tables))

(defun symbol-lessp (left right)
  (string-lessp (symbol-name left) (symbol-name right)))

(defun term-lessp (left right)
  (or (and (null left) right)
      (and (null right) nil)
      (symbol-lessp (car left) (car right))
      (and (eql (car left) (car right))
           (term-lessp (cdr left) (cdr right)))))

(defun collapse-seq-table (seq-table)
  (let ((table (make-hash-table :test #’equal)))
    (dolist (entry seq-table)
      (let ((key (car entry))
            (count (cdr entry)))
        (incf (gethash key table 0) count)))
    (sort (hash-table-alist table) #’term-lessp :key #’car)))

(defun next-seq-tables-1 (seq-table)
  (if (null seq-table)
      (list (list))
      (let ((tail-tables (next-seq-tables-1 (cdr seq-table))))
        (extend-seq-tables (car seq-table) tail-tables))))

(defun extend-seq-tables (entry tail-tables)
  (revmappend (lambda (tail-table)
             (extend-seq-table entry tail-table))
           tail-tables))

(defun extend-seq-table (entry tail-table)
  (revmap (lambda (path)
            (extend-with-path path (cdr entry) tail-table))
          (seq-paths *directional-keypad* (car entry))))

(defun extend-with-path (path count tail-table)
  (append (revmap (lambda (term) (cons term count)) path)
          tail-table))

(defun seq-table-length (seq-table)
  (reduce #’+ (map ’list (lambda (entry) (* (length (car entry)) (cdr entry))) seq-table)))

The initial-paths-table takes the target numeric sequence and produces a table of the sequence fragments to enter that sequence. Order is not presevered.

(defun initial-paths-table (numeric-seq)
  (map ’list (lambda (path)
                (let ((table (make-hash-table :test #’equal)))
                  (dolist (term path (hash-table-alist table))
                    (incf (gethash term table 0)))))
       (seq-paths *numeric-keypad* numeric-seq)))

We generate the table for a generation by iteratively calling next-seq-tables until we reach the number of robots in the cascade.

(defun generation-table (n numeric-seq)
  (if (zerop n)
      (initial-paths-table numeric-seq)
      (revmappend #’next-seq-tables (generation-table (1- n) numeric-seq))))

(defun shortest-table (sequence-tables)
  (car (sort sequence-tables #’< :key #’seq-table-length)))

Finally, we can compute the complexity of the sequence by counting the number of keypresses in the shortest sequence and multiplying by the code in the sequence.

(defun complexity (code n-generations)
    (* (seq-table-length (shortest-table (generation-table n-generations code)))
       (fold-left (lambda (acc digit)
                    (if (eql digit ’a)
                        acc
                        (+ (* acc 10) digit)))
                  0
                  code)))

And we can compute the answer to part 1 and part 2 with a cascade of two robots and a cascade of twenty-five robots respectively.

(defun part-1 ()
  (reduce #’+ (map ’list (lambda (input) (complexity input 2)) (read-input (input-pathname)))))

(defun part-2 ()
  (reduce #’+ (map ’list (lambda (input) (complexity input 25)) (read-input (input-pathname)))))