simple coverage again

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)