Advent of Code 2024: Day 4

Day 4 part 1 is your standard word search. First we read the grid of letters:

(defun read-input (input-pathname)
  (read-file-into-grid
    (char-interner #'char-upcase (find-package "ADVENT2024/DAY4"))
    input-pathname))

A “trace” is a row, column, or diagonal of letters. To search a trace for the word, we examine each suffix of the trace to see if starts with the word. We also check the reverse of the word:

(defun search-trace (trace target)
  (let ((rev (reverse target)))
    (collect-sum
     (#M(lambda (suffix)
          (if (or (starts-with-subseq target suffix)
                  (starts-with-subseq rev suffix))
              1
              0))
        (scan-suffixes trace)))))

Then we search all the traces:

(defun search-trace-list (trace-list target)
  (collect-sum
   (#M(lambda (trace)
        (search-trace trace target))
    (scan 'list trace-list))))

(defun search-grid (grid target)
  (collect-sum
   (#M(lambda (get-trace-list)
        (search-trace-list (funcall get-trace-list grid) target))
      (scan ’list
         (list (lambda (grid) (collect ’list (scan-rows grid)))
               (lambda (grid) (collect ’list (scan-columns grid)))
               (lambda (grid) (collect ’list (scan-falling-diagonals grid)))
               (lambda (grid) (collect ’list (scan-rising-diagonals grid))))))))

(defun part-1 ()
  (search-grid (read-input (input-pathname)) #(X M A S)))

Note that since scan-rows etc. and collect are macros, so we cannot pass them as first class functions. Instead we pass lambdas that call them so that the full macro expression is visible to the compiler.

For part 2, we are searching for Xs of “MAS” in the grid. We search for As, then check for M and S in the diagonals.

m-s1? is a helper function that checks if a pair of coords contains an M and an S.

(defun m-s1? (grid coord1 coord2)
  (and (on-grid? grid coord1)
       (on-grid? grid coord2)
       (eql (grid-ref grid coord1) 'M)
       (eql (grid-ref grid coord2) 'S)))

m-s? checks if a pair of coords contains an M and an S in any order.

(defun m-s? (grid coord1 coord2)
  (or (m-s1? grid coord1 coord2)
      (m-s1? grid coord2 coord1)))

x-mas? checks whether an A is surrounded by an M and an S.

(defun x-mas? (grid coord)
  (and (on-grid? grid coord)
       (eql (grid-ref grid coord) 'A)
       (and (m-s? grid (coord-northwest coord) (coord-southeast coord))
            (m-s? grid (coord-northeast coord) (coord-southwest coord)))))

Then we just count the occurrances:

(defun search-x-mas (grid)
  (collect-sum
   (#M(lambda (coord)
        (if (x-mas? grid coord)
            1
            0))
      (scan-grid-coords grid))))

(defun part-2 ()
  (search-x-mas (read-input (input-pathname))))