this repo has no description
hauleth.dev
1<!-- livebook:{"persist_outputs":true} -->
2
3# Day 20
4
5```elixir
6Mix.install([:kino_aoc])
7```
8
9## Section
10
11<!-- livebook:{"attrs":"eyJhc3NpZ25fdG8iOiJwdXp6bGVfaW5wdXQiLCJkYXkiOiIyMCIsInNlc3Npb25fc2VjcmV0IjoiQURWRU5UX09GX0NPREVfU0VTU0lPTiIsInllYXIiOiIyMDI0In0","chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->
12
13```elixir
14{:ok, puzzle_input} =
15 KinoAOC.download_puzzle("2024", "20", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
16```
17
18<!-- livebook:{"output":true} -->
19
20```
21{:ok,
22 "#############################################################################################################################################\n#...#...#...#...#.........#.........###...#.....#...#.....#...#.......#...#...###...#...#...###.......#.........#...#...#...#...............#\n#.#.#.#.#.#.#.#.#.#######.#.#######.###.#.#.###.#.#.#.###.#.#.#.#####.#.#.#.#.###.#.#.#.#.#.###.#####.#.#######.#.#.#.#.#.#.#.#############.#\n#.#.#.#.#.#...#.#.....#...#.#.......#...#.#...#.#.#.#...#...#.#.#.....#.#.#.#.#...#...#.#.#...#...#...#.....#...#.#.#.#...#...#.........#...#\n#.#.#.#.#.#####.#####.#.###.#.#######.###.###.#.#.#.###.#####.#.#.#####.#.#.#.#.#######.#.###.###.#.#######.#.###.#.#.#########.#######.#.###\n#.#.#.#.#...#...#...#.#...#.#.#.....#...#...#.#.#.#...#.#.....#.#.###...#.#.#.#.......#.#.#...#...#.....###.#.....#...#...#...#.......#...###\n#.#.#.#.###.#.###.#.#.###.#.#.#.###.###.###.#.#.#.###.#.#.#####.#.###.###.#.#.#######.#.#.#.###.#######.###.###########.#.#.#.#######.#######\n#.#.#.#.#...#...#.#.#.#...#.#.#.#...###...#.#.#.#.#...#.#...#...#...#...#...#.....###.#.#.#...#.....#...#...#.......#...#...#...#.....#.....#\n#.#.#.#.#.#####.#.#.#.#.###.#.#.#.#######.#.#.#.#.#.###.###.#.#####.###.#########.###.#.#.###.#####.#.###.###.#####.#.#########.#.#####.###.#\n#.#.#.#.#.....#.#.#...#.#...#...#.....#...#...#.#.#...#.#...#.....#...#...#.......#...#...#...#.....#...#...#.....#.#.........#...#.....#...#\n#.#.#.#.#####.#.#.#####.#.###########.#.#######.#.###.#.#.#######.###.###.#.#######.#######.###.#######.###.#####.#.#########.#####.#####.###\n#.#...#.....#.#.#.#.....#...#.....#...#...#.....#...#.#.#...#...#...#.#...#.......#.......#...#.......#.....#.....#...........#...#.....#...#\n#.#########.#.#.#.#.#######.#.###.#.#####.#.#######.#.#.###.#.#.###.#.#.#########.#######.###.#######.#######.#################.#.#####.###.#\n#.#...#...#...#...#...#####.#...#...#####.#.###...#.#.#.#...#.#.....#...#...#.....###...#.#...#...###...#...#.#...#...#.....###.#.###...#...#\n#.#.#.#.#.###########.#####.###.#########.#.###.#.#.#.#.#.###.###########.#.#.#######.#.#.#.###.#.#####.#.#.#.#.#.#.#.#.###.###.#.###.###.###\n#...#...#...#.......#...#...#...#...###...#...#.#.#.#.#.#.###.......#.....#...#...#...#.#.#.###.#.#...#.#.#.#...#...#...#...#...#...#...#...#\n###########.#.#####.###.#.###.###.#.###.#####.#.#.#.#.#.#.#########.#.#########.#.#.###.#.#.###.#.#.#.#.#.#.#############.###.#####.###.###.#\n#...###...#...#...#...#...#...#...#.#...#...#.#.#.#.#...#...###...#.#.....#.....#.#...#...#.#...#.#.#.#.#.#...#...........#...#.....#...#...#\n#.#.###.#.#####.#.###.#####.###.###.#.###.#.#.#.#.#.#######.###.#.#.#####.#.#####.###.#####.#.###.#.#.#.#.###.#.###########.###.#####.###.###\n#.#.#...#.....#.#...#.....#...#.#...#...#.#...#.#...#.......#...#.#.#.....#.....#.###.....#.#...#.#.#.#...#...#...........#...#.....#.#...###\n#.#.#.#######.#.###.#####.###.#.#.#####.#.#####.#####.#######.###.#.#.#########.#.#######.#.###.#.#.#.#####.#############.###.#####.#.#.#####\n#.#...#.....#.#.#...#...#...#...#.#...#.#...#...#.....#.....#...#.#.#.......#...#...#...#.#.....#.#.#.#.....#.............#...#.....#.#.#...#\n#.#####.###.#.#.#.###.#.###.#####.#.#.#.###.#.###.#####.###.###.#.#.#######.#.#####.#.#.#.#######.#.#.#.#####.#############.###.#####.#.#.#.#\n#.#...#.#...#...#.....#.....#.....#.#.#.#...#...#.#...#...#.....#.#.#.....#.#.....#...#.#...#.....#.#.#.....#.#...###...###.#...#...#.#.#.#.#\n#.#.#.#.#.###################.#####.#.#.#.#####.#.#.#.###.#######.#.#.###.#.#####.#####.###.#.#####.#.#####.#.#.#.###.#.###.#.###.#.#.#.#.#.#\n#.#.#...#.................#...#...#.#.#.#.#.....#.#.#.###.......#.#.#...#...#...#...#...#...#.#.....#.#...#.#.#.#.....#.....#.....#...#...#.#\n#.#.#####################.#.###.#.#.#.#.#.#.#####.#.#.#########.#.#.###.#####.#.###.#.###.###.#.#####.#.#.#.#.#.###########################.#\n#.#.....#.................#.###.#.#.#.#.#.#...#...#.#...#...#...#.#.#...#...#.#.#...#...#...#.#...#...#.#.#.#.#.#.....#.......#.....#...#...#\n#.#####.#.#################.###.#.#.#.#.#.###.#.###.###.#.#.#.###.#.#.###.#.#.#.#.#####.###.#.###.#.###.#.#.#.#.#.###.#." <> ...}
23```
24
25```elixir
26#puzzle_input =
27 """
28###############
29#...#...#.....#
30#.#.#.#.#.###.#
31#S#...#.#.#...#
32#######.#.#.###
33#######.#.#...#
34#######.#.###.#
35###..E#...#...#
36###.#######.###
37#...###...#...#
38#.#####.#.###.#
39#.#...#.#.#...#
40#.#.#.#.#.#.###
41#...#...#...###
42###############
43 """
44```
45
46<!-- livebook:{"output":true} -->
47
48```
49warning: outdented heredoc line. The contents inside the heredoc should be indented at the same level as the closing """. The following is forbidden:
50
51 def text do
52 """
53 contents
54 """
55 end
56
57Instead make sure the contents are indented as much as the heredoc closing:
58
59 def text do
60 """
61 contents
62 """
63 end
64
65The current heredoc line is indented too little
66└─ Workspace/hauleth/advent-of-code/2024/day20.livemd#cell:iyjl3w4kz3srtwoq:3:3
67
68```
69
70<!-- livebook:{"output":true} -->
71
72```
73"###############\n#...#...#.....#\n#.#.#.#.#.###.#\n#S#...#.#.#...#\n#######.#.#.###\n#######.#.#...#\n#######.#.###.#\n###..E#...#...#\n###.#######.###\n#...###...#...#\n#.#####.#.###.#\n#.#...#.#.#...#\n#.#.#.#.#.#.###\n#...#...#...###\n###############\n"
74```
75
76```elixir
77map =
78 puzzle_input
79 |> String.split("\n")
80 |> Enum.with_index()
81 |> Enum.flat_map(fn {row, y} ->
82 row
83 |> String.split("", trim: true)
84 |> Enum.with_index()
85 |> Enum.map(fn {c, x} ->
86 {{x, y}, c}
87 end)
88 end)
89```
90
91<!-- livebook:{"output":true} -->
92
93```
94[
95 {{0, 0}, "#"},
96 {{1, 0}, "#"},
97 {{2, 0}, "#"},
98 {{3, 0}, "#"},
99 {{4, 0}, "#"},
100 {{5, 0}, "#"},
101 {{6, 0}, "#"},
102 {{7, 0}, "#"},
103 {{8, 0}, "#"},
104 {{9, 0}, "#"},
105 {{10, 0}, "#"},
106 {{11, 0}, "#"},
107 {{12, 0}, "#"},
108 {{13, 0}, "#"},
109 {{14, 0}, "#"},
110 {{15, 0}, "#"},
111 {{16, 0}, "#"},
112 {{17, 0}, "#"},
113 {{18, 0}, "#"},
114 {{19, 0}, "#"},
115 {{20, 0}, "#"},
116 {{21, 0}, "#"},
117 {{22, 0}, "#"},
118 {{23, 0}, "#"},
119 {{24, 0}, "#"},
120 {{25, 0}, "#"},
121 {{26, 0}, "#"},
122 {{27, 0}, "#"},
123 {{28, 0}, "#"},
124 {{29, 0}, "#"},
125 {{30, 0}, "#"},
126 {{31, 0}, "#"},
127 {{32, 0}, "#"},
128 {{33, 0}, "#"},
129 {{34, 0}, "#"},
130 {{35, 0}, "#"},
131 {{36, 0}, "#"},
132 {{37, 0}, "#"},
133 {{38, 0}, "#"},
134 {{39, 0}, "#"},
135 {{40, 0}, "#"},
136 {{41, 0}, "#"},
137 {{42, 0}, "#"},
138 {{43, 0}, "#"},
139 {{44, 0}, "#"},
140 {{45, 0}, "#"},
141 {{46, 0}, "#"},
142 {{47, ...}, "#"},
143 {{...}, ...},
144 {...},
145 ...
146]
147```
148
149```elixir
150%{"#" => walls, "." => road, "S" => [start], "E" => [finish]} =
151 Enum.group_by(map, &elem(&1, 1), &elem(&1, 0))
152```
153
154<!-- livebook:{"output":true} -->
155
156```
157%{
158 "#" => [
159 {0, 0},
160 {1, 0},
161 {2, 0},
162 {3, 0},
163 {4, 0},
164 {5, 0},
165 {6, 0},
166 {7, 0},
167 {8, 0},
168 {9, 0},
169 {10, 0},
170 {11, 0},
171 {12, 0},
172 {13, 0},
173 {14, 0},
174 {15, 0},
175 {16, 0},
176 {17, 0},
177 {18, 0},
178 {19, 0},
179 {20, 0},
180 {21, 0},
181 {22, 0},
182 {23, 0},
183 {24, 0},
184 {25, 0},
185 {26, 0},
186 {27, 0},
187 {28, 0},
188 {29, 0},
189 {30, 0},
190 {31, 0},
191 {32, 0},
192 {33, 0},
193 {34, 0},
194 {35, 0},
195 {36, 0},
196 {37, 0},
197 {38, 0},
198 {39, 0},
199 {40, 0},
200 {41, 0},
201 {42, 0},
202 {43, 0},
203 {44, 0},
204 {45, 0},
205 {46, 0},
206 {47, ...},
207 {...},
208 ...
209 ],
210 "." => [
211 {1, 1},
212 {2, 1},
213 {3, 1},
214 {5, 1},
215 {6, 1},
216 {7, 1},
217 {9, 1},
218 {10, 1},
219 {11, 1},
220 {13, 1},
221 {14, 1},
222 {15, 1},
223 {17, 1},
224 {18, 1},
225 {19, 1},
226 {20, 1},
227 {21, 1},
228 {22, 1},
229 {23, 1},
230 {24, 1},
231 {25, 1},
232 {27, 1},
233 {28, 1},
234 {29, 1},
235 {30, 1},
236 {31, 1},
237 {32, 1},
238 {33, 1},
239 {34, 1},
240 {35, 1},
241 {39, 1},
242 {40, 1},
243 {41, 1},
244 {43, 1},
245 {44, 1},
246 {45, 1},
247 {46, 1},
248 {47, 1},
249 {49, 1},
250 {50, 1},
251 {51, 1},
252 {53, 1},
253 {54, 1},
254 {55, 1},
255 {56, 1},
256 {57, 1},
257 {59, ...},
258 {...},
259 ...
260 ],
261 "E" => [{27, 59}],
262 "S" => [{49, 53}]
263}
264```
265
266```elixir
267defmodule Race do
268 def distances(start, finish, walls) do
269 do_distances(start, finish, 0, MapSet.new(walls), %{})
270 end
271
272 defp do_distances(finish, finish, n, _, acc),
273 do: Map.put(acc, finish, n)
274
275 defp do_distances(current, finish, n, walls, acc) do
276 acc = Map.put(acc, current, n)
277
278 current
279 |> neigh()
280 |> Enum.reject(&(&1 in walls or Map.has_key?(acc, &1)))
281 |> hd()
282 |> do_distances(finish, n + 1, walls, acc)
283 end
284
285 def neigh({x, y}, d \\ 1) do
286 for {dx, dy} <- [{0, d}, {0, -d}, {d, 0}, {-d, 0}], do: {x + dx, y + dy}
287 end
288
289 def neighbours({x, y}, r \\ 1) do
290 for dx <- -r..r,
291 dy <- -r..r,
292 {dx, dy} != {0, 0},
293 d = abs(dx) + abs(dy),
294 d <= r,
295 do: {x + dx, y + dy}
296 end
297
298 def d({xa, ya}, {xb, yb}) do
299 abs(xa - xb) + abs(ya - yb)
300 end
301end
302```
303
304<!-- livebook:{"output":true} -->
305
306```
307{:module, Race, <<70, 79, 82, 49, 0, 0, 17, ...>>, {:d, 2}}
308```
309
310```elixir
311steps = Race.distances(start, finish, walls)
312```
313
314<!-- livebook:{"output":true} -->
315
316```
317%{
318 {18, 103} => 8261,
319 {61, 121} => 7060,
320 {65, 63} => 2098,
321 {77, 129} => 6964,
322 {1, 26} => 695,
323 {116, 69} => 4441,
324 {83, 76} => 4281,
325 {117, 125} => 5656,
326 {103, 106} => 5785,
327 {30, 113} => 8041,
328 {89, 14} => 2511,
329 {35, 30} => 1133,
330 {37, 53} => 32,
331 {11, 39} => 384,
332 {131, 5} => 2998,
333 {65, 43} => 1754,
334 {139, 46} => 3615,
335 {12, 135} => 7871,
336 {65, 131} => 7046,
337 {49, 117} => 7412,
338 {29, 25} => 1108,
339 {83, 36} => 2319,
340 {47, 27} => 1556,
341 {4, 81} => 8645,
342 {13, 124} => 8295,
343 {121, 77} => 4608,
344 {103, 39} => 3756,
345 {119, 60} => 4389,
346 {13, 85} => 8604,
347 {63, 81} => 6682,
348 {111, 108} => 5755,
349 {111, 103} => 5764,
350 {15, 92} => 8587,
351 {1, 101} => 8500,
352 {20, 3} => 939,
353 {61, 95} => 6878,
354 {23, 67} => 9208,
355 {78, 75} => 6545,
356 {79, 17} => 2358,
357 {17, 137} => 7852,
358 {124, 93} => 4933,
359 {138, 9} => 3283,
360 {58, 33} => 1667,
361 {67, 105} => 6818,
362 {47, 44} => 1195,
363 {122, 137} => 5595,
364 {13, 55} => 154,
365 {97, 138} => 6129,
366 {75, ...} => 2165,
367 {...} => 1616,
368 ...
369}
370```
371
372## Part 1
373
374```elixir
375Enum.reduce(steps, 0, fn {pos, start}, acc ->
376 count =
377 steps
378 |> Map.take(Race.neighbours(pos, 2))
379 |> Enum.count(fn {last, finish} ->
380 finish - start - Race.d(pos, last) >= 100
381 end)
382
383 count + acc
384end)
385```
386
387<!-- livebook:{"output":true} -->
388
389```
3901393
391```
392
393## Part 2
394
395We can notice that we are looking for shortcuts in circle of radius $r$ defined in Taxicab metric ($d(a, b) = \sum_{i} |a_i - b_i|$). That makes code pretty simple and allows us to reuse ideas from Part 1.
396
397```elixir
398steps
399|> Task.async_stream(
400 fn {pos, start} ->
401 steps
402 |> Map.take(Race.neighbours(pos, 20))
403 |> Enum.count(fn {last, finish} ->
404 finish - start - Race.d(pos, last) >= 100
405 end)
406 end,
407 ordered: false
408)
409|> Enum.reduce(0, fn {:ok, count}, acc ->
410 count + acc
411end)
412```
413
414<!-- livebook:{"output":true} -->
415
416```
417990096
418```
419
420<!-- livebook:{"offset":11400,"stamp":{"token":"XCP.ONwDp6zRpWXsXASH95Q0puANk15Li1hG2FDCrv6Gqu42Q7k9pb_Te_6RDoUE0dp3yYbG7jry8-6iHGJvcZtsDFstlznyVHk9HVhXRZiC2uQczaOfF4K8HQL9QuzNguTht7A","version":2}} -->