aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2023/day11/solver.lisp
blob: 666b71c8e2d6ffdb5021695f30b5de5bf20eb7ab (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
;; 9:59
;; 10:31 part1
;; 10:47 part2

(ql:quickload '(fiveam))
(defparameter eg-input "...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....")

(defun indexes (array)
  (loop for v across array
        for i from 0 when v collect i))

(defun shift (coord spacers)
  (count-if (lambda (idx) (< idx coord)) spacers))

(defun expanded (point free-rows free-cols multiplier)
  (destructuring-bind (y x) point
    (list (+ y (* multiplier (shift y free-rows)))
          (+ x (* multiplier (shift x free-cols))))))

(fiveam:test parts
  (fiveam:is (= 1 (shift 5 '(3 6))))
  (fiveam:is (equal '(7 4) (expanded '(5 3) '(1 2) '(2) 1))))

(defun expanded-galaxies (rows &optional (multiplier 1))
  (let* ((free-rows (make-array (length rows) :initial-element t))
         (free-cols (make-array (length (car rows)) :initial-element t))
         (galaxies (loop for row in rows
                         for y from 0
                         nconc
                         (loop for col across row
                               for x from 0
                               when (eq col #\#)
                                 collect (list y x)
                                 and do (setf (aref free-rows y) nil
                                              (aref free-cols x) nil)))))
    (map 'vector
         (lambda (galaxie)
           (expanded galaxie
                     (indexes free-rows)
                     (indexes free-cols)
                     multiplier))
         galaxies)))


(defun manhattan-dist (s x)
  (destructuring-bind ((sx  sy) (bx  by)) (list s x)
    (+ (abs (- bx sx)) (abs (- by sy)))))


(defun solver (rows &optional (multiplier 1))
  (loop with gals = (expanded-galaxies rows multiplier)
        for g across gals
        for i from 0 sum
                     (loop for j from (1+ i) below (length gals)
                           sum (manhattan-dist g (aref gals j)))))

(fiveam:test solutions
  (fiveam:is (= 374 (solver (uiop:split-string eg-input :separator '(#\Newline)))))
  (fiveam:is (= 1030 (solver (uiop:split-string eg-input :separator '(#\Newline)) 9)))
  (fiveam:is (= 8410 (solver (uiop:split-string eg-input :separator '(#\Newline)) 99)))
  (fiveam:is (= 10154062 (solver (uiop:read-file-lines "input"))))
  (fiveam:is (= 553083047914 (solver (uiop:read-file-lines "input") 999999))))