(in-package :ca.mhcat.advent2022)


;; --- Day 4: Camp Cleanup ---

;; Space needs to be cleared before the last supplies can be
;; unloaded from the ships, and so several Elves have been
;; assigned the job of cleaning up sections of the camp.
;; Every section has a unique ID number, and each Elf is
;; assigned a range of section IDs.

;; However, as some of the Elves compare their section
;; assignments with each other, they've noticed that many of
;; the assignments overlap. To try to quickly find overlaps
;; and reduce duplicated effort, the Elves pair up and make
;; a big list of the section assignments for each pair (your
;; puzzle input).

;; For example, consider the following list of section
;; assignment pairs:

;; 2-4,6-8
;; 2-3,4-5
;; 5-7,7-9
;; 2-8,3-7
;; 6-6,4-6
;; 2-6,4-8

;; For the first few pairs, this list means:

;;     Within the first pair of Elves, the first Elf was
;;     assigned sections 2-4 (sections 2, 3, and 4), while
;;     the second Elf was assigned sections 6-8 (sections 6,
;;     7, 8).

;;     The Elves in the second pair were each assigned two
;;     sections.

;;     The Elves in the third pair were each assigned three
;;     sections: one got sections 5, 6, and 7, while the
;;     other also got 7, plus 8 and 9.

;; This example list uses single-digit section IDs to make
;; it easier to draw; your actual list might contain larger
;; numbers. Visually, these pairs of section assignments
;; look like this:

;; .234.....  2-4
;; .....678.  6-8

;; .23......  2-3
;; ...45....  4-5

;; ....567..  5-7
;; ......789  7-9

;; .2345678.  2-8
;; ..34567..  3-7

;; .....6...  6-6
;; ...456...  4-6

;; .23456...  2-6
;; ...45678.  4-8

;; Some of the pairs have noticed that one of their
;; assignments fully contains the other. For example, 2-8
;; fully contains 3-7, and 6-6 is fully contained by 4-6. In
;; pairs where one assignment fully contains the other, one
;; Elf in the pair would be exclusively cleaning sections
;; their partner will already be cleaning, so these seem
;; like the most in need of reconsideration. In this
;; example, there are 2 such pairs.

;; In how many assignment pairs does one range fully contain
;; the other?

(defparameter day4/test-data
  '("2-4,6-8"
    "2-3,4-5"
    "5-7,7-9"
    "2-8,3-7"
    "6-6,4-6"
    "2-6,4-8"))

(defclass day4/range ()
  ((start
    :initarg :start
    :initform 0
    :reader start)
   (end
    :initarg :end
    :initform (error "can't guess the ending")
    :reader end)))

(defmethod initialize-instance :after ((r day4/range) &key)
  (with-slots (start end) r
    (when (> start end)
      (error "can't have a range with a start after the end"))))

(defgeneric day4/contains (r1 r2))
(defmethod day4/contains ((r1 day4/range) (r2 day4/range))
  (with-slots (start end) r1
    (and (<= start (start r2))
         (>= end (end r2)))))

(defun day4/total-overlap (range1 range2)
  (or (day4/contains range1 range2)
      (day4/contains range2 range1)))

(defun day4/split-at (s ch)
  (let ((split-point (position ch s)))
    (list (subseq s 0 split-point)
          (subseq s (1+ split-point)))))

(defun day4/parse-line (line)
  (flet ((make-range (pair)
           (make-instance
            'day4/range
            :start (parse-integer (first pair))
            :end (parse-integer (second pair)))))
    (let ((range-pairs (mapcar (lambda (s)
                                 (day4/split-at s #\-))
                               (day4/split-at line #\,))))
      (mapcar #'make-range range-pairs))))

(defun day4/load-dataset (lst)
  (mapcar #'day4/parse-line lst))

(defun day4/compute (pred data)
  (let ((overlaps (mapcar (lambda (pair)
                            (apply pred pair))
                          data)))
    (length (remove-if #'null overlaps))))

(defun day4/compute-part1 (data)
  (day4/compute #'day4/total-overlap data))

(defun day4/part1 ()
  (day4/compute-part1
   (day4/load-dataset
    (load-lines "day4.txt"))))

;; --- Part Two ---

;; It seems like there is still quite a bit of duplicate
;; work planned. Instead, the Elves would like to know the
;; number of pairs that overlap at all.

;; In the above example, the first two pairs (2-4,6-8 and
;; 2-3,4-5) don't overlap, while the remaining four pairs
;; (5-7,7-9, 2-8,3-7, 6-6,4-6, and 2-6,4-8) do overlap:

;;     5-7,7-9 overlaps in a single section, 7.
;;     2-8,3-7 overlaps all of the sections 3 through 7.
;;     6-6,4-6 overlaps in a single section, 6.
;;     2-6,4-8 overlaps in sections 4, 5, and 6.

;; So, in this example, the number of overlapping assignment
;; pairs is 4.

;; In how many assignment pairs do the ranges overlap?

(defgeneric day4/overlaps (r1 r2))
(defmethod day4/overlaps ((r1 day4/range) (r2 day4/range))
  (with-slots (start end) r1
    (not
     (or (> start (end r2))
         (< end (start r2))))))

(defun day4/compute-part2 (data)
  (day4/compute #'day4/overlaps data))

(defun day4/part2 ()
  (day4/compute-part2
   (day4/load-dataset
    (load-lines "day4.txt"))))