diff options
Diffstat (limited to 'AoC2022/15/solver.lisp')
| -rw-r--r-- | AoC2022/15/solver.lisp | 123 |
1 files changed, 99 insertions, 24 deletions
diff --git a/AoC2022/15/solver.lisp b/AoC2022/15/solver.lisp index 3471b3b..4a1f56b 100644 --- a/AoC2022/15/solver.lisp +++ b/AoC2022/15/solver.lisp @@ -1,14 +1,5 @@ -(ql:quickload '(fiveam str cl-ppcre arrows uiop)) - - - -(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)))) +(ql:quickload '(fiveam str cl-ppcre arrows uiop iterate)) +(use-package :iterate) (defun grid (bounds) (destructuring-bind ((xmin xmax) (ymin ymax)) bounds @@ -41,6 +32,14 @@ (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)))) + (defun manhattan-dist (pos-sensor pos-beacon) (destructuring-bind ((sx . sy) (bx . by)) (list pos-sensor pos-beacon) (+ (abs (- bx sx)) (abs (- by sy))))) @@ -81,25 +80,95 @@ 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)))) + +(defun sensor-range-on-row (coverages target-row) + (loop for ((sx . sy) range) in coverages + for span = (- range (abs (- sy target-row))) + when (> span 0) + maximize (+ sx span) into right + 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 count-cover (markers target-row) - (let ((bounds (bounds markers)) - (max-distance (loop for (sensor beacon) on markers by #'cddr - maximize (manhattan-dist sensor beacon)))) - (destructuring-bind ((xmin xmax) ys) bounds - (declare (ignore ys)) + (let ((coverages (sensor-coverage markers)) + (beacon (delete-duplicates (loop for (s b) on markers by #'cddr collect b) :test #'equal))) + (destructuring-bind (xmin xmax) (sensor-range-on-row coverages target-row) (loop with y = target-row - for x from (- xmin max-distance) to (+ xmax max-distance) - :count (loop for (sensor beacon) on markers by #'cddr - :thereis (and (not (equal beacon (cons x y))) - (not (equal sensor (cons x y))) - (<= (manhattan-dist sensor (cons x y)) - (manhattan-dist sensor beacon)))))))) + 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))))))) (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]" + (and (<= a0 b1) (<= b0 a1))) + +(set-) + +(loop with intervals = nil + for ((sx . sy) beacon) on markers by #'cddr + for cover = (max 0 (- (manhattan-dist sensor beacon) (abs (- sy 11)))) + + do (let ((l (- sx cover)) + (r (+ sx cover))) + (cond + ((some (lambda (int) (overlap l r (car int) (cdr int))) intervals) + ))) + + maximize into max + minimize into min + finally (return (cons min max)) + ) + + +(defun coverage-edge (sensor coverage low high) + (destructuring-bind (x . y) sensor + (let ((edge (1+ coverage))) + (arrows:-<> + (loop for cx from (- x edge) to (+ x edge) + collecting (cons cx (- y (- edge (abs (- x cx))))) + collecting (cons cx (+ y (- edge (abs (- x cx)))))) + (delete-if-not (lambda (point) + (and (<= low (car point) high) + (<= low (cdr point) high))) + <>) + (delete-duplicates <> :test #'equal))))) + + +(defun fail-freq-edge (markers bound) + (let ((sensor-coverage (sensor-coverage markers))) + (loop for (sensor coverage) in sensor-coverage + :for candi = (loop for edge-point in (coverage-edge sensor coverage bound) + :unless + (loop for (other-sensor range) in sensor-coverage + :thereis (<= (manhattan-dist edge-point other-sensor) range)) + :return edge-point) + :when candi + :return (list sensor coverage candi)))) + +(fail-freq-edge (markers (uiop:read-file-lines "eg-in")) 20) + +(coverage-edge (cons 2 18) 7 20) +(coverage-edge (cons 9 16) 1 20) +(coverage-edge (cons 20 1) 7 20) + ;; fail coverage (defun fail-freq (markers bound) (loop :for y from 0 to bound @@ -112,7 +181,7 @@ :return (+ (* 4000000 col) y))) (fail-freq (markers (uiop:read-file-lines "eg-in")) 20) -(fail-freq (markers (uiop:read-file-lines "input")) 4000000) +(fail-freq-edge (markers (uiop:read-file-lines "input")) 4000000) (let* ((markers ) (bound 20))) @@ -121,6 +190,12 @@ (let* ((lines (uiop:read-file-lines "input")) (markers (markers lines)) (bounds (bounds markers))) - bounds) + (list + + (loop for (sensor beacon) on markers by #'cddr + maximize (manhattan-dist sensor beacon)))) + + +(loop for (x)) (make-array (* 4000000 4000000) :element-type '(unsigned-byte 1) :initial-element 0) |