-
Notifications
You must be signed in to change notification settings - Fork 0
/
day11.lisp
245 lines (235 loc) · 22 KB
/
day11.lisp
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
(in-package #:advent-of-code-2023.day11)
(defun find-empty-rows-and-columns (array)
"Find empty rows and columns in ARRAY."
(labels ((empty (c)
(char= #\. c)))
(let* ((rows (length array))
(cols (length (first array)))
(transposed (transpose array))
(empty-rows
(loop
for r from 0 below rows
if (every #'empty (nth r array))
collect r))
(empty-cols
(loop
for c from 0 below cols
if (every #'empty (nth c transposed))
collect c)))
(list empty-rows empty-cols))))
(defun duplicate-rows-and-columns (array rows cols)
"Duplicate ROWS and COLS in ARRAY. Transpose twice to make row/column
duplication easier."
(let* ((expanded-rows
(loop
for r from 0
for row in array
collect row
if (member r rows)
collect row))
(expanded-cols
(loop
for c from 0
for col in (transpose expanded-rows)
collect col
if (member c cols)
collect col)))
(transpose expanded-cols)))
(defun find-galaxies (array)
"Find all galaxies (#\#) within ARRAY and return a list of (row
. column) cons cells."
(loop
for r from 0
for row in array
nconc (loop
for c from 0
for item in row
if (char= #\# item)
collect (cons r c))))
(defun puzzle-1 (&key (input *example-input-1*))
(labels ((distance (el1 el2)
(+ (abs (- (car el2) (car el1)))
(abs (- (cdr el2) (cdr el1))))))
(let* ((data (parse-string-into-list input))
(empties (find-empty-rows-and-columns data))
(expanded (apply #'duplicate-rows-and-columns data empties))
(galaxies (find-galaxies expanded)))
(loop
for (el1 . els) on galaxies
sum (loop
for el2 in els
sum (distance el1 el2))))))
(defun puzzle-2 (&key (input *example-input-2*) (expansion-factor 1000000))
(labels ((distance (el1 el2)
(+ (abs (- (car el2) (car el1)))
(abs (- (cdr el2) (cdr el1))))))
(let* ((data (parse-string-into-list input))
(galaxies (find-galaxies data))
(empties (find-empty-rows-and-columns data))
(expanded (loop
for (gr . gc) in galaxies
for gr-increment = (* (1- expansion-factor) (count-if #'(lambda (er) (< er gr)) (first empties)))
for gc-increment = (* (1- expansion-factor) (count-if #'(lambda (ec) (< ec gc)) (second empties)))
collect (cons (+ gr gr-increment)
(+ gc gc-increment)))))
(loop
for (el1 . els) on expanded
sum (loop
for el2 in els
sum (distance el1 el2))))))
;;;; Data
(defvar *example-input-1*
"...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....")
(defvar *input-1*
".#......................#........................#.........................#................#...............................................
...........................................................................................................#...........#....................
........#...................#.......#............................................#....................#.................................#...
.........................................#............#.........................................#...........................................
....................................................................................................................................#.......
#...........................................................................................................................................
................#......................................................#.............#......................................................
......#..............#.........#......#........................#............................................................................
............#.....................................#......................................#...........................#......................
.....................................................................................................#....................#.................
.....................................................................#.......#............................#......#..............#...........
#...........................................................................................................................................
...................................#.....................................#..................................................................
.........#................#................................#...........................#......#.......................#..................#..
...............#....................................#..........................................................#............................
...........................................#..................................................................................#.............
...............................#...........................................#.......#.................#......................................
#..............................................................#..........................................#.................................
...........#.........................................................#.............................................#........................
......................#...........#...........................................#..........#.....#............................................
........................................................#...............................................................#......#............
...#..........#.........................#................................#..................................................................
............................................................................................................................................
..................#..................................#..............#..................................................................#....
...............................#...........................#...................#.............................#..............................
....................................#....................................................#.............#...............#...................#
................................................................................................#...........................................
.#............#............#........................................................#......................................#................
.......#...................................#........#.......................................................................................
..........................................................#.................................................................................
..............................................................................#..............#.......#................................#.....
.................................#..........................................................................#.........#.....................
....................#....................................................................#......................................#...........
........#...................................#.....................................................................#.........................
#........................#.........................#.............................................#..........................................
.................#.........................................#.........................#......................................................
..............................#.................................#.......................................................................#...
......#...............................#..............................................................................#.............#........
......................................................#..................#.................#............#.......#...........................
..............#...........#......................................................#..........................................................
............................................................#...............................................................................
.....................................................................#......................................................................
.#..................#........................................................................#................................#.............
.........................................#..........................................................................#.......................
.........#.....#..............#..............................................#.........#..............#..............................#.....#
...............................................................................................................#............................
...................................................#...................#...................................................#................
.......................#...........#..............................#......................................#..............................#...
...........#................#...............................................................................................................
...........................................................................#.................................#..............................
................#......................................................................#...........#........................................
.....................................................................................................................#........#......#......
..................................................#.............#..............................#............................................
......#.....#...........#..................#..............................................................#.................................
............................................................................................................................................
...................#...................#..................#....................................................#........................#...
............................................................................................................................................
.........................................................................#..................#...............................................
.....................................................................................................................................#.....#
...................................#...........#....................#.......................................................................
..#.....#.....................................................................#.........................#...................................
...........................#.........................#..................................#..........#..................#.....................
..................................................................................#............................................#............
..............#................#...............................#............................................................................
............................................................................................................................................
.....................................#.........#......................................#..............#........#..........#..................
.....#............#...............................................#........................................................................#
..........................................................................................................#.................................
..........#.............#.....#...........................#.....................#...........................................................
...............................................................#.................................#....................................#.....
....................................#..................................#....................................................................
#......................................................................................................#..........#..........#..............
..........................................#.............................................#...................................................
.................#.............................#........#......................................#.........................#...............#..
......................................#..........................................#..........................................................
............#...............................................#...............................................................................
...........................................................................................#..........................................#.....
.....#................#...............................................................................#.....................................
............................#......................#................#.............................................................#.........
...................................#.........................................................................................#..............
.#.......................................................................#.........#........................#...............................
.........................................#.................#.....................................#...............#..........................
..............................#.............................................................................................................
.................#...............................#.............................#.......#.....#.......#......................................
.......................................................................#....................................................................
............................................................................................................................................
......................................#...........................#.........................................................................
.................................................................................#..........................................................
..................................#.......................#.................................................................................
......................#..............................................#...........................#..........................#.....#.....#...
...........................#............#................................................................#.....#............................
...........................................................................................#................................................
............................................................................................................................................
.........#.........#..........................................................#.............................#.........#.............#.......
...........................................#.............#..................................................................................
............................#..........................................................#..........................#.........................
.......................#.........#..........................................................................................................
......#...........................................#....................#.......................#..........#.................................
...............#.................................................................#..........................................#...............
..........................................................#......#....................................................#............#......#.
......................................................................................................#.....................................
...............................................................................................................#............................
...............................#.....#................#.............................#.......................................................
..#............................................................................#...............#..........................#.................
.......#...................................#........................................................#.......................................
..............................................................#........#.....................................#..............................
...........................#.......#..............#......................................................................................#..
......................#......................................................................................................#......#.......
..............#...........................................................................................#.............#...................
..........................................................#.........#.........................#.............................................
.......................................#.......#...............................#..............................#.............................
................................#...................................................#.......................................................
#..........................................#........#..........#............................................................................
...........................................................................#............#.........................#..................#......
............#...........................................................................................#...................................
...................................#........................................................#...............................................
........................#.................................#......#.......................................................#..................
........#................................................................#..................................................................
...................#..............................#.................................#..............#.........#.....#.............#..........
..........................................#...................#........................................................................#....
.........................................................................................................#..................................
..............................#.........................................................#...................................................
.#..............#...........................................................................................................................
...................................#...........#........................................................................#...................
.........#...............................#........................................................................................#.........
....................#........................................................................#.....................#.........#............#.
..............................................................................#.......................#.......#.............................
.................................#.......................#...............#...............#..................................................
............................................................................................................................................
............................#........#......................................................................................................
......................#........................................#................#...........#..............#........................#.......
.....#.......#........................................................................#..........#........................................#.
..................................................#.........................................................................................
...............................................................................................................#.........#..................
.........................#........#........................#.............#..........................#.......................................
..........#..............................#......................#..........................#................................................
#..................................................................................#........................................................
...............................#................................................................................................#...........
.....................................................#.......#.............................................#................................
......#...............#..............#.........#..................#...............................................#......#...............#..")
(defvar *example-input-2*
*example-input-1*)
(defvar *input-2* *input-1*)