this repo has no description
hauleth.dev
1<!-- livebook:{"persist_outputs":true} -->
2
3# Day 16
4
5```elixir
6Mix.install([:kino_aoc, :image])
7```
8
9## Setup
10
11<!-- livebook:{"attrs":"eyJhc3NpZ25fdG8iOiJwdXp6bGVfaW5wdXQiLCJkYXkiOiIxNiIsInNlc3Npb25fc2VjcmV0IjoiQURWRU5UX09GX0NPREVfU0VTU0lPTiIsInllYXIiOiIyMDI0In0","chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->
12
13```elixir
14{:ok, puzzle_input} =
15 KinoAOC.download_puzzle("2024", "16", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
16```
17
18<!-- livebook:{"output":true} -->
19
20```
21{:ok,
22 "#############################################################################################################################################\n#.....#.......#.............#.........#.......................#.......#...#...............#.....#.#.................................#.#....E#\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%{?# => walls, ?S => [start], ?E => [finish]} =
27 puzzle_input
28 |> String.trim()
29 |> String.split("\n", trim: true)
30 |> Enum.with_index()
31 |> Enum.flat_map(fn {row, y} ->
32 row
33 |> String.trim()
34 |> String.to_charlist()
35 |> Enum.with_index()
36 |> Enum.map(fn {char, x} ->
37 {{x, y}, char}
38 end)
39 end)
40 |> Enum.group_by(&elem(&1, 1), &elem(&1, 0))
41
42walls = MapSet.new(walls)
43```
44
45<!-- livebook:{"output":true} -->
46
47```
48MapSet.new([
49 {76, 13},
50 {112, 138},
51 {38, 2},
52 {124, 56},
53 {83, 76},
54 {140, 11},
55 {100, 134},
56 {75, 140},
57 {103, 106},
58 {68, 134},
59 {124, 60},
60 {35, 30},
61 {2, 132},
62 {8, 50},
63 {78, 98},
64 {101, 62},
65 {98, 136},
66 {95, 56},
67 {74, 12},
68 {102, 74},
69 {22, 38},
70 {14, 86},
71 {12, 135},
72 {86, 10},
73 {29, 26},
74 {4, 81},
75 {31, 42},
76 {9, 34},
77 {137, 16},
78 {86, 138},
79 {90, 0},
80 {14, 122},
81 {120, 42},
82 {102, 57},
83 {84, 102},
84 {138, 124},
85 {0, 101},
86 {116, 96},
87 {54, 138},
88 {18, 134},
89 {82, 60},
90 {15, 92},
91 {58, 58},
92 {78, 75},
93 {75, 0},
94 {16, 73},
95 {76, 2},
96 {58, 84},
97 {138, ...},
98 {...},
99 ...
100])
101```
102
103```elixir
104{_, {w, h}} = Enum.min_max(walls)
105
106w = w + 1
107h = h + 1
108```
109
110<!-- livebook:{"output":true} -->
111
112```
113141
114```
115
116```elixir
117put_in(%{}, [Access.key(:a, %{}), :b], 10)
118```
119
120<!-- livebook:{"output":true} -->
121
122```
123%{a: %{b: 10}}
124```
125
126```elixir
127defmodule Race.B do
128 @turns ~w'^ > v <'a
129
130 defguardp score(elements, pos, dir) when :erlang.map_get({pos, dir}, elements).score
131
132 def search_paths(start, finish, dir \\ :>, walls) when dir in @turns do
133 result = do_search([{0, [{start, dir}]}], walls, %{})
134
135 %{paths: visited, score: score} = result[{finish, :>}]
136
137 all = get_all(visited, result)
138
139 {score, all}
140 end
141
142 def get_all(path, seen) do
143 Enum.reduce(path, MapSet.new(), fn p, acc ->
144 path = MapSet.new(seen[p].paths, fn {p, _} -> p end)
145 MapSet.union(acc, path)
146 end)
147 end
148
149 def do_search([], _, visited), do: visited
150
151 def do_search([{cost, [{curr, dir} | _] = path} | rest], walls, visited)
152 when cost == score(visited, curr, dir) do
153 visited = Map.update!(visited, {curr, dir}, &%{&1 | paths: path})
154
155 do_search(rest, walls, visited)
156 end
157
158 def do_search([{cost, [{curr, prev} | _] = path} | rest], walls, visited)
159 when not is_map_key(visited, {curr, prev})
160 when cost < score(visited, curr, prev) do
161 visited = Map.put(visited, {curr, prev}, %{score: cost, paths: path})
162
163 @turns
164 |> Enum.map(fn dir -> {cost + cost(prev, dir), [{step(curr, dir), dir} | path]} end)
165 |> Enum.reject(fn {_cost, [{pos, _} | _]} -> pos in walls end)
166 |> sort_merge(rest)
167 |> do_search(walls, visited)
168 end
169
170 def do_search([{_, [_curr | _]} | rest], walls, visited),
171 do: do_search(rest, walls, visited)
172
173 # Going straight is cheap and turning is costly
174 defp cost(a, a), do: 1
175 defp cost(_, _), do: 1001
176
177 defp step({x, y}, :^), do: {x, y - 1}
178 defp step({x, y}, :>), do: {x + 1, y}
179 defp step({x, y}, :v), do: {x, y + 1}
180 defp step({x, y}, :<), do: {x - 1, y}
181
182 defp sort_merge([], bs), do: bs
183 defp sort_merge(as, []), do: as
184
185 defp sort_merge([a | as], [b | bs]) do
186 if a < b do
187 [a | sort_merge(as, [b | bs])]
188 else
189 [b | sort_merge([a | as], bs)]
190 end
191 end
192end
193```
194
195<!-- livebook:{"output":true} -->
196
197```
198{:module, Race.B, <<70, 79, 82, 49, 0, 0, 23, ...>>, {:sort_merge, 2}}
199```
200
201```elixir
202{score, paths} = Race.B.search_paths(start, finish, walls)
203```
204
205<!-- livebook:{"output":true} -->
206
207```
208{134588,
209 MapSet.new([
210 {77, 129},
211 {17, 138},
212 {17, 137},
213 {37, 139},
214 {19, 137},
215 {100, 131},
216 {139, 68},
217 {14, 139},
218 {79, 128},
219 {19, 138},
220 {50, 137},
221 {139, 67},
222 {137, 104},
223 {137, 117},
224 {131, 49},
225 {107, 125},
226 {3, 127},
227 {135, 64},
228 {4, 131},
229 {21, 134},
230 {63, 127},
231 {101, 124},
232 {5, 139},
233 {125, 14},
234 {129, 48},
235 {139, 70},
236 {21, 119},
237 {17, 129},
238 {137, 120},
239 {17, 136},
240 {131, 120},
241 {32, 139},
242 {133, 21},
243 {102, 123},
244 {12, 111},
245 {123, 19},
246 {112, 127},
247 {73, 129},
248 {7, 116},
249 {127, 22},
250 {7, 137},
251 {9, 131},
252 {24, 133},
253 {137, 95},
254 {8, 133},
255 {134, 7},
256 {129, ...},
257 {...},
258 ...
259 ])}
260```
261
262## Part 1
263
264```elixir
265score
266```
267
268<!-- livebook:{"output":true} -->
269
270```
271134588
272```
273
274```elixir
275Image.new!(w, h)
276|> Image.mutate(fn img ->
277 for {x, y} <- walls do
278 Image.Draw.point(img, x, y, color: [128, 0, 0])
279 end
280
281 for {x, y} <- paths do
282 Image.Draw.point(img, x, y, color: [0, 255, 0])
283 end
284
285 img
286end)
287|> elem(1)
288|> Image.resize!(6, interpolate: :nearest)
289```
290
291## Part 2
292
293```elixir
294MapSet.size(paths)
295```
296
297<!-- livebook:{"output":true} -->
298
299```
300625
301```
302
303<!-- livebook:{"offset":9337,"stamp":{"token":"XCP.AVI7h-Nq9jZKx9YmL5qYerJkeKKqddhzKrKUkab-HwNDUM8nQItD1O_rd2ROsJxc96gwIzwrMAixlIdLeZAgOVhtCs22LZM44Wl1VwcpYbg3RNCdgwIjqGheO5YrCGrEGJc","version":2}} -->