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

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

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


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

(let* ((lines (uiop:read-file-lines "input"))
       (markers (markers lines))
       (bounds (bounds markers))
       (max-distance (loop for (sensor beacon) on markers by #'cddr
                           maximize (manhattan-dist sensor beacon))))

  (destructuring-bind ((xmin xmax) (ymin ymax)) bounds
    (let* ((stride (- (+ (* 2 max-distance) xmax 1) xmin))
           (row-min (- xmin max-distance))
           (target-row 2000000)
           (row (make-array stride :element-type '(unsigned-byte 1) :initial-element 0)))
      (loop for (sensor beacon) on markers by #'cddr
            for distance = (manhattan-dist sensor beacon)
            when (= target-row (cdr sensor))
              do (setf (aref row (- (car sensor) row-min)) 1)
            when (= target-row (cdr beacon))
              do (setf (aref row (- (car beacon) row-min)) 1)

            sum (loop
                  for x from (- xmin distance) to (+ xmax distance)
                  when (and (<= (manhattan-dist sensor (cons x target-row)) distance)
                            (< -1 (- x row-min) stride)
                            (= 0 (aref row (- x row-min))))
                    count it and do (setf (aref row (- x row-min)) 1))))))