aoc2020 day11

aoc2020-day11.lisp

;;;; +----------------------------------------------------------------+
;;;; | Advent of Code 2020                                            |
;;;; +----------------------------------------------------------------+

(defpackage #:snippets/aoc2020/day11
  (:use #:cl)
  (:export
   #:day11))

(in-package #:snippets/aoc2020/day11)

(defconstant empty #\L)

(defconstant occupied #\#)

(defun parse (input)
  (map 'vector #'copy-seq input))

(defun make-empty-grid (num-rows num-cols)
  (flet ((make-row ()
           (make-string num-cols :initial-element #\.)))
    (map-into (make-array num-rows) #'make-row)))

(defun num-rows (grid)
  (length grid))

(defun num-cols (grid)
  (length (aref grid 0)))

(defun cell (grid i j)
  (aref (aref grid i) j))

(defun (setf cell) (new-state grid i j)
  (setf (aref (aref grid i) j) new-state))

(defun cell-in-bounds-p (grid i j)
  (and (<= 0 i (1- (num-rows grid)))
       (<= 0 j (1- (num-cols grid)))))

(defun occupied-scanner (r)
  (lambda (grid i j)
    (let ((n 0))
      (dolist (di '(-1 0 1))
        (dolist (dj '(-1 0 1))
          (when (and (not (= di dj 0))
                     (send-ray grid i j di dj r))
            (incf n))))
      n)))

(defun send-ray (grid i j di dj r)
  (let ((ni (+ i di))
        (nj (+ j dj)))
    (cond ((zerop r) nil)
          ((not (cell-in-bounds-p grid ni nj)) nil)
          ((eql (cell grid ni nj) empty) nil)
          ((eql (cell grid ni nj) occupied) t)
          (t (send-ray grid ni nj di dj (1- r))))))

(defun state-transition (min-occupied)
  (lambda (state num-occupied)
    (cond ((and (eql state empty) (zerop num-occupied)) occupied)
          ((and (eql state occupied) (>= num-occupied min-occupied)) empty)
          (t state))))

(defun update (input output scanner transition)
  (let ((same t))
    (dotimes (i (num-rows output))
      (dotimes (j (num-cols output))
        (let* ((input-state (cell input i j))
               (num-occupied (funcall scanner input i j))
               (output-state (funcall transition input-state num-occupied)))
          (setf (cell output i j) output-state)
          (setf same (and same (eql input-state output-state))))))
    (not same)))

(defun simulate (input ray-radius min-occupied)
  (do ((output (make-empty-grid (num-rows input) (num-cols input)))
       (scanner (occupied-scanner ray-radius))
       (transition (state-transition min-occupied)))
      ((not (update input output scanner transition))
       input)
    (rotatef input output)))

(defun total-occupied (grid)
  (loop for row across grid
        sum (count occupied row)))

(defun day11 (input)
  (list (total-occupied (simulate (parse input) 1 4))
        (total-occupied (simulate (parse input) most-positive-fixnum 5))))