End the War on Freedom

The wait to recharge a device is making it hard to sell devices to people uninterested in waiting around for a device to recover charge. Compounding the problem is the wait for those ahead in line to finish charging their devices. You’ve already been waiting for half an hour or longer to plug your device […]

The post Queuing Up For a Charge appeared first on EPautos - Libertarian Car Talk.

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))))

The time to fight hardest is when you’re winning. When the enemy is wobbly, that’s when you land the haymaker that puts him down for the count. That’s when you end him, if he’s an enemy bent on ending you. That moment is right now – as regards the federal regulatory apparat, which is the […]

The post Strike Now . . . Strike Hard appeared first on EPautos - Libertarian Car Talk.

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.