aoc2019 day10

aoc2019-day10.lisp

;;;; +----------------------------------------------------------------+
;;;; | Advent of Code 2019                                            |
;;;; +----------------------------------------------------------------+

(defpackage #:snippets/aoc2019/day10
  (:use #:cl)
  (:export
   #:day10))

(in-package #:snippets/aoc2019/day10)

(defun parse (input)
  (let* ((width (position #\Newline input))
         (height (ceiling (length input) (1+ width)))
         (grid (make-array (list height width) :initial-element nil)))
    (loop with x = 0
          with y = 0
          for char across input
          do (ecase char
               (#\.
                (incf x))
               (#\#
                (setf (aref grid y x) t)
                (incf x))
               (#\Newline
                (setf x 0)
                (incf y))))
    grid))

(defun vec (x y)
  (complex x y))

(defun vx (vec)
  (realpart vec))

(defun vy (vec)
  (imagpart vec))

(defconstant angle-precision 100)

(defun angle (v)
  (mod
   (truncate
    (* (phase v)
       (/ 180 pi)
       angle-precision))
   (* 360 angle-precision)))

(defun mag (v)
  (abs v))

(defmacro do-asteroids ((loc grid) &body forms)
  (let ((x (gensym))
        (y (gensym))
        (gridvar (gensym)))
    `(let ((,gridvar ,grid))
       (dotimes (,y (array-dimension ,gridvar 0))
         (dotimes (,x (array-dimension ,gridvar 1))
           (when (aref ,gridvar ,y ,x)
             (let ((,loc (vec ,x ,y)))
               ,@forms)))))))

(defun find-best (grid)
  (let ((max -1)
        (best-loc nil)
        (best-others nil))
    (do-asteroids (loc grid)
      (let ((others (make-hash-table)))
        (do-asteroids (loc2 grid)
          (unless (= loc loc2)
            (push loc2 (gethash (angle (- loc2 loc)) others))))
        (let ((n (hash-table-count others)))
          (when (> n max)
            (setf max n)
            (setf best-loc loc)
            (setf best-others others)))))
    (values best-loc best-others)))

(defun sort-by-distance (others loc)
  (loop for a being each hash-key of others
        using (hash-value list)
        do (setf (gethash a others)
                 (sort list #'< :key (lambda (v) (mag (- v loc)))))))

(defun vaporize (loc others n)
  (sort-by-distance others loc)
  (loop
   (let ((old-n n))
     (loop for i from 0 below (* 360 angle-precision)
           for a = (mod (- i (* 90 angle-precision))
                        (* 360 angle-precision))
           do (symbol-macrolet ((in-line (gethash a others)))
                (when in-line
                  (let ((unlucky (pop in-line)))
                    (when (zerop (decf n))
                      (return-from vaporize unlucky))))))
     (when (= old-n n)
       (error "Too few asteroids?")))))

(defun answer (loc)
  (+ (* (vx loc) 100)
     (vy loc)))

(defun day10 (input)
  (multiple-value-bind (loc others) (find-best (parse input))
    (list (hash-table-count others)
          (answer (vaporize loc others 200)))))