Advent of Code 2024: Day 11

For day 11, we are given a list of stones inscribed with numbers.

;;; -*- Lisp -*-

(in-package "ADVENT2024/DAY11")

(defun read-input (input-pathname)
  (collect ’list (scan-file input-pathname)))

On each blink (clock tick), we apply some rules to all the stones:

(defun digit-count (stone)
  (1+ (integer-log stone 10)))

(defun split-stone (stone)
  (let ((divisor (expt 10 (/ (digit-count stone) 2))))
    (multiple-value-list (floor stone divisor))))  ;; thanks Charlie McMackin

(defun apply-rules (stone)
  (cond ((zerop stone) (list 1))
        ((evenp (digit-count stone)) (split-stone stone))
        (t (list (* stone 2024)))))

The puzzle goes through the effort to ensure that you know that the stones are kept in order, but the fact is the order doesn’t matter at all. We can just keep track of the total number of stones of each value in a table. After each step, we collect all the stones with the same value and sum them up. Each stone will be represented by a stone-entry cons of the stone value and the number of stones with that value.

(defun coalesce (stone-alist)
  (let ((table (make-hash-table :test ’eql)))
    (dolist (stone-entry stone-alist table)
      (incf (gethash (car stone-entry) table 0) (cdr stone-entry)))))

So on each blink, we iterate over the table and apply the rules. Then we coalesce the results.

(defun blink (stone-table)
  (coalesce
   (multiple-value-bind (stone-values stone-counts) (scan-hash stone-table)
     (collect-append
      (#M(lambda (stone-value stone-count)
           (map ’list
               (lambda (new-stone) (cons new-stone stone-count))
               (apply-rules stone-value)))
         stone-values
         stone-counts)))))

The main loop is to simply call blink n times.

(defun initial-stone-table (initial-stones)
  (coalesce (map ’list (lambda (stone) (cons stone 1)) initial-stones)))

(defun blink-n (initial-stones n)
  (do ((stone-table (initial-stone-table initial-stones) (blink stone-table))
       (generation 0 (1+ generation)))
  ((>= generation n)
   (collect-sum (multiple-value-bind (stones counts) (scan-hash stone-table)
                   counts)))))

(defun part-1 ()
  (blink-n (read-input (input-pathname)) 25))

(defun part-2 ()
  (blink-n (read-input (input-pathname)) 75))

This problem took me a moment until I realized that the order of the stones didn’t matter. If you try to keep the stones in order, you end up with an exponential explosion of stones.