(defun p1-process-line (line)
   (to-symbols line 'advt2024-d8))
  
(defun count-results (results)
  (loop for i from 0 below (array-total-size results)
        count (row-major-aref results i)))

(defun place-annode (pos results)
  (let ((x (first pos)) (y (second pos)))
    (when (in-map results x y) 
      (setf (aref results y x) t))))

(defun create-annodes-p1 (x1 y1 x2 y2)
  (let ((delta-x (- x2 x1)) (delta-y (- y2 y1)))
    (list (list (- x1 delta-x) (- y1 delta-y)) (list (+ x2 delta-x) (+ y2 delta-y)))))

(defun place-annodes (positions results create-annodes)
  (when positions
     (loop with a = (car positions)
           with x1 = (first a)
           with y1 = (second a)
           for b in (cdr positions)
           for ans = (funcall create-annodes x1 y1 (first b) (second b))
           do (dolist (a ans) (place-annode a results)))
     (place-annodes (cdr positions) results create-annodes)))

(defun place-all-annodes (xmits map &optional (create-annodes #'create-annodes-p1))
  (let ((results (make-array (array-dimensions map) :element-type 'boolean :initial-element nil)))
    (loop for k being the hash-key of xmits
          do (place-annodes (gethash k xmits) results create-annodes))
    results))

(defun find-transmitters (map)
  "look throught the map and record where the transmitters are in a hash map"
  (let ((h (make-hash-table)))
    (destructuring-bind (rows cols) (array-dimensions map)
      (loop for j from 0 below rows
            do (loop for i from 0 below cols
                     for v = (aref map j i)
                     unless (eql v '|.|)
                       do (push (list i j) (gethash v h))
                     )))
    h))

(defun run-p1 (file) 
  (let* ((map (list-to-2d-array (read-file file #'p1-process-line))))
    (count-results (place-all-annodes (find-transmitters map) map))
    ))

(defun create-annodes-2 (x1 y1 x2 y2 map)
  (destructuring-bind (rows cols) (array-dimensions map)
    (let* ((m (/ (- y2 y1) (- x2 x1) ))
           (b (- y2 (* m x2))))
      (loop for x from 0 below cols
            for y = (+ b (* x m))
            for r = (nth-value 1 (floor y))
            when (and (= r 0) (>= y 0) (< y rows))
              collect (list x y)))))

(defun run-p2 (file) 
  (let* ((map (list-to-2d-array (read-file file #'p1-process-line))))
    (count-results (place-all-annodes (find-transmitters map) map
                                      (lambda (x1 y1 x2 y2)
                                        (create-annodes-2 x1 y1 x2 y2 map))))))

(defstruct calibration result inputs)

(defun p1-process-line (line)
  (let ((parts (str:words line)))
    (make-calibration :result (parse-integer (car parts) :junk-allowed t)
                      :inputs (mapcar #'parse-integer (cdr parts)))))

(defun apply-opperators (c opps)
  (let ((accum (car (calibration-inputs c))))
  (loop for o in opps
        for v in (cdr (calibration-inputs c))
        until (> accum (calibration-result c))
        if (eql o 'ADD)
          do (setf accum (+ accum v))
        else if (eql o 'MUL)
          do (setf accum (* accum v))
        else
          do (setf accum (+ v (* accum (expt 10 (1+ (floor (log v 10)))))))
        finally (return accum)
        )))

(defun generate-operators (item-count)
  (labels ((g-rec (c results)
             (if (< c 1)
                 results
                 (g-rec (1- c) (loop for r in results
                                     collect (cons 'ADD r)
                                     collect (cons 'MUL r))))))
    (g-rec (1- item-count) '((ADD) (MUL)))))

(defun generate-ops-hash (c gen-ops)
  (let ((h (make-hash-table)))
    (dotimes (x c)
      (setf (gethash (+ 2 x) h) (funcall gen-ops (+ 1 x))))
    h))

(defun validate-calibration (c ops-h)
  (let ((r (calibration-result c))
        (ops (gethash (length (calibration-inputs c)) ops-h)))
    (loop for o in ops
          for v = (apply-opperators c o)
          when (= v r)
            return t)))

(defun run-p1 (file) 
  (let ((calibrations  (read-file file #'p1-process-line))
        (ops (generate-ops-hash 13 #'generate-operators)))
    (loop for c in calibrations
          when (validate-calibration c ops)
            sum (calibration-result c))))

(defun generate-operators-p2 (item-count)
  (labels ((g-rec (c results)
             (if (< c 1)
                 results
                 (g-rec (1- c) (loop for r in results
                                     collect (cons 'ADD r)
                                     collect (cons 'MUL r)
                                     collect (cons 'CAT r))))))
    (g-rec (1- item-count) '((ADD) (MUL) (CAT)))))

(defun run-p2 (file) 
  (let ((calibrations  (read-file file #'p1-process-line))
        (ops (generate-ops-hash 13 #'generate-operators-p2)))
    (loop for c in calibrations
          when (validate-calibration c ops)
            sum (calibration-result c))))

(defun p1-mult (str)
  "pulls out numbers and multiplies them, assumes already filtered by size"
  (let ((vals (ppcre:all-matches-as-strings "\\d+" str)))
    (apply #'* (or (mapcar #'parse-integer vals) '(0)))))

(defun p1-process-line (line)
  "look for mul, do the mul, and sum"
  (let ((ptrn "mul\\(\\d?\\d?\\d,\\d?\\d?\\d\\)"))
    (apply #'+ (mapcar #'p1-mult (ppcre:all-matches-as-strings ptrn line)))))

(defun run-p1 (file) 
  (let ((data (read-file file #'p1-process-line)))
    (apply #'+ data)))

(defun p2-process-line (line)
  "looks for mul, do, and don't"
  (let ((ptrn "(mul\\(\\d?\\d?\\d,\\d?\\d?\\d\\))|(do\\(\\))|(don't\\(\\))"))
    (ppcre:all-matches-as-strings ptrn line)))

(defun p2-filter (data)
  "expects list containing the string tokens (mul, do, don't) from the file"
  (let ((process t))
    (loop for x in data
          when (string= "don't()" x)
            do (setf process nil)
          when (string= "do()" x)
            do (setf process t)
          when process
            sum (p1-mult x))))

(defun run-p2 (file) 
  (let ((data (read-file file #'p2-process-line)))
    ;; treat the input as one line to make processing the do's and don't's easier
    (p2-filter (flatten data))))

(defun p1-process-line (line)
  (to-symbols line))

(defun found-word-h (word data i j)
  "checks for a word existing from the point horizontally to the right"
  (loop for j2 from j 
        for w in word
        when (not (eql w (aref data i j2)))
          return nil
        finally (return t)))

(defun found-word-v (word data i j)
  "checks for a word existing from the point vertically down"
  (loop for i2 from i 
        for w in word
        when (not (eql w (aref data i2 j)))
          return nil
        finally (return t)))

(defun found-word-d-l (word data i j)
  "checks for a word existsing from the point diagonally to the left and down"
  (destructuring-bind (n m) (array-dimensions data)
    (declare (ignorable n))
    
    (and (>= (- i (length word)) -1)
         (>= m (+ j  (length word)))
         (loop for i2 from i downto 0
               for j2 from j
               for w in word
               when (not (eql w (aref data i2 j2)))
                 return nil
               finally  (return t)))))

(defun found-word-d-r (word data i j)
  "checks for a word existing from the point diagonally to the right and down"
  (destructuring-bind (n m) (array-dimensions data)
    (and (>= n (+ i (length word)))
         (>= m (+ j  (length word)))
         (loop for i2 from i
               for j2 from j
               for w in word
               when (not (eql w (aref data i2 j2)))
                 return nil
               finally  (return t)))
    ))

(defun count-word-h (data word)
  "Counts horizontal matches of the word"
  (let ((word-r (reverse word))
        (word-l (length word)))
    (destructuring-bind (n m) (array-dimensions data)
      (loop for i from 0 below n 
            sum (loop for j from 0 upto (- m word-l)
                      count (found-word-h word data i j)
                      count (found-word-h word-r data i j))))))

(defun count-word-v (data word)
  "Counts vertical matches of the word"
  (let ((word-r (reverse word))
        (word-l (length word)))
    (destructuring-bind (n m) (array-dimensions data)
      (loop for j from 0 below m 
            sum (loop for i from 0 upto (- n word-l)
                      count (found-word-v word data i j)
                      count (found-word-v word-r data i j))))))

(defun count-word-d (data word)
  "Counts diagonal matches of the word"
  (let ((word-r (reverse word)))
    (destructuring-bind (n m) (array-dimensions data)
      (loop for i from 0 below n
            sum (loop for j from 0 below m
                      count (found-word-d-l word data i j)
                      count (found-word-d-l word-r data i j)
                      count (found-word-d-r word data i j)
                      count (found-word-d-r word-r data i j)
                      )))))


(defun run-p1 (file)
  "cares about the word xmas in any direction"
  (let ((word '(X M A S))
        (data (list-to-2d-array (read-file file #'p1-process-line))))
    (+
     (count-word-v data word)
     (count-word-h data word)
     (count-word-d data word))))


(defun run-p2 (file) 
  "cares about an x of mas crossed with mas"
  (let ((word '(M A S))
        (word-r '(S A M))
        (data (list-to-2d-array (read-file file #'p1-process-line))))
    (destructuring-bind (n m) (array-dimensions data)
      (loop for i from 0 below (- n 2)
            sum (loop for j from 0 below (- m 2)
                      count (and (found-word-d-r word data i j)
                                 (found-word-d-l word data (+ i 2) j))
                      count (and (found-word-d-r word-r data i j)
                                 (found-word-d-l word data (+ i 2) j))
                      count (and (found-word-d-r word data i j)
                                 (found-word-d-l word-r data (+ i 2) j))
                      count (and (found-word-d-r word-r data i j)
                                 (found-word-d-l word-r data (+ i 2) j))
                        )))))

(defun p1-process-rules (line)
  (mapcar #'parse-integer (uiop:split-string line :separator "|")))

(defun p1-process-pages (line)
  (mapcar #'parse-integer (uiop:split-string line :separator ",")))

(defun middle (pages)
  (nth (floor (length pages) 2) pages))

(defun check-rule-p (rule pages)
  (let ((p1 (position (car rule) pages))
        (p2 (position (cadr rule) pages)))
    (or (not p1) (not p2) (< p1 p2))))

(defun ordered-p (pages rules)
  (loop for r in rules
        unless (check-rule-p r pages)
          return nil
        finally
           (return t)))

(defun run-p1 (rules-file pages-file) 
  (let ((rules (read-file rules-file #'p1-process-rules))
        (pages (read-file pages-file #'p1-process-pages)))
    (loop for p in pages
          when (ordered-p p rules)
            sum (middle p)
          )))

(defun fix-pages (rules pages)
  (sort pages (lambda (p1 p2) (ordered-p (list p1 p2) rules)) ))

(defun run-p2 (rules-file pages-file) 
  (let ((rules (read-file rules-file #'p1-process-rules))
        (pages (read-file pages-file #'p1-process-pages)))
    (loop for p in pages
          unless (ordered-p p rules)
            sum (middle (fix-pages rules p))
          )))

(defvar *part1* "inputs/day06-part1")
(defvar *part1-test* "inputs/day06-part1-test")

(defstruct move x y direction)

(defstruct guard direction x y (moves (make-hash-table :test 'equalp)))

(defun convert-direction (g)
  (case g
    (^ 'up)
    (> 'right)
    (< 'left)
    (v 'down)))


(defun find-guard (map)
  (destructuring-bind (rows cols) (array-dimensions map)
    (loop for j from 0 below rows
          do (loop for i from 0 below cols
                   for v = (aref  map j i)
                   when (not (or (eql '|.| v) (eql '|#| v)))
                     do (return-from find-guard (make-guard :direction (convert-direction v) :x i :y j ))))))

(defun turn-guard (guard)
  (case (guard-direction guard)
    (UP (setf (guard-direction guard) 'RIGHT))
    (DOWN (setf (guard-direction guard) 'LEFT))
    (LEFT (setf (guard-direction guard) 'UP))
    (RIGHT (setf (guard-direction guard) 'DOWN))))

(defun on-map (map x y)
  (destructuring-bind (rows cols) (array-dimensions map)
    (and (>= x 0) (>= y 0)
         (< y rows) (< x cols))))

(defun mark-guard (map guard)
  (setf (aref map (guard-y guard) (guard-x guard)) 'X))

(defun next-pos (guard)
  (case (guard-direction guard)
    (UP (list (guard-x guard) (1- (guard-y guard))))
    (DOWN (list (guard-x guard) (1+ (guard-y guard))))
    (LEFT (list (1- (guard-x guard)) (guard-y guard)))
    (RIGHT (list (1+ (guard-x guard)) (guard-y guard)))))

(defun move-guard (map guard)
  (destructuring-bind (x y) (next-pos guard)
    (if (on-map map x y)
        (if (eql '|#| (aref map y x))
            (turn-guard guard)
            (progn (setf (guard-x guard) x)
                   (setf (guard-y guard) y))) 
        (setf (guard-direction guard) nil))))

(defun run-p1 (file) 
  (let* ((map (list-to-2d-array (read-file file #'to-symbols)))
         (guard (find-guard map)))
    (mark-guard map guard)
    (loop while (guard-direction guard)
          do (mark-guard map guard)
          do (move-guard map guard))
    (destructuring-bind (rows cols) (array-dimensions map)
      (loop for y from 0 below rows sum (loop for x from 0 below cols count (eql (aref map y x) 'X))))))

(defun save-move (guard move)
  (setf (gethash move (guard-moves guard)) t))

(defun reset-moves (guard)
  (setf (guard-moves guard) nil))

(defun is-loop (x y map original-guard)
  ;; can only set new blocks in blank spaces
  (unless (eql '|.| (aref map y x)) (return-from is-loop nil))
  (let ((guard (copy-guard original-guard)))
    ;; save the initial guard position
    (save-move guard (make-move :x (guard-x guard) :y (guard-y guard) :direction (guard-direction guard)))
    ;; set the "new" block
    (setf (aref map y x) '|#|)
    ;; loop and check for guard loops
    (let ((result
            (loop
              while (move-guard map guard)
              for move = (make-move :x (guard-x guard) :y (guard-y guard) :direction (guard-direction guard))
              ;; if we have seen the move before, then it is a loop
              if (gethash move (guard-moves guard))
                return t
              else
                do (save-move guard move)
              finally
                 (return nil))))

      ;; reset initial position
      (setf (aref map y x) '|.|)
      (clrhash (guard-moves guard))
      result)))


(defun run-p2 (file) 
  (let* ((map (list-to-2d-array (read-file file #'to-symbols)))
         (guard (find-guard map)))
    
    (destructuring-bind (rows cols) (array-dimensions map)
      (loop for y from 0 below rows
            sum (loop for x from 0 below cols
                      count (is-loop x y map guard)))
      )))

(defun p1-process-line (line)
  (mapcar #'parse-integer (str:words line)))

(defun line-direction-p (line)
  "make sure the line always goes in the same direction"
  (loop for x in line
        for y in (cdr line)
        count (> x y) into dec
        count (< x y) into inc
        when (and (> dec 0 ) (> inc 0)) return nil
        when (= x y) return nil
        finally (return t)))

(defun line-in-range-p (line)
  "makes sure the delta is within 3"
  (loop for x in line
        for y in (cdr line)
        for delta = (abs (- x y))
        when (or (> delta 3) )
          return nil 
        finally (return t)))

(defun test-line-p (line)
  (and (line-in-range-p line) (line-direction-p line)))

(defun run-p1 (file) 
  (let ((data (read-file file #'p1-process-line)))
    (apply #'+ (mapcar (lambda (line) (if (test-line-p line) 1 0)) data))))

(defun test-line-p2 (line)
  (or (test-line-p (cdr line))
      (test-line-p (cdr (reverse line)))
  (loop for back on line
        collect (car back) into front
        when (test-line-p (concatenate 'list front (cddr back)))
          return t
        finally (return nil)
  )))

(defun run-p2 (file) 
  (let ((data (read-file file #'p1-process-line)))
    (loop for line in data
          count (test-line-p2 line))))