aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2022/15/solver.lisp
diff options
context:
space:
mode:
Diffstat (limited to 'AoC2022/15/solver.lisp')
-rw-r--r--AoC2022/15/solver.lisp111
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))))