this repo has no description
hauleth.dev
1<!-- livebook:{"persist_outputs":true} -->
2
3# Day 12
4
5```elixir
6Mix.install([
7 {:kino_aoc, git: "https://github.com/ljgago/kino_aoc"},
8 {:libgraph, ">= 0.0.0"}
9])
10```
11
12<!-- livebook:{"output":true} -->
13
14```
15:ok
16```
17
18## Section
19
20<!-- livebook:{"attrs":{"day":"12","session_secret":"ADVENT_OF_CODE_SESSION","variable":"puzzle_input","year":"2022"},"chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->
21
22```elixir
23{:ok, puzzle_input} =
24 KinoAOC.download_puzzle("2022", "12", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
25```
26
27<!-- livebook:{"output":true} -->
28
29```
30{:ok,
31 "abccccaaacaccccaaaaacccccccaaccccccccaaaaaaccccccaaaaaccccccccccaaaaaaaaacccccccaaaaaaaaaaaaaaccaaaaaccccccccccccaccacccccccccccccccccccccccccccccccccccccccaaaaaa\nabccaacaaaaaccaaaaacccccaaaaaccccccccaaaaaaccccccaaaaaacccccccccaaaaaaaaaaaaacccaaaaaaaaaaaaaaaaaaaaaccccccccccccaaaacccccccccccccccccccccccccccccccccccccccaaaaaa\nabccaaaaaaaaccaaaaaacccccaaaaaccccccaaaaaaaacccccaaaaaaccccccccccaaaaaaaaaaaacccaaaaaacaaaaaacaaaaaaaaccccccccccaaaaacccccaccccccccccccccccccaaacccccccccccccaaaaa\nabcccaaaaaccccccaaaacccccaaaaacccccaaaaaaaaaaccccaaaaaacccccccccaaaaaaaaaaaaaacaaaaaaaaaaaaaacaaaaaaaaccccccccccaaaaaacccaaacccccccccccccccccaaaccccccccccccccaaaa\nabaaacaaaaacccccacccccccaaaaaccccccaaaaaaaaaaccccccaaaccccccccccaaaaaaaaacaaaaaaaaaaaaaaaaaaacccaaacaccaaaccccccaaaaaaaacaaacccccccccccaaccccaaacccccccccccccccaac\nabaaacaacaaaaccccccccccccccaaccccccacaaaaacccccaacccccccccccccccaaaacaaaaaaaaaacccaacccaaacaacccaaccccaaaaccccccccaacaaaaaaaaaaccccccccaaaaccaaaccccccccccccccaaac\nabaaccaaccaaacacccccccccccccccccccccccaaaacccaaaaaaccaaaccccccccccaacaaaaaaaaaacccaaccccccccccccccccccaaaaccccccccccccaaaaaaaaaccccccciiiiiaaaaacccccccccccccccccc\nabaaccccaaaaaaaacccccccccccccccccccccccaaccccaaaaaaccaaaaaccccacccaaccaaacaaaaacccccccccccccccaacccccccaaaccccccccccccccaaaaacccccccciiiiiiiiaaaaaccccccaaaccccccc\nabaaacccaaaaaaaacccccccccccccccccccccccccccccaaaaaacaaaaaccccaaaaaaaccaaccaaacccccccaaaaacacccaaccccccccccaacccccccccccaaaaaaccccccciiiiiiiiijjaaaaaccccaaacaccccc\nabaaaccccaaaaaaccccccccccccccccccccaaccccccccaaaaaccaaaaacccccaaaaaaaaccccccccccccccaaaaaaaaaaaaccccccccccaaacaaccccccaaaaaaaccccccciiinnnnoijjjjjjjjjjaaaaaaacccc\nabccccccccaaaaacccccaacccccccccccaaaacccccccccaaaacccaaaaaccccaaaaaaaaacccccccccccccaaaaaaaaaaaaaaccccccccaaaaaacccaacaaacaaacccccchhinnnnnoojjjjjjjjjkkaaaaaacccc\nabcccccccaaaaaacaaacaacccccccccccaaaaaaccccccccccccccaacccccccaaaaaaaaacaaccccccccccaaaaaaaaaaaaaaacccccaaaaaaacccaaaaccccccacaaccchhinnnnnoooojjjjjjkkkkaaaaccccc\nabaacccaccaaaccccaaaaaccccccccccccaaaaccccccccccccccccccccccccaaaaaaaacaaaaaaaccccccaaaaaaaaaaaaaaacccccaaaaaaacccaaaaccccaaacaaachhhnnntttuooooooooppkkkaaaaccccc\nabaacccaaaaaaaccccaaaaaacccccccccaaaaaccccccccccccccccccccccccaaaaaaacccaaaaacccccccccaaacaaaaaaaaccccccccaaaaacccaaaacccccaaaaacchhhnnnttttuooooooppppkkkaaaccccc\nabaacccaaaaaaccccaaaaaaacccccccccaacaaccccccccccccccccccccccaaaccaaaccaaaaaaacccccccccccccaaaaaaaccccccaacaacaaacccccccccccaaaaaahhhhnntttttuuouuuuupppkkkcccccccc\nabaaaacaaaaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccaaaacccaaacaaaaaaaaccccccccccccaccaaaccccccaaacaaccccccccccccccaaaaaahhhhnnntttxxxuuuuuuupppkkkcccccccc\nabaaaacaaaaaaaaaaacaaacccaaacccccccccccccccccccccacccccccccaaaacccccccaaaaaaaaccccccccccccccccaaacccccaaacaaacccccccccccccaaaaaahhhhmnnttxxxxuuyuuuuuppkkkcccccccc\nabaaaccaaaaaaaaccccaaaccccaaaccacccccccccccaaaaaaaaccccccccaaaacccccccccaaacaacccccccccccccccccccccaaaaaaaaaacccccacccccccaacaghhhmmmmtttxxxxxxyyyuupppkkccccccccc\nabaaccaaaaaaaccccccccccccaaaaaaaacccccccccccaaaaaaccccccccccccccccccccccaaccccccaacccccccccccccccccaaaaaaaaacccccaaccccccccccagggmmmmttttxxxxxyyyyvvppkkkccccccccc\nabaacccaccaaacccccccccccaaaaaaaaccccccccccccaaaaaaccccccccccccccccccccccccccaaacaaaccccccccccccccccccaaaaaccccaaaaacaacccccccgggmmmmttttxxxxxyyyyvvpppiiiccccccccc\nSbaaaaaccccaaccccccccccaaaaaaaaacacccccccccaaaaaaaacccccccccccccccaacccccccccaaaaaccccccccccaaaacccccaaaaaacccaaaaaaaaccaaaccgggmmmsssxxxEzzzzyyvvvpppiiiccccccccc\nabaaaaaccccccccccccccccaaaaaaaaaaaaaaaaaccaaaaaaaaaacccccccccccaaaaacccccccccaaaaaaaccccccccaaaaaccccaaaaaaaccccaaaaacccaaaaagggmmmsssxxxxxyyyyyyvvqqqiiiccccccccc\nabaaaaacccccccccccccccccaaaaaaaacaaaaaacccaaaaaaaaaaccccccccccccaaaaacccccccaaaaaaaacccccccaaaaaaccccaaacaaacccaaaaacccaaaaaagggmmmssswwwwwyyyyyyyvvqqqiiicccccccc\nabaaaaccccccccccccccccccccaaaaaaaaaaaaacccacacaaacccccccccccccccaaaaacccccccaaaaaaaacccccccaaaaaaccccacccccccccaacaaaccaaaaaagggmmmsssswwwwyyyyyyyvvvqqiiicccccccc\nabaaaaacccccccccccccccccccaacccaaaaaaaaaccccccaaaccccccccccccccaaaaaccccccccaacaaacccccccccaaaaaacccccccccccccccccaaccccaaaaagggmmmmssssswwyywwvvvvvvqqiiicccccccc\nabaaaaacccccccccccccc" <> ...}
32```
33
34```elixir
35# puzzle_input = """
36# Sabqponm
37# abcryxxl
38# accszExk
39# acctuvwj
40# abdefghi
41# """
42```
43
44<!-- livebook:{"output":true} -->
45
46```
47nil
48```
49
50```elixir
51min = ?a - ?a
52max = ?z - ?a
53
54{map, start, stop} =
55 puzzle_input
56 |> String.split("\n", trim: true)
57 |> Enum.map(&to_charlist/1)
58 |> Enum.with_index()
59 |> Enum.flat_map(fn {line, y} ->
60 line
61 |> Enum.with_index()
62 |> Enum.map(fn {c, x} -> {{x, y}, c} end)
63 end)
64 |> Enum.reduce({%{}, nil, nil}, fn {p, v}, {map, s, e} ->
65 case v do
66 ?S -> {Map.put(map, p, min), p, e}
67 ?E -> {Map.put(map, p, max), s, p}
68 _ -> {Map.put(map, p, v - ?a), s, e}
69 end
70 end)
71
72graph =
73 map
74 |> Enum.reduce(Graph.new(), fn {p, v}, graph ->
75 {x, y} = p
76
77 graph =
78 if map[{x - 1, y}] && v + 1 >= map[{x - 1, y}],
79 do: Graph.add_edge(graph, {x, y}, {x - 1, y}, label: [v, map[{x - 1, y}]]),
80 else: graph
81
82 graph =
83 if map[{x + 1, y}] && v + 1 >= map[{x + 1, y}],
84 do: Graph.add_edge(graph, {x, y}, {x + 1, y}, label: [v, map[{x + 1, y}]]),
85 else: graph
86
87 graph =
88 if map[{x, y - 1}] && v + 1 >= map[{x, y - 1}],
89 do: Graph.add_edge(graph, {x, y}, {x, y - 1}, label: [v, map[{x, y - 1}]]),
90 else: graph
91
92 graph =
93 if map[{x, y + 1}] && v + 1 >= map[{x, y + 1}],
94 do: Graph.add_edge(graph, {x, y}, {x, y + 1}, label: [v, map[{x, y + 1}]]),
95 else: graph
96 end)
97```
98
99<!-- livebook:{"output":true} -->
100
101```
102warning: variable "graph" is unused (there is a variable with the same name in the context, use the pin operator (^) to match on it or prefix this variable with underscore if it is not meant to be used)
103 2022/day12.livemd#cell:6nz6sdhe57lxfvshc57dctj7qaalwwz3:42
104
105```
106
107<!-- livebook:{"output":true} -->
108
109```
110#Graph<type: directed, num_vertices: 6642, num_edges: 24117>
111```
112
113## Task 1
114
115```elixir
116length(Graph.get_shortest_path(graph, start, stop)) - 1
117```
118
119<!-- livebook:{"output":true} -->
120
121```
122437
123```
124
125```elixir
126graph.vertices
127```
128
129<!-- livebook:{"output":true} -->
130
131```
132%{
133 1148931603 => {118, 31},
134 15476201 => {158, 33},
135 3480980581 => {19, 26},
136 513279067 => {86, 0},
137 1642831488 => {111, 2},
138 669567979 => {38, 18},
139 1898334127 => {77, 28},
140 2414760132 => {41, 27},
141 1433989350 => {134, 33},
142 4010762779 => {100, 37},
143 1619384061 => {142, 27},
144 2736818014 => {105, 29},
145 3132807327 => {56, 13},
146 1603662291 => {94, 23},
147 183280155 => {35, 27},
148 2518352043 => {127, 27},
149 824501714 => {15, 33},
150 1813555375 => {70, 18},
151 733666720 => {72, 5},
152 4293490381 => {13, 24},
153 4037128590 => {87, 10},
154 1287605231 => {99, 3},
155 2697150767 => {19, 29},
156 3345146674 => {78, 5},
157 811252706 => {132, 14},
158 3035418479 => {156, 5},
159 2090318173 => {149, 1},
160 1306366779 => {71, 39},
161 113692275 => {158, 28},
162 1809958846 => {4, 0},
163 2979249361 => {95, 23},
164 712034521 => {2, 34},
165 838646858 => {127, 2},
166 2636390019 => {97, 34},
167 200998860 => {73, 23},
168 2440897975 => {91, 7},
169 2757930521 => {103, 38},
170 2626031906 => {92, 21},
171 4000959801 => {44, 20},
172 2762901234 => {69, 16},
173 3967362516 => {72, 9},
174 1858208296 => {81, 16},
175 3063825234 => {140, 14},
176 1669140133 => {46, 21},
177 684221776 => {146, 38},
178 623366404 => {63, 40},
179 3623360588 => {149, 6},
180 2885933829 => {137, 14},
181 3219344086 => {136, ...},
182 3451324297 => {...},
183 ...
184}
185```
186
187## Task 2
188
189```elixir
190tgraph = Graph.transpose(graph)
191```
192
193<!-- livebook:{"output":true} -->
194
195```
196#Graph<type: directed, num_vertices: 6642, num_edges: 24117>
197```
198
199```elixir
200lowest =
201 Enum.flat_map(map, fn
202 {p, 0} -> [p]
203 _ -> []
204 end)
205```
206
207<!-- livebook:{"output":true} -->
208
209```
210[
211 {59, 38},
212 {38, 5},
213 {76, 17},
214 {66, 36},
215 {54, 26},
216 {10, 18},
217 {3, 21},
218 {42, 40},
219 {73, 32},
220 {43, 36},
221 {2, 9},
222 {80, 31},
223 {20, 12},
224 {63, 11},
225 {5, 15},
226 {76, 4},
227 {136, 4},
228 {3, 9},
229 {90, 11},
230 {85, 39},
231 {24, 29},
232 {91, 28},
233 {55, 27},
234 {108, 10},
235 {84, 4},
236 {9, 9},
237 {161, 38},
238 {3, 33},
239 {68, 22},
240 {143, 3},
241 {49, 8},
242 {70, 26},
243 {39, 25},
244 {18, 13},
245 {88, 0},
246 {32, 21},
247 {96, 3},
248 {84, 40},
249 {53, 1},
250 {88, 30},
251 {120, 10},
252 {36, 4},
253 {115, 13},
254 {112, 3},
255 {42, 0},
256 {4, 17},
257 {35, 12},
258 {114, 19},
259 {20, ...},
260 {...},
261 ...
262]
263```
264
265```elixir
266# Copied BF implementation from `libgraph` to optimise it
267
268defmodule BellmanFord do
269 @moduledoc """
270 The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single
271 source vertex to all of the other vertices in a weighted digraph.
272 It is capable of handling graphs in which some of the edge weights are negative numbers
273 Time complexity: O(VLogV)
274 """
275
276 @type distance :: %{Graph.vertex_id() => integer}
277
278 @doc """
279 Returns nil when graph has negative cycle.
280 """
281 @spec call(Graph.t(), Graph.vertex()) :: [Graph.vertex()] | nil
282 def call(%Graph{vertices: vs, edges: meta}, source) do
283 distances = source |> Graph.Utils.vertex_id() |> init_distances(vs)
284
285 weights = Enum.map(meta, &edge_weight/1)
286
287 distances =
288 for _ <- 1..map_size(vs),
289 {{u, v}, weight} <- weights,
290 reduce: distances do
291 distances ->
292 case distances do
293 %{^u => :infinity} ->
294 distances
295
296 %{^u => du, ^v => dv} when du + weight < dv ->
297 %{distances | v => du + weight}
298
299 _ ->
300 distances
301 end
302 end
303
304 if has_negative_cycle?(distances, weights) do
305 nil
306 else
307 Map.new(distances, fn {k, v} -> {Map.fetch!(vs, k), v} end)
308 end
309 end
310
311 @spec init_distances(Graph.vertex(), Graph.vertices()) :: distance
312 defp init_distances(vertex_id, vertices) do
313 Map.new(vertices, fn
314 {id, _vertex} when id == vertex_id -> {id, 0}
315 {id, _} -> {id, :infinity}
316 end)
317 end
318
319 @spec edge_weight(term) :: float
320 defp edge_weight({e, edge_value}), do: {e, edge_value |> Map.values() |> List.first()}
321
322 defp has_negative_cycle?(%{} = distances, meta) do
323 Enum.any?(meta, fn {{u, v}, weight} ->
324 %{^u => du, ^v => dv} = distances
325
326 du != :infinity and du + weight < dv
327 end)
328 end
329end
330```
331
332<!-- livebook:{"output":true} -->
333
334```
335{:module, BellmanFord, <<70, 79, 82, 49, 0, 0, 18, ...>>, {:has_negative_cycle?, 2}}
336```
337
338```elixir
339paths =
340 tgraph
341 # |> Graph.bellman_ford(stop)
342 |> BellmanFord.call(stop)
343```
344
345<!-- livebook:{"output":true} -->
346
347```
348%{
349 {76, 13} => :infinity,
350 {38, 2} => :infinity,
351 {1, 26} => 430,
352 {140, 11} => 100,
353 {32, 15} => 388,
354 {89, 14} => 328,
355 {35, 30} => 392,
356 {156, 9} => :infinity,
357 {4, 5} => 454,
358 {74, 12} => :infinity,
359 {11, 39} => 425,
360 {131, 5} => 323,
361 {22, 38} => 413,
362 {29, 25} => 403,
363 {86, 10} => :infinity,
364 {83, 36} => 366,
365 {29, 26} => 402,
366 {47, 27} => :infinity,
367 {9, 34} => 426,
368 {137, 16} => 12,
369 {90, 0} => :infinity,
370 {103, 39} => 289,
371 {126, 13} => :infinity,
372 {47, 38} => :infinity,
373 {128, 35} => 268,
374 {20, 3} => 412,
375 {145, 20} => 24,
376 {143, 39} => 247,
377 {79, 17} => 335,
378 {75, 0} => :infinity,
379 {150, 18} => 167,
380 {147, 10} => 178,
381 {148, 26} => 75,
382 {76, 2} => :infinity,
383 {138, 9} => 104,
384 {58, 33} => 372,
385 {150, 5} => 296,
386 {54, 31} => 374,
387 {22, 37} => 412,
388 {75, 36} => :infinity,
389 {91, 35} => :infinity,
390 {143, 4} => :infinity,
391 {121, 27} => 283,
392 {91, 38} => :infinity,
393 {159, 26} => 268,
394 {131, 24} => 124,
395 {58, 10} => 367,
396 {111, 14} => :infinity,
397 {75, ...} => 345,
398 {...} => 411,
399 ...
400}
401```
402
403```elixir
404paths
405|> Map.take(lowest)
406|> Map.values()
407|> Enum.min()
408```
409
410<!-- livebook:{"output":true} -->
411
412```
413430
414```