Advent of Code 2024: Day 10

For Day 10, we are given a topographic map as a grid of elevations.

;;; -*- Lisp -*-

(in-package "ADVENT2024/DAY10")

(defun read-grid (input-pathname)
  (read-file-into-grid #'char->decimal input-pathname))

The trailheads are at elevation 0.

(defun find-trailheads (grid)
  (gethash 0 (invert-grid grid)))

At any elevation, we can take a step to a neighboring cell if it is at 1 unit higher elevation.

(defun take-step (grid location)
  (let ((target-elevation (1+ (grid-ref grid location))))
    (collect 'list
      (choose-if (λ (loc)
                   (and (on-grid? grid loc)
                        (= (grid-ref grid loc) target-elevation)))
                 (scan 'list (list
                              (coord-north location)
                              (coord-east  location)
                              (coord-south location)
                              (coord-west  location))))))

The trail-walker is a trail collector that takes a trailhead and does a breadth-first search to find the highest elevations reachable from that trailhead.

(defun trail-walker (grid)
  (λ (trailhead)
    (collect-last
     (scan-fn 'list
              (λ () (list trailhead))
              (λ (frontiers)
                (remove-duplicates
                 (collect-append
                  (#Mtake-step (series grid) (scan frontiers)))
                 :test #'equal))
              #'null)))

A scorer is a curried function that takes a collector, then a grid, then a trailhead, and returns the score for that trailhead, which is the number of collected trails.

(defun scorer (collector)
  (λ (grid)
    (let ((collect-trails (funcall collector grid)))
      (λ (trailhead)
        (length (funcall collect-trails trailhead))))))

The puzzle takes a grid and a scorer, and sums the scores of the trailheads in the grid.

(defun puzzle (grid trailhead-scorer)
  (collect-sum
    (map-fn 'integer
            (funcall trailhead-scorer grid)
            (scan 'list (find-trailheads grid)))))

For the first part of the puzzle, we are to sum the scores of the trailheads using the trail-walker as the scorer. That is, for each trailhead, the number of highest points we can reach.

(defun part-1 ()
  (puzzle (read-grid (input-pathname)) (scorer #'trail-walker)))

For part two, we sum the number of paths to the highest points reachable from each trailhead. When we do the breadth-first search, we keep the history of the path we have taken.

(defun extend-path (grid path)
  (map 'list (λ (step) (cons step path)) (take-step grid (car path))))

(defun trail-collector (grid)
  (λ (trailhead)
    (collect-last
     (scan-fn 'list
              (λ () (list (list trailhead)))
              (λ (paths)
                (collect-append
                 (#Mextend-path
                    (series grid)
                    (scan 'list paths))))
              (λ (paths)
                (every (λ (path)
                         (= (length path) 11))
                       paths)))))

(defun part-2 ()
  (puzzle (read-grid (input-pathname)) (scorer #'trail-collector)))