aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2022/15/eg-in
blob: a61242407e0d5ef6618cca5e67224d0493edbe8e (plain) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3
generated by cgit v1.2.3 (git 2.43.2) at 2025-02-24 01:35:56 +0000
ctuation.Marker */ .highlight .w { color: #EEFFFF } /* Text.Whitespace */ .highlight .mb { color: #F78C6C } /* Literal.Number.Bin */ .highlight .mf { color: #F78C6C } /* Literal.Number.Float */ .highlight .mh { color: #F78C6C } /* Literal.Number.Hex */ .highlight .mi { color: #F78C6C } /* Literal.Number.Integer */ .highlight .mo { color: #F78C6C } /* Literal.Number.Oct */ .highlight .sa { color: #BB80B3 } /* Literal.String.Affix */ .highlight .sb { color: #C3E88D } /* Literal.String.Backtick */ .highlight .sc { color: #C3E88D } /* Literal.String.Char */ .highlight .dl { color: #EEFFFF } /* Literal.String.Delimiter */ .highlight .sd { color: #546E7A; font-style: italic } /* Literal.String.Doc */ .highlight .s2 { color: #C3E88D } /* Literal.String.Double */ .highlight .se { color: #EEFFFF } /* Literal.String.Escape */ .highlight .sh { color: #C3E88D } /* Literal.String.Heredoc */ .highlight .si { color: #89DDFF } /* Literal.String.Interpol */ .highlight .sx { color: #C3E88D } /* Literal.String.Other */ .highlight .sr { color: #89DDFF } /* Literal.String.Regex */ .highlight .s1 { color: #C3E88D } /* Literal.String.Single */ .highlight .ss { color: #89DDFF } /* Literal.String.Symbol */ .highlight .bp { color: #89DDFF } /* Name.Builtin.Pseudo */ .highlight .fm { color: #82AAFF } /* Name.Function.Magic */ .highlight .vc { color: #89DDFF } /* Name.Variable.Class */ .highlight .vg { color: #89DDFF } /* Name.Variable.Global */ .highlight .vi { color: #89DDFF } /* Name.Variable.Instance */ .highlight .vm { color: #82AAFF } /* Name.Variable.Magic */ .highlight .il { color: #F78C6C } /* Literal.Number.Integer.Long */
(ql:quickload '(fiveam))
(defpackage :day21
  (:use :cl :fiveam :alexandria))
(in-package :day21)
;;22:55
;;23:32

(defun find-start (field)
  (destructuring-bind (rows cols)
      (array-dimensions field)
    (loop for row below rows do
      (loop for col below cols do
        (when (eq (aref field row col) #\S)
          (return-from find-start (list row col)))))))

(defun read-field (filename)
  (let* ((lines (uiop:read-file-lines filename)))
    (make-array (list (length lines) (length (car lines)))
                :initial-contents lines)))

(defun solver (field boundedp &rest step-counts)
  (let* (pending
         (visited (make-hash-table :test #'equal))
         (start (find-start field))
         (step-count (car (last step-counts)))
         (end-positions (mapcar (lambda (s)
                                  (cons (- step-count s)
                                        (make-hash-table :test #'equal)))
                                step-counts)))
    (destructuring-bind (rows cols)
        (array-dimensions field)

      (push (cons step-count start) pending)
      (setf (gethash start visited) step-count)

      (loop while pending
            for (steps-left row col) = (pop pending)
            ;; an even number of steps left means it is possible
            ;; to go and return to the place in the steps available
            ;; Thus count to the solution.
            do
               (dolist (ep end-positions)
                 (destructuring-bind (check-point . tracker) ep
                   (let ((mark-left (- steps-left check-point)))
                     (when (and (not (minusp mark-left))
                                (evenp mark-left))
                       (setf (gethash (list row col) tracker) t)))))
            unless (zerop steps-left)
              do (loop
                   for (dr dc) in '((-1 0) (0 -1) (1 0) (0 1))
                   for nr = (+ row dr)
                   for nc = (+ col dc)
                   for new-pos = (list nr nc)
                   when (and (< (gethash new-pos visited -1) (1- steps-left))
                             (if boundedp
                                 (and
                                  (< -1 nr rows)
                                  (< -1 nc cols))
                                 t)
                             (not (eq #\# (aref field (mod nr rows) (mod nc cols)))))
                     do (setf (gethash new-pos visited) (1- steps-left))
                        (push (cons (1- steps-left) new-pos) pending))))
    (mapcar (compose #'hash-table-count #'cdr) end-positions)))


(defun solve-quadratic (r-one r-two r-three)
  ;; The covered area grows proportional to the square of steps taken.
  ;; The requested numbers of steps (= 26501365 (+ (* 202300 131) 65))
  ;; The function that takes to the the edge of the field g(x) = 65 + x * 131
  ;; The standard quadratic function q(x) = a*x^2 + b*x + c
  ;; r₁ = q o g (0) = c
  ;; r₂ = q o g (1) = a  +  b + c
  ;; r₃ = q o g (2) = 4a + 2b + c
  ;;
  ;; solving is simple
  ;; a = (r₃  - 2r₂ + r₁) / 2
  ;; b = (4r₂ - 3r₁ - r₃) / 2
  ;; c = r₁
  (values (/ (+ (- r-three (* 2 r-two))
                r-one)
             2)
          (/ (- (* 4 r-two) (* 3 r-one) r-three) 2)
          r-one))

(defun solve-part2 (places)
  (let ((x 202300))
    (multiple-value-bind (a b c)
        (apply #'solve-quadratic places)
      (+ (* a x x) (* b x) c))))

(test solutions
  (is (= 16 (car (solver (read-field "eg-in") t 6))))
  (is (= 3574 (car (solver (read-field "input") t 64))))
  (mapc (lambda (solution calculated)
          (is (= solution calculated)))
        '(16 50 1594 6536 26538 59895)
        (solver (read-field "eg-in") nil 6 10 50 100 200 300))

  (let ((results '(3719 33190 91987))
        (places (solver (read-field "input") nil 65 (+ 65 131) (+ 65 (* 131 2)))))
    (mapc (lambda (solution calculated)
            (is (= solution calculated)))
          results
          places)
    (is (= 600090522932119 (solve-part2 results)))))
generated by cgit v1.2.3 (git 2.43.2) at 2025-02-24 01:35:55 +0000