Advent of Code 2024: Day 18

For day 18, we have a maze again, but this time the input is given as coordinate pairs of where the walls go. The start and goal are the upper left and lower right respectively.

(in-package "ADVENT2024/DAY18")

(defun read-input (file grid n-bytes)
  (iterate ((coord (#M(lambda (line)
                       (apply #’coord (map ’list #’parse-integer (str:split #\, line))))
                      (cotruncate (scan-file file #’read-line)
                                  (scan-range :below n-bytes)))))
    (setf (grid-ref grid coord) ’\#))
  (setf (grid-ref grid (coord 0 0)) ’|S|)
  (setf (grid-ref grid (coord (1- (grid-height grid)) (1- (grid-width grid)))) ’|E|))

(defun sample-input ()
  (let ((grid (make-array (list 7 7) :initial-element ’|.|)))
    (read-input (sample-input-pathname) grid 12)
    grid))

(defun input (n-bytes)
  (let ((grid (make-grid 71 71 :initial-element ’|.|)))
    (read-input (input-pathname) grid n-bytes)
    grid))

The bulk of the solution simply reuses the Dijkstra’s algorithm from day 16. I won’t reproduce the code here. We just adjust the path scorer to not penalize for turns.

For part 1, we load the first 1024 walls and find a shortest path.

(defun part-1 ()
  (let* ((grid (input 1024))
         (solutions (solve-maze grid)))
    (score-path (car solutions))))

For part 2, we want to find the first wall in the list of walls that prevents us from reaching the goal. Binary search time.

(defun total-walls ()
  (collect-length (scan-file (input-pathname) #’read-line)))

(defun binary-search (pass fail)
  (if (= (1+ pass) fail)
      (list pass fail)
      (let* ((mid (floor (+ pass fail) 2))
             (grid (input mid)))
        (let ((solutions (solve-maze grid)))
          (if (null solutions)
              (binary-search pass mid)
              (binary-search mid fail))))))

(defun get-coord (n)
  (collect-nth n (scan-file (input-pathname) #’read-line)))

(defun part-2 ()
  (collect-nth (car (binary-search 1024 (total-walls)))
  (scan-file (input-pathname) #’read-line)))