Advent of Code 2024: Day 20

For day 20, we return to a maze problem. The maze involved, however, is trivial — there are no decision points, it is just a convoluted path.

;;; -*- Lisp -*-

(in-package "ADVENT2024/DAY20")

(defun read-input (input-pathname)
  (read-file-into-grid
    (char-interner #’identity (find-package "ADVENT2024/DAY20"))
     input-pathname))

(defun find-start-and-goal (maze)
  (let ((inverse (invert-grid maze ’|.|)))
    (values (car (gethash ’S inverse))
            (car (gethash ’E inverse)))))

We compute the distance to the goal at all points along the path by walking the path backwards.

(defun compute-distances (maze)
  (let ((distances (make-grid (grid-height maze) (grid-width maze)
                              :initial-element nil)))
    (multiple-value-bind (start goal) (find-start-and-goal maze)
      (declare (ignore start))
      (let iter ((current goal)
                 (distance 0))
        (when current
          (setf (grid-ref distances current) distance)
          (iter (let* ((neighbors (#M2v+ (scan ’list (list +north+ +south+ +east+ +west+))
                                     (series current)))
                       (fill? (#M(lambda (maze neighbor)
                                   (and (on-grid? maze neighbor)
                                        (not (eql (grid-ref maze neighbor) ’\#))
                                        (null (grid-ref distances neighbor))))
                                 (series maze)
                                 neighbors)))
                  (collect-first (choose fill? neighbors)))
                (1+ distance))))
      distances)))

When we run through the maze we are allowed to cheat just once by walking through a wall. For part 1, we can walk just one step through a wall, but for part 2, we can walk up to 20 steps ignoring the walls. We might as well combine the two solutions into a single parameterized function. We will be asked to count the number of cheats that shorten the path by at least 100 steps.

I tried for quite some time to come up with a series oriented way to solve this, but it turned out to be much easier to just write a named-let iterative loop. So much for series.

First, we have a function that finds the cheats for a specific location. We are given a grid of distances to the goal, a coord that we start from, the current distance to the goal, the number of steps we can take through the walls, and the number of steps we have to shave off to count this cheat.

We iterate in a square grid centered at the current location and twice as wide plus one as the cheat steps. Check the locations in the distance grid that fall within the square and this tells us how much closer to the goal we can get by cheating to that location. We have to add in the manhattan distance from the current location to the cheat location to get the total distance. Subtract that from the original distance to the goal and we have the number of steps we save by using this cheat. If it exceeds our threshold, we count it.

(defun scan-square-coords (size)
  (declare (optimizable-series-function))
  (let ((displacement (coord size size)))
    (#M2v- (scan-coords (1+ (* size 2)) (1+ (* size 2)))
           (series displacement))))

(defun count-location-cheats (distances coord distance cheat-steps threshold)
  (collect-sum
   (choose
    (mapping (((cheat-vec) (scan-square-coords cheat-steps)))
      (let ((manhattan-distance (+ (abs (column cheat-vec)) (abs (row cheat-vec))))
            (cheat-coord (2v+ coord cheat-vec)))
        (and (<= manhattan-distance cheat-steps)
             (on-grid? distances cheat-coord)
             (let ((cheat-distance (grid-ref distances cheat-coord)))
               (and cheat-distance
                    (let* ((distance-if-cheating (+ manhattan-distance cheat-distance))
                           (savings (- distance distance-if-cheating)))
                      (and (>= savings threshold)
                           1))))))))))

So then we just iterate over the locations in the distance grid and call this function for each location, summing the results.

(defun count-cheats (distances-grid cheat-steps threshold)
  (collect-sum
   (choose
    (mapping (((coord distance) (scan-grid distances-grid)))
      (and distance
           (count-location-cheats distances-grid coord distance cheat-steps threshold))))))

For part 1, we can only take two steps through a wall.

(defun part-1 ()
  (count-cheats (compute-distances (read-input (input-pathname))) 2 100))

For part 2, we can take up to 20 steps through a wall.

(defun part-2 ()
  (count-cheats (compute-distances (read-input (input-pathname))) 20 100))