Advent of Code 2024: Day 12

For day 12, we’re back to a grid of characters. Each character labels a region on the grid.

;;; -*- Lisp -*-

(in-package "ADVENT2024/DAY12")

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

We’re asked to find the area and perimeter of each region and the number of line segments in the perimeter. We use a flood-fill algorithm to find the area. If the flood-fill walks out of the region, we add 1 to the perimeter. The number of line segments in the perimeter is equal to the number of corners of the region, so we check for interior and exterior corners at each step.

(defun neighbors (coord)
   (list (coord-north coord)
         (coord-south coord)
         (coord-east coord)
         (coord-west coord)))

(defun flood-fill (grid visited seed-point)
  (let ((region-tag (grid-ref grid seed-point)))
    (flet ((in-region? (coord)
             (and (on-grid? grid coord)
                  (eql region-tag (grid-ref grid coord)))))
      (let itr ((points (list seed-point))
                (area 0)
                (perimeter 0)
                (corners 0))
        (if (null points)
            (values area perimeter corners)
            (let ((this-point (car points))
                  (rest-points (cdr points)))
              (cond ((not (in-region? this-point))
                     (itr rest-points area (1+ perimeter) corners))
                    ((grid-ref visited this-point)
                     (itr rest-points area perimeter corners))
                    (t
                     (setf (grid-ref visited this-point) t)
                     (itr (append rest-points (neighbors this-point))
                          (1+ area)
                          perimeter
                          (+ corners
                             (let ((n*  (in-region? (coord-north     this-point)))
                                   (ne* (in-region? (coord-northeast this-point)))
                                   (e*  (in-region? (coord-east      this-point)))
                                   (se* (in-region? (coord-southeast this-point)))
                                   (s*  (in-region? (coord-south     this-point)))
                                   (sw* (in-region? (coord-southwest this-point)))
                                   (w*  (in-region? (coord-west      this-point)))
                                   (nw* (in-region? (coord-northwest this-point))))
                               (+ ;; Concave corners
                                  (if (and n* e* (not ne*)) 1 0)
                                  (if (and e* s* (not se*)) 1 0)
                                  (if (and s* w* (not sw*)) 1 0)
                                  (if (and w* n* (not nw*)) 1 0)
                                  ;; Convex corners
                                  (if (and (not n*) (not e*)) 1 0)
                                  (if (and (not e*) (not s*)) 1 0)
                                  (if (and (not s*) (not w*)) 1 0)
                                  (if (and (not w*) (not n*)) 1 0))))))))))))))

To find seed points for regions, we scan the grid for points that are not visited. We rely on the series being pipelined so that the visited array is mutated as we process each region.

(defun scan-unvisited (visited)
  (declare (optimizable-series-function))
  (choose
   (mapping (((coord val) (scan-grid visited)))
     (and (null val) coord))))

To scan the regions, we flood fill the unvisited points.

(defun scan-regions (grid)
  (declare (optimizable-series-function 3))
  (let ((visited (make-array (array-dimensions grid) :initial-element nil)))
    (#3M(lambda (seed) (flood-fill grid visited seed))
     (scan-unvisited visited))))

To solve the puzzle, we scan the regions and apply the score function, summing the results.

(defun puzzle (grid score-function)  
  (collect-sum
   (mapping (((area perimeter segments) (scan-regions grid)))
     (funcall score-function area perimeter segments))))

Part 1 scores by multiplying the area by the perimeter.

(defun part-1 ()
  (puzzle (read-input (input-pathname))
          (lambda (area perimeter segments)
            (declare (ignore segments))
            (* area perimeter))))

Part 2 scores by multiplying the area by the number of segments in the perimeter.

(defun part-2 ()
  (puzzle (read-input (input-pathname))
          (lambda (area perimeter segments)
            (declare (ignore perimeter))
            (* area segments))))