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)))))
