this repo has no description
hauleth.dev
1<!-- livebook:{"persist_outputs":true} -->
2
3# Day 16
4
5```elixir
6Mix.install([
7 {:kino_aoc, git: "https://github.com/ljgago/kino_aoc"},
8 {:libgraph, github: "hauleth/libgraph", ref: "perf/bellman-ford-implementation"}
9])
10```
11
12<!-- livebook:{"output":true} -->
13
14```
15:ok
16```
17
18## Setup
19
20<!-- livebook:{"attrs":{"day":"16","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", "16", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
25```
26
27<!-- livebook:{"output":true} -->
28
29```
30{:ok,
31 "Valve QJ has flow rate=11; tunnels lead to valves HB, GL\nValve VZ has flow rate=10; tunnel leads to valve NE\nValve TX has flow rate=19; tunnels lead to valves MG, OQ, HM\nValve ZI has flow rate=5; tunnels lead to valves BY, ON, RU, LF, JR\nValve IH has flow rate=0; tunnels lead to valves YB, QS\nValve QS has flow rate=22; tunnel leads to valve IH\nValve QB has flow rate=0; tunnels lead to valves QX, ES\nValve NX has flow rate=0; tunnels lead to valves UH, OP\nValve PJ has flow rate=0; tunnels lead to valves OC, UH\nValve OR has flow rate=6; tunnels lead to valves QH, BH, HB, JD\nValve OC has flow rate=7; tunnels lead to valves IZ, JR, TA, ZH, PJ\nValve UC has flow rate=0; tunnels lead to valves AA, BY\nValve QX has flow rate=0; tunnels lead to valves AA, QB\nValve IZ has flow rate=0; tunnels lead to valves OC, SX\nValve AG has flow rate=13; tunnels lead to valves NW, GL, SM\nValve ON has flow rate=0; tunnels lead to valves MO, ZI\nValve XT has flow rate=18; tunnels lead to valves QZ, PG\nValve AX has flow rate=0; tunnels lead to valves UH, MO\nValve JD has flow rate=0; tunnels lead to valves OR, SM\nValve HM has flow rate=0; tunnels lead to valves TX, QH\nValve LF has flow rate=0; tunnels lead to valves ZI, UH\nValve QH has flow rate=0; tunnels lead to valves OR, HM\nValve RT has flow rate=21; tunnel leads to valve PG\nValve NE has flow rate=0; tunnels lead to valves VZ, TA\nValve OQ has flow rate=0; tunnels lead to valves TX, GE\nValve AA has flow rate=0; tunnels lead to valves QZ, UC, OP, QX, EH\nValve UH has flow rate=17; tunnels lead to valves PJ, NX, AX, LF\nValve GE has flow rate=0; tunnels lead to valves YB, OQ\nValve EH has flow rate=0; tunnels lead to valves AA, MO\nValve MG has flow rate=0; tunnels lead to valves TX, NW\nValve YB has flow rate=20; tunnels lead to valves IH, GE, XG\nValve MO has flow rate=15; tunnels lead to valves EH, ON, AX, ZH, CB\nValve JR has flow rate=0; tunnels lead to valves ZI, OC\nValve GL has flow rate=0; tunnels lead to valves AG, QJ\nValve SM has flow rate=0; tunnels lead to valves JD, AG\nValve HB has flow rate=0; tunnels lead to valves OR, QJ\nValve TA has flow rate=0; tunnels lead to valves OC, NE\nValve PG has flow rate=0; tunnels lead to valves RT, XT\nValve XG has flow rate=0; tunnels lead to valves CB, YB\nValve ES has flow rate=9; tunnels lead to valves QB, FL\nValve BH has flow rate=0; tunnels lead to valves RU, OR\nValve FL has flow rate=0; tunnels lead to valves SX, ES\nValve CB has flow rate=0; tunnels lead to valves MO, XG\nValve QZ has flow rate=0; tunnels lead to valves AA, XT\nValve BY has flow rate=0; tunnels lead to valves UC, ZI\nValve ZH has flow rate=0; tunnels lead to valves MO, OC\nValve OP has flow rate=0; tunnels lead to valves NX, AA\nValve NW has flow rate=0; tunnels lead to valves MG, AG\nValve RU has flow rate=0; tunnels lead to valves ZI, BH\nValve SX has flow rate=16; tunnels lead to valves IZ, FL"}
32```
33
34```elixir
35# puzzle_input = """
36# Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
37# Valve BB has flow rate=13; tunnels lead to valves CC, AA
38# Valve CC has flow rate=2; tunnels lead to valves DD, BB
39# Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
40# Valve EE has flow rate=3; tunnels lead to valves FF, DD
41# Valve FF has flow rate=0; tunnels lead to valves EE, GG
42# Valve GG has flow rate=0; tunnels lead to valves FF, HH
43# Valve HH has flow rate=22; tunnel leads to valve GG
44# Valve II has flow rate=0; tunnels lead to valves AA, JJ
45# Valve JJ has flow rate=21; tunnel leads to valve II
46# """
47```
48
49<!-- livebook:{"output":true} -->
50
51```
52nil
53```
54
55```elixir
56{{start, _}, valves} =
57 valves =
58 puzzle_input
59 |> String.split("\n", trim: true)
60 |> Kino.render()
61 |> Enum.map(fn line ->
62 %{
63 "name" => name,
64 "rate" => rate,
65 "routes" => routes
66 } =
67 Regex.named_captures(
68 ~r/Valve (?<name>..).*rate=(?<rate>\d+);.*valves? (?<routes>.*)$/,
69 line
70 )
71
72 {name, %{rate: String.to_integer(rate), routes: String.split(routes, ~r/,\s*/, trim: true)}}
73 end)
74 |> then(&{hd(&1), Map.new(&1)})
75```
76
77<!-- livebook:{"output":true} -->
78
79```
80["Valve QJ has flow rate=11; tunnels lead to valves HB, GL",
81 "Valve VZ has flow rate=10; tunnel leads to valve NE",
82 "Valve TX has flow rate=19; tunnels lead to valves MG, OQ, HM",
83 "Valve ZI has flow rate=5; tunnels lead to valves BY, ON, RU, LF, JR",
84 "Valve IH has flow rate=0; tunnels lead to valves YB, QS",
85 "Valve QS has flow rate=22; tunnel leads to valve IH",
86 "Valve QB has flow rate=0; tunnels lead to valves QX, ES",
87 "Valve NX has flow rate=0; tunnels lead to valves UH, OP",
88 "Valve PJ has flow rate=0; tunnels lead to valves OC, UH",
89 "Valve OR has flow rate=6; tunnels lead to valves QH, BH, HB, JD",
90 "Valve OC has flow rate=7; tunnels lead to valves IZ, JR, TA, ZH, PJ",
91 "Valve UC has flow rate=0; tunnels lead to valves AA, BY",
92 "Valve QX has flow rate=0; tunnels lead to valves AA, QB",
93 "Valve IZ has flow rate=0; tunnels lead to valves OC, SX",
94 "Valve AG has flow rate=13; tunnels lead to valves NW, GL, SM",
95 "Valve ON has flow rate=0; tunnels lead to valves MO, ZI",
96 "Valve XT has flow rate=18; tunnels lead to valves QZ, PG",
97 "Valve AX has flow rate=0; tunnels lead to valves UH, MO",
98 "Valve JD has flow rate=0; tunnels lead to valves OR, SM",
99 "Valve HM has flow rate=0; tunnels lead to valves TX, QH",
100 "Valve LF has flow rate=0; tunnels lead to valves ZI, UH",
101 "Valve QH has flow rate=0; tunnels lead to valves OR, HM",
102 "Valve RT has flow rate=21; tunnel leads to valve PG",
103 "Valve NE has flow rate=0; tunnels lead to valves VZ, TA",
104 "Valve OQ has flow rate=0; tunnels lead to valves TX, GE",
105 "Valve AA has flow rate=0; tunnels lead to valves QZ, UC, OP, QX, EH",
106 "Valve UH has flow rate=17; tunnels lead to valves PJ, NX, AX, LF",
107 "Valve GE has flow rate=0; tunnels lead to valves YB, OQ",
108 "Valve EH has flow rate=0; tunnels lead to valves AA, MO",
109 "Valve MG has flow rate=0; tunnels lead to valves TX, NW",
110 "Valve YB has flow rate=20; tunnels lead to valves IH, GE, XG",
111 "Valve MO has flow rate=15; tunnels lead to valves EH, ON, AX, ZH, CB",
112 "Valve JR has flow rate=0; tunnels lead to valves ZI, OC",
113 "Valve GL has flow rate=0; tunnels lead to valves AG, QJ",
114 "Valve SM has flow rate=0; tunnels lead to valves JD, AG",
115 "Valve HB has flow rate=0; tunnels lead to valves OR, QJ",
116 "Valve TA has flow rate=0; tunnels lead to valves OC, NE",
117 "Valve PG has flow rate=0; tunnels lead to valves RT, XT",
118 "Valve XG has flow rate=0; tunnels lead to valves CB, YB",
119 "Valve ES has flow rate=9; tunnels lead to valves QB, FL",
120 "Valve BH has flow rate=0; tunnels lead to valves RU, OR",
121 "Valve FL has flow rate=0; tunnels lead to valves SX, ES",
122 "Valve CB has flow rate=0; tunnels lead to valves MO, XG",
123 "Valve QZ has flow rate=0; tunnels lead to valves AA, XT",
124 "Valve BY has flow rate=0; tunnels lead to valves UC, ZI",
125 "Valve ZH has flow rate=0; tunnels lead to valves MO, OC",
126 "Valve OP has flow rate=0; tunnels lead to valves NX, AA",
127 "Valve NW has flow rate=0; tunnels lead to valves MG, AG",
128 "Valve RU has flow rate=0; tunnels lead to valves ZI, BH",
129 "Valve SX has flow rate=16; tunnels lead to valves IZ, FL"]
130```
131
132<!-- livebook:{"output":true} -->
133
134```
135{{"QJ", %{rate: 11, routes: ["HB", "GL"]}},
136 %{
137 "CB" => %{rate: 0, routes: ["MO", "XG"]},
138 "EH" => %{rate: 0, routes: ["AA", "MO"]},
139 "YB" => %{rate: 20, routes: ["IH", "GE", "XG"]},
140 "ON" => %{rate: 0, routes: ["MO", "ZI"]},
141 "ES" => %{rate: 9, routes: ["QB", "FL"]},
142 "XG" => %{rate: 0, routes: ["CB", "YB"]},
143 "TX" => %{rate: 19, routes: ["MG", "OQ", "HM"]},
144 "RT" => %{rate: 21, routes: ["PG"]},
145 "GL" => %{rate: 0, routes: ["AG", "QJ"]},
146 "XT" => %{rate: 18, routes: ["QZ", "PG"]},
147 "BY" => %{rate: 0, routes: ["UC", "ZI"]},
148 "QJ" => %{rate: 11, routes: ["HB", "GL"]},
149 "QB" => %{rate: 0, routes: ["QX", "ES"]},
150 "QH" => %{rate: 0, routes: ["OR", "HM"]},
151 "SX" => %{rate: 16, routes: ["IZ", "FL"]},
152 "ZI" => %{rate: 5, routes: ["BY", "ON", "RU", "LF", "JR"]},
153 "OC" => %{rate: 7, routes: ["IZ", "JR", "TA", "ZH", "PJ"]},
154 "NW" => %{rate: 0, routes: ["MG", "AG"]},
155 "UH" => %{rate: 17, routes: ["PJ", "NX", "AX", "LF"]},
156 "VZ" => %{rate: 10, routes: ["NE"]},
157 "MO" => %{rate: 15, routes: ["EH", "ON", "AX", "ZH", "CB"]},
158 "ZH" => %{rate: 0, routes: ["MO", "OC"]},
159 "RU" => %{rate: 0, routes: ["ZI", "BH"]},
160 "FL" => %{rate: 0, routes: ["SX", "ES"]},
161 "SM" => %{rate: 0, routes: ["JD", "AG"]},
162 "AA" => %{rate: 0, routes: ["QZ", "UC", "OP", "QX", "EH"]},
163 "JR" => %{rate: 0, routes: ["ZI", "OC"]},
164 "QS" => %{rate: 22, routes: ["IH"]},
165 "AG" => %{rate: 13, routes: ["NW", "GL", "SM"]},
166 "JD" => %{rate: 0, routes: ["OR", "SM"]},
167 "QZ" => %{rate: 0, routes: ["AA", "XT"]},
168 "MG" => %{rate: 0, routes: ["TX", "NW"]},
169 "UC" => %{rate: 0, routes: ["AA", "BY"]},
170 "AX" => %{rate: 0, routes: ["UH", "MO"]},
171 "HM" => %{rate: 0, routes: ["TX", "QH"]},
172 "LF" => %{rate: 0, routes: ["ZI", "UH"]},
173 "BH" => %{rate: 0, routes: ["RU", "OR"]},
174 "OR" => %{rate: 6, routes: ["QH", "BH", "HB", "JD"]},
175 "GE" => %{rate: 0, routes: ["YB", "OQ"]},
176 "QX" => %{rate: 0, routes: ["AA", "QB"]},
177 "IZ" => %{rate: 0, routes: ["OC", "SX"]},
178 "PG" => %{rate: 0, routes: ["RT", "XT"]},
179 "NX" => %{rate: 0, routes: ["UH", "OP"]},
180 "OP" => %{rate: 0, routes: ["NX", "AA"]},
181 "TA" => %{rate: 0, routes: ["OC", ...]},
182 "IH" => %{rate: 0, routes: [...]},
183 "HB" => %{rate: 0, ...},
184 "PJ" => %{...},
185 ...
186 }}
187```
188
189```elixir
190graph = Graph.new(type: :directed)
191
192edges =
193 Enum.flat_map(valves, fn {a, %{routes: routes}} ->
194 for b <- routes, p <- [{a, b, weight: 1}, {b, a, weight: 1}], do: p
195 end)
196
197graph =
198 Graph.add_edges(graph, edges)
199 |> Kino.render()
200
201paths =
202 for v <- Graph.vertices(graph), into: %{} do
203 routes =
204 graph
205 |> Graph.bellman_ford(v)
206 |> Enum.filter(fn {k, _} -> valves[k].rate > 0 and k != v end)
207 |> Map.new()
208
209 {v, routes}
210 end
211```
212
213<!-- livebook:{"output":true} -->
214
215```
216#Graph<type: directed, vertices: ["LF", "CB", "AX", "ZI", "ZH", "VZ", "AA", "UH", "OC", "IH", "FL",
217 "JR", "QB", "EH", "QH", "ON", "TA", "PJ", "SX", "YB", "UC", "BH", "MO", "OQ", "HM", "JD", "OR",
218 "NE", "QS", "XT", "IZ", "QZ", "BY", "PG", "NW", "HB", "AG", "QJ", "RT", "TX", "GE", "QX", "XG",
219 "NX", "GL", "RU", "SM", "ES", "MG",
220 "OP"], edges: ["LF" -> "UH", "LF" -> "ZI", "CB" -> "MO", "CB" -> "XG", "AX" -> "UH", "AX" -> "MO", "ZI" -> "BY", "ZI" -> "RU", "ZI" -> "ON", "ZI" -> "LF", "ZI" -> "JR", "ZH" -> "OC", "ZH" -> "MO", "VZ" -> "NE", "AA" -> "UC", "AA" -> "EH", "AA" -> "QX", "AA" -> "OP", "AA" -> "QZ", "UH" -> "LF", "UH" -> "PJ", "UH" -> "AX", "UH" -> "NX", "OC" -> "ZH", "OC" -> "IZ", "OC" -> "TA", "OC" -> "PJ", "OC" -> "JR", "IH" -> "YB", "IH" -> "QS", "FL" -> "SX", "FL" -> "ES", "JR" -> "OC", "JR" -> "ZI", "QB" -> "QX", "QB" -> "ES", "EH" -> "MO", "EH" -> "AA", "QH" -> "OR", "QH" -> "HM", "ON" -> "MO", "ON" -> "ZI", "TA" -> "OC", "TA" -> "NE", "PJ" -> "OC", "PJ" -> "UH", "SX" -> "IZ", "SX" -> "FL", "YB" -> "GE", "YB" -> "IH", "YB" -> "XG", "UC" -> "BY", "UC" -> "AA", "BH" -> "OR", "BH" -> "RU", "MO" -> "ZH", "MO" -> "EH", "MO" -> "ON", "MO" -> "CB", "MO" -> "AX", "OQ" -> "GE", "OQ" -> "TX", "HM" -> "TX", "HM" -> "QH", "JD" -> "OR", "JD" -> "SM", "OR" -> "BH", "OR" -> "HB", "OR" -> "JD", "OR" -> "QH", "NE" -> "TA", "NE" -> "VZ", "QS" -> "IH", "XT" -> "QZ", "XT" -> "PG", "IZ" -> "OC", "IZ" -> "SX", "QZ" -> "AA", "QZ" -> "XT", "BY" -> "UC", "BY" -> "ZI", "PG" -> "RT", "PG" -> "XT", "NW" -> "MG", "NW" -> "AG", "HB" -> "OR", "HB" -> "QJ", "AG" -> "SM", "AG" -> "GL", "AG" -> "NW", "QJ" -> "GL", "QJ" -> "HB", "RT" -> "PG", "TX" -> "OQ", "TX" -> "MG", "TX" -> "HM", "GE" -> "OQ", "GE" -> "YB", "QX" -> "QB", "QX" -> "AA", "XG" -> "YB", "XG" -> "CB", "NX" -> "UH", "NX" -> "OP", "GL" -> "QJ", "GL" -> "AG", "RU" -> "BH", "RU" -> "ZI", "SM" -> "AG", "SM" -> "JD", "ES" -> "QB", "ES" -> "FL", "MG" -> "NW", "MG" -> "TX", "OP" -> "AA", "OP" -> "NX"]>
221```
222
223<!-- livebook:{"output":true} -->
224
225```
226%{
227 "CB" => %{
228 "AG" => 8,
229 "ES" => 6,
230 "MO" => 1,
231 "OC" => 3,
232 "OR" => 6,
233 "QJ" => 8,
234 "QS" => 4,
235 "RT" => 7,
236 "SX" => 5,
237 "TX" => 5,
238 "UH" => 3,
239 "VZ" => 6,
240 "XT" => 5,
241 "YB" => 2,
242 "ZI" => 3
243 },
244 "EH" => %{
245 "AG" => 9,
246 "ES" => 4,
247 "MO" => 1,
248 "OC" => 3,
249 "OR" => 6,
250 "QJ" => 8,
251 "QS" => 6,
252 "RT" => 5,
253 "SX" => 5,
254 "TX" => 7,
255 "UH" => 3,
256 "VZ" => 6,
257 "XT" => 3,
258 "YB" => 4,
259 "ZI" => 3
260 },
261 "YB" => %{
262 "AG" => 6,
263 "ES" => 8,
264 "MO" => 3,
265 "OC" => 5,
266 "OR" => 6,
267 "QJ" => 8,
268 "QS" => 2,
269 "RT" => 9,
270 "SX" => 7,
271 "TX" => 3,
272 "UH" => 5,
273 "VZ" => 8,
274 "XT" => 7,
275 "ZI" => 5
276 },
277 "ON" => %{
278 "AG" => 7,
279 "ES" => 6,
280 "MO" => 1,
281 "OC" => 3,
282 "OR" => 4,
283 "QJ" => 6,
284 "QS" => 6,
285 "RT" => 7,
286 "SX" => 5,
287 "TX" => 7,
288 "UH" => 3,
289 "VZ" => 6,
290 "XT" => 5,
291 "YB" => 4,
292 "ZI" => 1
293 },
294 "ES" => %{
295 "AG" => 12,
296 "MO" => 5,
297 "OC" => 4,
298 "OR" => 9,
299 "QJ" => 11,
300 "QS" => 10,
301 "RT" => 7,
302 "SX" => 2,
303 "TX" => 11,
304 "UH" => 6,
305 "VZ" => 7,
306 "XT" => 5,
307 "YB" => 8,
308 "ZI" => 6
309 },
310 "XG" => %{
311 "AG" => 7,
312 "ES" => 7,
313 "MO" => 2,
314 "OC" => 4,
315 "OR" => 7,
316 "QJ" => 9,
317 "QS" => 3,
318 "RT" => 8,
319 "SX" => 6,
320 "TX" => 4,
321 "UH" => 4,
322 "VZ" => 7,
323 "XT" => 6,
324 "YB" => 1,
325 "ZI" => 4
326 },
327 "TX" => %{
328 "AG" => 3,
329 "ES" => 11,
330 "MO" => 6,
331 "OC" => 8,
332 "OR" => 3,
333 "QJ" => 5,
334 "QS" => 5,
335 "RT" => 12,
336 "SX" => 10,
337 "UH" => 8,
338 "VZ" => 11,
339 "XT" => 10,
340 "YB" => 3,
341 "ZI" => 6
342 },
343 "RT" => %{
344 "AG" => 13,
345 "ES" => 7,
346 "MO" => 6,
347 "OC" => 8,
348 "OR" => 10,
349 "QJ" => 12,
350 "QS" => 11,
351 "SX" => 9,
352 "TX" => 12,
353 "UH" => 7,
354 "VZ" => 11,
355 "XT" => 2,
356 "YB" => 9,
357 "ZI" => 7
358 },
359 "GL" => %{
360 "AG" => 1,
361 "ES" => 12,
362 "MO" => 8,
363 "OC" => 8,
364 "OR" => 3,
365 "QJ" => 1,
366 "QS" => 9,
367 "RT" => 13,
368 "SX" => 10,
369 "TX" => 4,
370 "UH" => 8,
371 "VZ" => 11,
372 "XT" => 11,
373 "YB" => 7,
374 "ZI" => 6
375 },
376 "XT" => %{
377 "AG" => 11,
378 "ES" => 5,
379 "MO" => 4,
380 "OC" => 6,
381 "OR" => 8,
382 "QJ" => 10,
383 "QS" => 9,
384 "RT" => 2,
385 "SX" => 7,
386 "TX" => 10,
387 "UH" => 5,
388 "VZ" => 9,
389 "YB" => 7,
390 "ZI" => 5
391 },
392 "BY" => %{
393 "AG" => 7,
394 "ES" => 5,
395 "MO" => 3,
396 "OC" => 3,
397 "OR" => 4,
398 "QJ" => 6,
399 "QS" => 8,
400 "RT" => 6,
401 "SX" => 5,
402 "TX" => 7,
403 "UH" => 3,
404 "VZ" => 6,
405 "XT" => 4,
406 "YB" => 6,
407 "ZI" => 1
408 },
409 "QJ" => %{
410 "AG" => 2,
411 "ES" => 11,
412 "MO" => 7,
413 "OC" => 7,
414 "OR" => 2,
415 "QS" => 10,
416 "RT" => 12,
417 "SX" => 9,
418 "TX" => 5,
419 "UH" => 7,
420 "VZ" => 10,
421 "XT" => 10,
422 "YB" => 8,
423 "ZI" => 5
424 },
425 "QB" => %{
426 "AG" => 11,
427 "ES" => 1,
428 "MO" => 4,
429 "OC" => 5,
430 "OR" => 8,
431 "QJ" => 10,
432 "QS" => 9,
433 "RT" => 6,
434 "SX" => 3,
435 "TX" => 10,
436 "UH" => 5,
437 "VZ" => 8,
438 "XT" => 4,
439 "YB" => 7,
440 "ZI" => 5
441 },
442 "QH" => %{
443 "AG" => 4,
444 "ES" => 10,
445 "MO" => 6,
446 "OC" => 6,
447 "OR" => 1,
448 "QJ" => 3,
449 "QS" => 7,
450 "RT" => 11,
451 "SX" => 8,
452 "TX" => 2,
453 "UH" => 6,
454 "VZ" => 9,
455 "XT" => 9,
456 "YB" => 5,
457 "ZI" => 4
458 },
459 "SX" => %{
460 "AG" => 10,
461 "ES" => 2,
462 "MO" => 4,
463 "OC" => 2,
464 "OR" => 7,
465 "QJ" => 9,
466 "QS" => 9,
467 "RT" => 9,
468 "TX" => 10,
469 "UH" => 4,
470 "VZ" => 5,
471 "XT" => 7,
472 "YB" => 7,
473 "ZI" => 4
474 },
475 "ZI" => %{
476 "AG" => 6,
477 "ES" => 6,
478 "MO" => 2,
479 "OC" => 2,
480 "OR" => 3,
481 "QJ" => 5,
482 "QS" => 7,
483 "RT" => 7,
484 "SX" => 4,
485 "TX" => 6,
486 "UH" => 2,
487 "VZ" => 5,
488 "XT" => 5,
489 "YB" => 5
490 },
491 "OC" => %{
492 "AG" => 8,
493 "ES" => 4,
494 "MO" => 2,
495 "OR" => 5,
496 "QJ" => 7,
497 "QS" => 7,
498 "RT" => 8,
499 "SX" => 2,
500 "TX" => 8,
501 "UH" => 2,
502 "VZ" => 3,
503 "XT" => 6,
504 "YB" => 5,
505 "ZI" => 2
506 },
507 "NW" => %{
508 "AG" => 1,
509 "ES" => 13,
510 "MO" => 8,
511 "OC" => 9,
512 "OR" => 4,
513 "QJ" => 3,
514 "QS" => 7,
515 "RT" => 14,
516 "SX" => 11,
517 "TX" => 2,
518 "UH" => 9,
519 "VZ" => 12,
520 "XT" => 12,
521 "YB" => 5,
522 "ZI" => 7
523 },
524 "UH" => %{
525 "AG" => 8,
526 "ES" => 6,
527 "MO" => 2,
528 "OC" => 2,
529 "OR" => 5,
530 "QJ" => 7,
531 "QS" => 7,
532 "RT" => 7,
533 "SX" => 4,
534 "TX" => 8,
535 "VZ" => 5,
536 "XT" => 5,
537 "YB" => 5,
538 "ZI" => 2
539 },
540 "VZ" => %{
541 "AG" => 11,
542 "ES" => 7,
543 "MO" => 5,
544 "OC" => 3,
545 "OR" => 8,
546 "QJ" => 10,
547 "QS" => 10,
548 "RT" => 11,
549 "SX" => 5,
550 "TX" => 11,
551 "UH" => 5,
552 "XT" => 9,
553 "YB" => 8,
554 "ZI" => 5
555 },
556 "MO" => %{
557 "AG" => 8,
558 "ES" => 5,
559 "OC" => 2,
560 "OR" => 5,
561 "QJ" => 7,
562 "QS" => 5,
563 "RT" => 6,
564 "SX" => 4,
565 "TX" => 6,
566 "UH" => 2,
567 "VZ" => 5,
568 "XT" => 4,
569 "YB" => 3,
570 "ZI" => 2
571 },
572 "ZH" => %{
573 "AG" => 9,
574 "ES" => 5,
575 "MO" => 1,
576 "OC" => 1,
577 "OR" => 6,
578 "QJ" => 8,
579 "QS" => 6,
580 "RT" => 7,
581 "SX" => 3,
582 "TX" => 7,
583 "UH" => 3,
584 "VZ" => 4,
585 "XT" => 5,
586 "YB" => 4,
587 "ZI" => 3
588 },
589 "RU" => %{
590 "AG" => 5,
591 "ES" => 7,
592 "MO" => 3,
593 "OC" => 3,
594 "OR" => 2,
595 "QJ" => 4,
596 "QS" => 8,
597 "RT" => 8,
598 "SX" => 5,
599 "TX" => 5,
600 "UH" => 3,
601 "VZ" => 6,
602 "XT" => 6,
603 "YB" => 6,
604 "ZI" => 1
605 },
606 "FL" => %{
607 "AG" => 11,
608 "ES" => 1,
609 "MO" => 5,
610 "OC" => 3,
611 "OR" => 8,
612 "QJ" => 10,
613 "QS" => 10,
614 "RT" => 8,
615 "SX" => 1,
616 "TX" => 11,
617 "UH" => 5,
618 "VZ" => 6,
619 "XT" => 6,
620 "YB" => 8,
621 "ZI" => 5
622 },
623 "SM" => %{
624 "AG" => 1,
625 "ES" => 11,
626 "MO" => 7,
627 "OC" => 7,
628 "OR" => 2,
629 "QJ" => 3,
630 "QS" => 9,
631 "RT" => 12,
632 "SX" => 9,
633 "TX" => 4,
634 "UH" => 7,
635 "VZ" => 10,
636 "XT" => 10,
637 "YB" => 7,
638 "ZI" => 5
639 },
640 "AA" => %{
641 "AG" => 9,
642 "ES" => 3,
643 "MO" => 2,
644 "OC" => 4,
645 "OR" => 6,
646 "QJ" => 8,
647 "QS" => 7,
648 "RT" => 4,
649 "SX" => 5,
650 "TX" => 8,
651 "UH" => 3,
652 "VZ" => 7,
653 "XT" => 2,
654 "YB" => 5,
655 "ZI" => 3
656 },
657 "JR" => %{
658 "AG" => 7,
659 "ES" => 5,
660 "MO" => 3,
661 "OC" => 1,
662 "OR" => 4,
663 "QJ" => 6,
664 "QS" => 8,
665 "RT" => 8,
666 "SX" => 3,
667 "TX" => 7,
668 "UH" => 3,
669 "VZ" => 4,
670 "XT" => 6,
671 "YB" => 6,
672 "ZI" => 1
673 },
674 "QS" => %{
675 "AG" => 8,
676 "ES" => 10,
677 "MO" => 5,
678 "OC" => 7,
679 "OR" => 8,
680 "QJ" => 10,
681 "RT" => 11,
682 "SX" => 9,
683 "TX" => 5,
684 "UH" => 7,
685 "VZ" => 10,
686 "XT" => 9,
687 "YB" => 2,
688 "ZI" => 7
689 },
690 "AG" => %{
691 "ES" => 12,
692 "MO" => 8,
693 "OC" => 8,
694 "OR" => 3,
695 "QJ" => 2,
696 "QS" => 8,
697 "RT" => 13,
698 "SX" => 10,
699 "TX" => 3,
700 "UH" => 8,
701 "VZ" => 11,
702 "XT" => 11,
703 "YB" => 6,
704 "ZI" => 6
705 },
706 "JD" => %{
707 "AG" => 2,
708 "ES" => 10,
709 "MO" => 6,
710 "OC" => 6,
711 "OR" => 1,
712 "QJ" => 3,
713 "QS" => 9,
714 "RT" => 11,
715 "SX" => 8,
716 "TX" => 4,
717 "UH" => 6,
718 "VZ" => 9,
719 "XT" => 9,
720 "YB" => 7,
721 "ZI" => 4
722 },
723 "QZ" => %{
724 "AG" => 10,
725 "ES" => 4,
726 "MO" => 3,
727 "OC" => 5,
728 "OR" => 7,
729 "QJ" => 9,
730 "QS" => 8,
731 "RT" => 3,
732 "SX" => 6,
733 "TX" => 9,
734 "UH" => 4,
735 "VZ" => 8,
736 "XT" => 1,
737 "YB" => 6,
738 "ZI" => 4
739 },
740 "MG" => %{
741 "AG" => 2,
742 "ES" => 12,
743 "MO" => 7,
744 "OC" => 9,
745 "OR" => 4,
746 "QJ" => 4,
747 "QS" => 6,
748 "RT" => 13,
749 "SX" => 11,
750 "TX" => 1,
751 "UH" => 9,
752 "VZ" => 12,
753 "XT" => 11,
754 "YB" => 4,
755 "ZI" => 7
756 },
757 "UC" => %{
758 "AG" => 8,
759 "ES" => 4,
760 "MO" => 3,
761 "OC" => 4,
762 "OR" => 5,
763 "QJ" => 7,
764 "QS" => 8,
765 "RT" => 5,
766 "SX" => 6,
767 "TX" => 8,
768 "UH" => 4,
769 "VZ" => 7,
770 "XT" => 3,
771 "YB" => 6,
772 "ZI" => 2
773 },
774 "AX" => %{
775 "AG" => 9,
776 "ES" => 6,
777 "MO" => 1,
778 "OC" => 3,
779 "OR" => 6,
780 "QJ" => 8,
781 "QS" => 6,
782 "RT" => 7,
783 "SX" => 5,
784 "TX" => 7,
785 "UH" => 1,
786 "VZ" => 6,
787 "XT" => 5,
788 "YB" => 4,
789 "ZI" => 3
790 },
791 "HM" => %{
792 "AG" => 4,
793 "ES" => 11,
794 "MO" => 7,
795 "OC" => 7,
796 "OR" => 2,
797 "QJ" => 4,
798 "QS" => 6,
799 "RT" => 12,
800 "SX" => 9,
801 "TX" => 1,
802 "UH" => 7,
803 "VZ" => 10,
804 "XT" => 10,
805 "YB" => 4,
806 "ZI" => 5
807 },
808 "LF" => %{
809 "AG" => 7,
810 "ES" => 7,
811 "MO" => 3,
812 "OC" => 3,
813 "OR" => 4,
814 "QJ" => 6,
815 "QS" => 8,
816 "RT" => 8,
817 "SX" => 5,
818 "TX" => 7,
819 "UH" => 1,
820 "VZ" => 6,
821 "XT" => 6,
822 "YB" => 6,
823 ...
824 },
825 "BH" => %{
826 "AG" => 4,
827 "ES" => 8,
828 "MO" => 4,
829 "OC" => 4,
830 "OR" => 1,
831 "QJ" => 3,
832 "QS" => 9,
833 "RT" => 9,
834 "SX" => 6,
835 "TX" => 4,
836 "UH" => 4,
837 "VZ" => 7,
838 "XT" => 7,
839 ...
840 },
841 "OR" => %{
842 "AG" => 3,
843 "ES" => 9,
844 "MO" => 5,
845 "OC" => 5,
846 "QJ" => 2,
847 "QS" => 8,
848 "RT" => 10,
849 "SX" => 7,
850 "TX" => 3,
851 "UH" => 5,
852 "VZ" => 8,
853 "XT" => 8,
854 ...
855 },
856 "GE" => %{
857 "AG" => 5,
858 "ES" => 9,
859 "MO" => 4,
860 "OC" => 6,
861 "OR" => 5,
862 "QJ" => 7,
863 "QS" => 3,
864 "RT" => 10,
865 "SX" => 8,
866 "TX" => 2,
867 "UH" => 6,
868 ...
869 },
870 "QX" => %{
871 "AG" => 10,
872 "ES" => 2,
873 "MO" => 3,
874 "OC" => 5,
875 "OR" => 7,
876 "QJ" => 9,
877 "QS" => 8,
878 "RT" => 5,
879 "SX" => 4,
880 "TX" => 9,
881 ...
882 },
883 "IZ" => %{
884 "AG" => 9,
885 "ES" => 3,
886 "MO" => 3,
887 "OC" => 1,
888 "OR" => 6,
889 "QJ" => 8,
890 "QS" => 8,
891 "RT" => 9,
892 "SX" => 1,
893 ...
894 },
895 "PG" => %{
896 "AG" => 12,
897 "ES" => 6,
898 "MO" => 5,
899 "OC" => 7,
900 "OR" => 9,
901 "QJ" => 11,
902 "QS" => 10,
903 "RT" => 1,
904 ...
905 },
906 "NX" => %{"AG" => 9, "ES" => 5, "MO" => 3, "OC" => 3, "OR" => 6, "QJ" => 8, "QS" => 8, ...},
907 "OP" => %{"AG" => 10, "ES" => 4, "MO" => 3, "OC" => 4, "OR" => 7, "QJ" => 9, ...},
908 "TA" => %{"AG" => 9, "ES" => 5, "MO" => 3, "OC" => 1, "OR" => 6, ...},
909 "IH" => %{"AG" => 7, "ES" => 9, "MO" => 4, "OC" => 6, ...},
910 "HB" => %{"AG" => 3, "ES" => 10, "MO" => 6, ...},
911 "PJ" => %{"AG" => 9, "ES" => 5, ...},
912 "OQ" => %{"AG" => 4, ...},
913 "NE" => %{...}
914}
915```
916
917## Task 1
918
919```elixir
920defmodule Alone do
921 def visit(current, valves, paths, left, opened) when left >= 0 do
922 {left, rate, opened} =
923 case valves[current].rate do
924 0 -> {left, 0, opened}
925 other -> {left - 1, other, Map.put(opened, current, left - 1)}
926 end
927
928 rate = rate * left
929
930 paths[current]
931 |> Enum.map(fn
932 {next, weight} when weight + 1 < left and not is_map_key(opened, next) ->
933 {val, opened} = visit(next, valves, paths, left - weight, opened)
934 {val + rate, opened}
935
936 _ ->
937 {rate, opened}
938 end)
939 |> Enum.max_by(&elem(&1, 0))
940 end
941end
942```
943
944<!-- livebook:{"output":true} -->
945
946```
947{:module, Valves, <<70, 79, 82, 49, 0, 0, 11, ...>>, {:visit, 5}}
948```
949
950```elixir
951{t, v} = Alone.visit("AA", valves, paths, 30, %{})
952```
953
954<!-- livebook:{"output":true} -->
955
956```
957{1820, %{"AG" => 6, "MO" => 23, "QJ" => 3, "QS" => 16, "TX" => 10, "UH" => 26, "YB" => 19}}
958```
959
960## Task 2
961
962```elixir
963defmodule Alone do
964 def visit(current, valves, paths, left, opened) when left >= 0 do
965 {left, rate, opened} =
966 case valves[current].rate do
967 0 -> {left, 0, opened}
968 other -> {left - 1, other, Map.put(opened, current, left - 1)}
969 end
970
971 rate = rate * left
972
973 paths[current]
974 |> Enum.map(fn
975 {next, weight} when weight + 1 < left and not is_map_key(opened, next) ->
976 {val, opened} = visit(next, valves, paths, left - weight, opened)
977 {val + rate, opened}
978
979 _ ->
980 {rate, opened}
981 end)
982 |> Enum.max_by(&elem(&1, 0))
983 end
984end
985```