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