aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorOscar Najera <hi@oscarnajera.com>2022-12-17 19:59:18 +0100
committerOscar Najera <hi@oscarnajera.com>2022-12-17 19:59:18 +0100
commitea80ec7f238cb5f3930800ccfbc9920436bc8189 (patch)
tree6746891f6bc07bd92cfeadc12a005ed0cdfb4a6e
parentc74421bcc04262ca88d105d1ebf7695ed5b07f43 (diff)
downloadscratch-ea80ec7f238cb5f3930800ccfbc9920436bc8189.tar.gz
scratch-ea80ec7f238cb5f3930800ccfbc9920436bc8189.tar.bz2
scratch-ea80ec7f238cb5f3930800ccfbc9920436bc8189.zip
simple coverage again
-rw-r--r--AoC2022/15/solver.lisp123
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)