(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))))

(defun in-grid (bounds)
  (destructuring-bind ((xmin xmax) (ymin ymax)) bounds
    (let ((stride (- xmax xmin -1)))
      (lambda (x y)
        (when (and (<= xmin x xmax) (<= ymin y ymax))
          (+ (- x xmin) (* (- y ymin) stride)))))))

(defun from-grid (bounds)
  (destructuring-bind ((xmin xmax) (ymin _)) bounds
    (declare (ignore _))
    (let ((stride (- xmax xmin -1)))
      (lambda (pos)
        (multiple-value-bind (y x) (floor pos stride)
          (cons (+ x xmin) (+ y ymin)))))))

(defun draw-grid (grid stride)
  (let ((out (make-string-output-stream)))
    (loop for elt across grid
          for idx from 0
          do (progn (when (= 0 (mod idx stride)) (terpri out))
                    (princ (case elt
                             (0 ".")
                             (1 "S")
                             (2 "B")
                             (3 "#")) out)))
    (get-output-stream-string out)))

;; 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)))))

(defun markers (lines)
  (loop for line in lines
        for (sx sy bx by) = (multiple-value-bind (match values)
                                (cl-ppcre:scan-to-strings "Sensor at x=(-?\\d+), y=\(-?\\d+\): closest beacon is at x=(-?\\d+), y=(-?\\d+)"
                                                          line)
                                (declare (ignore match))
                              (map 'list #'parse-integer values))
        nconc (list (cons sx sy) (cons bx by))))

(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))))

(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)))
    (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 (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)
 )


(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
        :for col = (loop :for x from 0 to bound
                         :when (loop :for (sensor beacon) on markers by #'cddr
                                     :never (<= (manhattan-dist sensor (cons x y))
                                                (manhattan-dist sensor beacon)))
                           :return x)
        :when col
          :return (+ (* 4000000 col) y)))

(fail-freq (markers (uiop:read-file-lines "eg-in")) 20)
(fail-freq-edge (markers (uiop:read-file-lines "input")) 4000000)

(let* ((markers )
       (bound 20)))


(let* ((lines (uiop:read-file-lines "input"))
       (markers (markers lines))
       (bounds (bounds markers)))
  (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)

(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))))