diff options
Diffstat (limited to 'AoC2022/15/solver.lisp')
| -rw-r--r-- | AoC2022/15/solver.lisp | 111 |
1 files changed, 59 insertions, 52 deletions
diff --git a/AoC2022/15/solver.lisp b/AoC2022/15/solver.lisp index 4a1f56b..3f35476 100644 --- a/AoC2022/15/solver.lisp +++ b/AoC2022/15/solver.lisp @@ -1,6 +1,7 @@ (ql:quickload '(fiveam str cl-ppcre arrows uiop iterate)) (use-package :iterate) +;; Obsolete drawing (defun grid (bounds) (destructuring-bind ((xmin xmax) (ymin ymax)) bounds (make-array (* (- xmax xmin -1) (- ymax ymin -1)) :initial-element 0 :element-type '(unsigned-byte 2)))) @@ -32,14 +33,7 @@ (3 "#")) out))) (get-output-stream-string out))) -(defun bounds (markers) - (list (list - (loop for (x . y) in markers minimize x) - (loop for (x . y) in markers maximize x)) - (list - (loop for (x . y) in markers minimize y) - (loop for (x . y) in markers maximize y)))) - +;; Actual problem (defun manhattan-dist (pos-sensor pos-beacon) (destructuring-bind ((sx . sy) (bx . by)) (list pos-sensor pos-beacon) (+ (abs (- bx sx)) (abs (- by sy))))) @@ -53,33 +47,6 @@ (map 'list #'parse-integer values)) nconc (list (cons sx sy) (cons bx by)))) - -(let* ((lines (uiop:read-file-lines "eg-in")) - (markers (markers lines)) - (bounds (bounds markers)) - (loc (in-grid bounds)) - (grid (grid bounds)) - (coords (from-grid bounds))) - (loop for ((sx . sy) (bx . by)) on markers by #'cddr - do (progn (setf (aref grid (funcall loc sx sy)) 1) - (setf (aref grid (funcall loc bx by)) 2))) - - (loop for (sensor beacon) on markers by #'cddr - for distance = (manhattan-dist sensor beacon) - do (loop - for elt across grid - and l from 0 - when (and (<= (manhattan-dist sensor (funcall coords l)) distance) (= elt 0)) - do (setf (aref grid l) 3))) - - (destructuring-bind ((xmin xmax) (ymin ymax)) bounds - (let ((stride (- xmax xmin -1))) - (princ (draw-grid grid stride)) - (loop repeat stride - for l from (* (+ 10 ymin) stride) - when (= 3 (aref grid l)) - count it)))) - (defun sensor-coverage (markers) (loop for (sensor beacon) on markers by #'cddr collect (list sensor (manhattan-dist sensor beacon)))) @@ -92,29 +59,43 @@ and minimize (- sx span) into left finally (return (list left right)))) -(arrows:-> - (markers (uiop:read-file-lines "eg-in")) - (sensor-coverage) - (sensor-range-on-row 10)) - -(equal (cons 5 2) (cons 5 2)) +(defun beacons-in-row (markers row) + (loop for (s (bx . by)) on markers by #'cddr + when (and (= row by) (not (member bx seenx))) + count by and collect bx into seenx)) (defun count-cover (markers target-row) - (let ((coverages (sensor-coverage markers)) - (beacon (delete-duplicates (loop for (s b) on markers by #'cddr collect b) :test #'equal))) + (let ((coverages (sensor-coverage markers))) (destructuring-bind (xmin xmax) (sensor-range-on-row coverages target-row) - (loop with y = target-row - for x from xmin to xmax - :count (loop for ((sx . sy) range) in coverages - :thereis (and (not (member (cons x y) beacon :test #'equal)) - (not (and (= x sx) (= y sy))) - (<= (manhattan-dist (cons sx sy) (cons x y)) - range))))))) + (- (loop with y = target-row + for x from xmin to xmax + :count (loop for ((sx . sy) range) in coverages + :thereis (and (not (and (= x sx) (= y sy))) + (<= (manhattan-dist (cons sx sy) (cons x y)) + range)))) + (beacons-in-row markers target-row))))) + +;; solution part 1 +(count-cover (markers (uiop:read-file-lines "eg-in")) 10) +(count-cover (markers (uiop:read-file-lines "input")) 2000000) +(defun bounds (markers) + (list (list + (loop for (x . y) in markers minimize x) + (loop for (x . y) in markers maximize x)) + (list + (loop for (x . y) in markers minimize y) + (loop for (x . y) in markers maximize y)))) + +(arrows:-> + (markers (uiop:read-file-lines "eg-in")) + (beacons-in-row 16) + ;; (delete-duplicates :key #'car) + ;; (sensor-coverage) + ;; (sensor-range-on-row 10) + ) -(count-cover (markers (uiop:read-file-lines "eg-in")) 10) -(count-cover (markers (uiop:read-file-lines "input")) 2000000) (defun overlap (a0 a1 b0 b1) "Test if [b0;b1] overlaps [a0;a1]" @@ -199,3 +180,29 @@ (loop for (x)) (make-array (* 4000000 4000000) :element-type '(unsigned-byte 1) :initial-element 0) + +(let* ((lines (uiop:read-file-lines "eg-in")) + (markers (markers lines)) + (bounds (bounds markers)) + (loc (in-grid bounds)) + (grid (grid bounds)) + (coords (from-grid bounds))) + (loop for ((sx . sy) (bx . by)) on markers by #'cddr + do (progn (setf (aref grid (funcall loc sx sy)) 1) + (setf (aref grid (funcall loc bx by)) 2))) + + (loop for (sensor beacon) on markers by #'cddr + for distance = (manhattan-dist sensor beacon) + do (loop + for elt across grid + and l from 0 + when (and (<= (manhattan-dist sensor (funcall coords l)) distance) (= elt 0)) + do (setf (aref grid l) 3))) + + (destructuring-bind ((xmin xmax) (ymin ymax)) bounds + (let ((stride (- xmax xmin -1))) + (princ (draw-grid grid stride)) + (loop repeat stride + for l from (* (+ 10 ymin) stride) + when (= 3 (aref grid l)) + count it)))) |