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"},"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:7urrvoyk6ltuxa4kdqc63nncfh37x2fn:30
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[32256290, 409066827, 186924390, 1502865800, 887663648, 2543466388, 697356458, 1070575781,
211 1659702078, 4000784021, 1947564743, 2361038489, 3904452243, 3615669650, 270460033, 1281654811,
212 3153535741, 2393890474, 3946102901, 2210758189, 2982223724, 2654353783, 2656280720, 3935389969,
213 2818948768, 4279780723, 3595206681, 3496428192, 2269119594, 2583881244, 3997991000, 520325395,
214 457672928, 1453390554, 3289433936, 2574402082, 1560492086, 3242480874, 389839366, 4176230802,
215 1147783117, 2469841095, 2034019869, 438932546, 1799582666, 1100008137, 467060197, 162439868,
216 3928107970, 800548913, ...]
217```
218
219```elixir
220# Copied BF implementation from `libgraph` to optimise it
221
222defmodule BellmanFord do
223 @moduledoc """
224 The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single
225 source vertex to all of the other vertices in a weighted digraph.
226 It is capable of handling graphs in which some of the edge weights are negative numbers
227 Time complexity: O(VLogV)
228 """
229
230 @type distance :: %{Graph.vertex_id() => integer}
231
232 @doc """
233 Returns nil when graph has negative cycle.
234 """
235 @spec call(Graph.t(), Graph.vertex()) :: [Graph.vertex()] | nil
236 def call(%Graph{vertices: vs, edges: meta}, source) do
237 distances = source |> Graph.Utils.vertex_id() |> init_distances(vs)
238
239 weights = Enum.map(meta, &edge_weight/1)
240
241 distances =
242 for _ <- 1..map_size(vs),
243 {{u, v}, weight} <- weights,
244 reduce: distances do
245 distances ->
246 case distances do
247 %{^u => :infinity} ->
248 distances
249
250 %{^u => du, ^v => dv} when du + weight < dv ->
251 %{distances | v => du + weight}
252
253 _ ->
254 distances
255 end
256 end
257
258 if has_negative_cycle?(distances, weights) do
259 nil
260 else
261 Map.new(distances, fn {k, v} -> {Map.fetch!(vertices, k), v} end)
262 end
263 end
264
265 @spec init_distances(Graph.vertex(), Graph.vertices()) :: distance
266 defp init_distances(vertex_id, vertices) do
267 Map.new(vertices, fn
268 {id, _vertex} when id == vertex_id -> {id, 0}
269 {id, _} -> {id, :infinity}
270 end)
271 end
272
273 @spec edge_weight(term) :: float
274 defp edge_weight({e, edge_value}), do: {e, edge_value |> Map.values() |> List.first()}
275
276 defp has_negative_cycle?(%{} = distances, meta) do
277 Enum.any?(meta, fn {{u, v}, weight} ->
278 %{^u => du, ^v => dv} = distances
279
280 du != :infinity and du + weight < dv
281 end)
282 end
283end
284```
285
286<!-- livebook:{"output":true} -->
287
288```
289{:module, BellmanFord, <<70, 79, 82, 49, 0, 0, 19, ...>>, {:has_negative_cycle?, 2}}
290```
291
292```elixir
293min_paths =
294 tgraph
295 # |> Graph.bellman_ford(stop)
296 |> BellmanFord.call(stop)
297 |> Map.take(lowest)
298 |> Map.values()
299```
300
301<!-- livebook:{"output":true} -->
302
303```
304[:infinity, :infinity, :infinity, 454, :infinity, :infinity, :infinity, :infinity, :infinity,
305 :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity,
306 :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity,
307 :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity,
308 :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity, :infinity,
309 :infinity, :infinity, :infinity, :infinity, :infinity, ...]
310```
311
312```elixir
313Enum.min(min_paths)
314```
315
316<!-- livebook:{"output":true} -->
317
318```
319430
320```