Advent of Code 2024: Day 8

Day 8 is another grid puzzle. We are given a map of antennas. Two antennas operate on the same frequency have the same ASCII character on the map. A “node” is a location on the map that is in line with two antennas of the same frequency and is twice as far from one antenna as the other. We are to count the nodes.

We can create an alist from antenna frequency to antenna locations by inverting the map:

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

(defun grid->antenna-list (grid)
  (hash-table-alist (invert-grid grid ’|.|)))

This solution makes use of first class functions. antinode-answer takes a function that produces an answer on one side of an antenna pair and applies it to the pair and swapped pair to produce answers on both sides.

(defun antinode-answer (antinode-half-answer)
  (lambda (grid left right)
    (append (funcall antinode-half-answer grid left right)
            (funcall antinode-half-answer grid right left))))

antinode-list takes a function that produces an answer for pair a single pair of antennas and maps it over all pairs of antennas on a frequency.

(defun antinode-list (antinode-answer)
  (lambda (grid node-list)
    (map-pairs (lambda (left right)
                 (funcall antinode-answer grid left right))
               node-list)))

All the antinodes can be obtained by invoking an antinode-list-generator over a set of node lists and appending the results.

(defun antinodes (antinode-list-generator)
  (lambda (grid node-list)
    (fold-left #’append nil
               (funcall antinode-list-generator grid node-list))))

So to solve the puzzle, we call an antinode generator on all the antennas.

(defun puzzle (grid antinode-generator)
  (length
   (remove-duplicates
    (fold-left (lambda (antinodes entry)
                 (append antinodes (funcall antinode-generator grid (cdr entry))))
               nil
               (grid->antenna-list grid))
    :test #’equal)))

In part 1, there is one node to the left and right of each pair, twice the distance from one antenna to the other.

(defun antinode (grid left right)
  (let* ((delta (2v- right left))
         (antinode (2v- left delta)))
    (when (on-grid? grid antinode)
      (list antinode))))

(defun part-1 ()
  (puzzle (read-grid (input-pathname))
          (antinodes (antinode-list (antinode-answer #’antinode)))))

For part two, the antinodes are at “resonant” points, i.e., spaced out equidistantly beyond the antenna pairs.

(defun resonant-antinodes (grid left right)
  (let* ((delta (2v- right left)))
    (do ((antinode left (2v- antinode delta))
         (answer ’() (cons antinode answer)))
        ((not (on-grid? grid antinode)) answer))))

(defun part-2 ()
  (puzzle (read-grid (input-pathname))
          (antinodes (antinode-list (antinode-answer #’resonant-antinodes)))))

Lisp was the first computer language to have first-class functions and lambda expressions.