Day 16
Mix.install([
{:kino_aoc, git: "https://github.com/ljgago/kino_aoc"},
{:libgraph, github: "hauleth/libgraph", ref: "perf/bellman-ford-implementation"}
])
:ok
Setup
{:ok, puzzle_input} =
KinoAOC.download_puzzle("2022", "16", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
{:ok,
"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"}
# puzzle_input = """
# Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
# Valve BB has flow rate=13; tunnels lead to valves CC, AA
# Valve CC has flow rate=2; tunnels lead to valves DD, BB
# Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
# Valve EE has flow rate=3; tunnels lead to valves FF, DD
# Valve FF has flow rate=0; tunnels lead to valves EE, GG
# Valve GG has flow rate=0; tunnels lead to valves FF, HH
# Valve HH has flow rate=22; tunnel leads to valve GG
# Valve II has flow rate=0; tunnels lead to valves AA, JJ
# Valve JJ has flow rate=21; tunnel leads to valve II
# """
nil
{{start, _}, valves} =
valves =
puzzle_input
|> String.split("\n", trim: true)
|> Kino.render()
|> Enum.map(fn line ->
%{
"name" => name,
"rate" => rate,
"routes" => routes
} =
Regex.named_captures(
~r/Valve (?<name>..).*rate=(?<rate>\d+);.*valves? (?<routes>.*)$/,
line
)
{name, %{rate: String.to_integer(rate), routes: String.split(routes, ~r/,\s*/, trim: true)}}
end)
|> then(&{hd(&1), Map.new(&1)})
["Valve QJ has flow rate=11; tunnels lead to valves HB, GL",
"Valve VZ has flow rate=10; tunnel leads to valve NE",
"Valve TX has flow rate=19; tunnels lead to valves MG, OQ, HM",
"Valve ZI has flow rate=5; tunnels lead to valves BY, ON, RU, LF, JR",
"Valve IH has flow rate=0; tunnels lead to valves YB, QS",
"Valve QS has flow rate=22; tunnel leads to valve IH",
"Valve QB has flow rate=0; tunnels lead to valves QX, ES",
"Valve NX has flow rate=0; tunnels lead to valves UH, OP",
"Valve PJ has flow rate=0; tunnels lead to valves OC, UH",
"Valve OR has flow rate=6; tunnels lead to valves QH, BH, HB, JD",
"Valve OC has flow rate=7; tunnels lead to valves IZ, JR, TA, ZH, PJ",
"Valve UC has flow rate=0; tunnels lead to valves AA, BY",
"Valve QX has flow rate=0; tunnels lead to valves AA, QB",
"Valve IZ has flow rate=0; tunnels lead to valves OC, SX",
"Valve AG has flow rate=13; tunnels lead to valves NW, GL, SM",
"Valve ON has flow rate=0; tunnels lead to valves MO, ZI",
"Valve XT has flow rate=18; tunnels lead to valves QZ, PG",
"Valve AX has flow rate=0; tunnels lead to valves UH, MO",
"Valve JD has flow rate=0; tunnels lead to valves OR, SM",
"Valve HM has flow rate=0; tunnels lead to valves TX, QH",
"Valve LF has flow rate=0; tunnels lead to valves ZI, UH",
"Valve QH has flow rate=0; tunnels lead to valves OR, HM",
"Valve RT has flow rate=21; tunnel leads to valve PG",
"Valve NE has flow rate=0; tunnels lead to valves VZ, TA",
"Valve OQ has flow rate=0; tunnels lead to valves TX, GE",
"Valve AA has flow rate=0; tunnels lead to valves QZ, UC, OP, QX, EH",
"Valve UH has flow rate=17; tunnels lead to valves PJ, NX, AX, LF",
"Valve GE has flow rate=0; tunnels lead to valves YB, OQ",
"Valve EH has flow rate=0; tunnels lead to valves AA, MO",
"Valve MG has flow rate=0; tunnels lead to valves TX, NW",
"Valve YB has flow rate=20; tunnels lead to valves IH, GE, XG",
"Valve MO has flow rate=15; tunnels lead to valves EH, ON, AX, ZH, CB",
"Valve JR has flow rate=0; tunnels lead to valves ZI, OC",
"Valve GL has flow rate=0; tunnels lead to valves AG, QJ",
"Valve SM has flow rate=0; tunnels lead to valves JD, AG",
"Valve HB has flow rate=0; tunnels lead to valves OR, QJ",
"Valve TA has flow rate=0; tunnels lead to valves OC, NE",
"Valve PG has flow rate=0; tunnels lead to valves RT, XT",
"Valve XG has flow rate=0; tunnels lead to valves CB, YB",
"Valve ES has flow rate=9; tunnels lead to valves QB, FL",
"Valve BH has flow rate=0; tunnels lead to valves RU, OR",
"Valve FL has flow rate=0; tunnels lead to valves SX, ES",
"Valve CB has flow rate=0; tunnels lead to valves MO, XG",
"Valve QZ has flow rate=0; tunnels lead to valves AA, XT",
"Valve BY has flow rate=0; tunnels lead to valves UC, ZI",
"Valve ZH has flow rate=0; tunnels lead to valves MO, OC",
"Valve OP has flow rate=0; tunnels lead to valves NX, AA",
"Valve NW has flow rate=0; tunnels lead to valves MG, AG",
"Valve RU has flow rate=0; tunnels lead to valves ZI, BH",
"Valve SX has flow rate=16; tunnels lead to valves IZ, FL"]
{{"QJ", %{rate: 11, routes: ["HB", "GL"]}},
%{
"CB" => %{rate: 0, routes: ["MO", "XG"]},
"EH" => %{rate: 0, routes: ["AA", "MO"]},
"YB" => %{rate: 20, routes: ["IH", "GE", "XG"]},
"ON" => %{rate: 0, routes: ["MO", "ZI"]},
"ES" => %{rate: 9, routes: ["QB", "FL"]},
"XG" => %{rate: 0, routes: ["CB", "YB"]},
"TX" => %{rate: 19, routes: ["MG", "OQ", "HM"]},
"RT" => %{rate: 21, routes: ["PG"]},
"GL" => %{rate: 0, routes: ["AG", "QJ"]},
"XT" => %{rate: 18, routes: ["QZ", "PG"]},
"BY" => %{rate: 0, routes: ["UC", "ZI"]},
"QJ" => %{rate: 11, routes: ["HB", "GL"]},
"QB" => %{rate: 0, routes: ["QX", "ES"]},
"QH" => %{rate: 0, routes: ["OR", "HM"]},
"SX" => %{rate: 16, routes: ["IZ", "FL"]},
"ZI" => %{rate: 5, routes: ["BY", "ON", "RU", "LF", "JR"]},
"OC" => %{rate: 7, routes: ["IZ", "JR", "TA", "ZH", "PJ"]},
"NW" => %{rate: 0, routes: ["MG", "AG"]},
"UH" => %{rate: 17, routes: ["PJ", "NX", "AX", "LF"]},
"VZ" => %{rate: 10, routes: ["NE"]},
"MO" => %{rate: 15, routes: ["EH", "ON", "AX", "ZH", "CB"]},
"ZH" => %{rate: 0, routes: ["MO", "OC"]},
"RU" => %{rate: 0, routes: ["ZI", "BH"]},
"FL" => %{rate: 0, routes: ["SX", "ES"]},
"SM" => %{rate: 0, routes: ["JD", "AG"]},
"AA" => %{rate: 0, routes: ["QZ", "UC", "OP", "QX", "EH"]},
"JR" => %{rate: 0, routes: ["ZI", "OC"]},
"QS" => %{rate: 22, routes: ["IH"]},
"AG" => %{rate: 13, routes: ["NW", "GL", "SM"]},
"JD" => %{rate: 0, routes: ["OR", "SM"]},
"QZ" => %{rate: 0, routes: ["AA", "XT"]},
"MG" => %{rate: 0, routes: ["TX", "NW"]},
"UC" => %{rate: 0, routes: ["AA", "BY"]},
"AX" => %{rate: 0, routes: ["UH", "MO"]},
"HM" => %{rate: 0, routes: ["TX", "QH"]},
"LF" => %{rate: 0, routes: ["ZI", "UH"]},
"BH" => %{rate: 0, routes: ["RU", "OR"]},
"OR" => %{rate: 6, routes: ["QH", "BH", "HB", "JD"]},
"GE" => %{rate: 0, routes: ["YB", "OQ"]},
"QX" => %{rate: 0, routes: ["AA", "QB"]},
"IZ" => %{rate: 0, routes: ["OC", "SX"]},
"PG" => %{rate: 0, routes: ["RT", "XT"]},
"NX" => %{rate: 0, routes: ["UH", "OP"]},
"OP" => %{rate: 0, routes: ["NX", "AA"]},
"TA" => %{rate: 0, routes: ["OC", ...]},
"IH" => %{rate: 0, routes: [...]},
"HB" => %{rate: 0, ...},
"PJ" => %{...},
...
}}
graph = Graph.new(type: :directed)
edges =
Enum.flat_map(valves, fn {a, %{routes: routes}} ->
for b <- routes, p <- [{a, b, weight: 1}, {b, a, weight: 1}], do: p
end)
graph =
Graph.add_edges(graph, edges)
|> Kino.render()
paths =
for v <- Graph.vertices(graph), into: %{} do
routes =
graph
|> Graph.bellman_ford(v)
|> Enum.filter(fn {k, _} -> valves[k].rate > 0 and k != v end)
|> Map.new()
{v, routes}
end
#Graph<type: directed, vertices: ["LF", "CB", "AX", "ZI", "ZH", "VZ", "AA", "UH", "OC", "IH", "FL",
"JR", "QB", "EH", "QH", "ON", "TA", "PJ", "SX", "YB", "UC", "BH", "MO", "OQ", "HM", "JD", "OR",
"NE", "QS", "XT", "IZ", "QZ", "BY", "PG", "NW", "HB", "AG", "QJ", "RT", "TX", "GE", "QX", "XG",
"NX", "GL", "RU", "SM", "ES", "MG",
"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"]>
%{
"CB" => %{
"AG" => 8,
"ES" => 6,
"MO" => 1,
"OC" => 3,
"OR" => 6,
"QJ" => 8,
"QS" => 4,
"RT" => 7,
"SX" => 5,
"TX" => 5,
"UH" => 3,
"VZ" => 6,
"XT" => 5,
"YB" => 2,
"ZI" => 3
},
"EH" => %{
"AG" => 9,
"ES" => 4,
"MO" => 1,
"OC" => 3,
"OR" => 6,
"QJ" => 8,
"QS" => 6,
"RT" => 5,
"SX" => 5,
"TX" => 7,
"UH" => 3,
"VZ" => 6,
"XT" => 3,
"YB" => 4,
"ZI" => 3
},
"YB" => %{
"AG" => 6,
"ES" => 8,
"MO" => 3,
"OC" => 5,
"OR" => 6,
"QJ" => 8,
"QS" => 2,
"RT" => 9,
"SX" => 7,
"TX" => 3,
"UH" => 5,
"VZ" => 8,
"XT" => 7,
"ZI" => 5
},
"ON" => %{
"AG" => 7,
"ES" => 6,
"MO" => 1,
"OC" => 3,
"OR" => 4,
"QJ" => 6,
"QS" => 6,
"RT" => 7,
"SX" => 5,
"TX" => 7,
"UH" => 3,
"VZ" => 6,
"XT" => 5,
"YB" => 4,
"ZI" => 1
},
"ES" => %{
"AG" => 12,
"MO" => 5,
"OC" => 4,
"OR" => 9,
"QJ" => 11,
"QS" => 10,
"RT" => 7,
"SX" => 2,
"TX" => 11,
"UH" => 6,
"VZ" => 7,
"XT" => 5,
"YB" => 8,
"ZI" => 6
},
"XG" => %{
"AG" => 7,
"ES" => 7,
"MO" => 2,
"OC" => 4,
"OR" => 7,
"QJ" => 9,
"QS" => 3,
"RT" => 8,
"SX" => 6,
"TX" => 4,
"UH" => 4,
"VZ" => 7,
"XT" => 6,
"YB" => 1,
"ZI" => 4
},
"TX" => %{
"AG" => 3,
"ES" => 11,
"MO" => 6,
"OC" => 8,
"OR" => 3,
"QJ" => 5,
"QS" => 5,
"RT" => 12,
"SX" => 10,
"UH" => 8,
"VZ" => 11,
"XT" => 10,
"YB" => 3,
"ZI" => 6
},
"RT" => %{
"AG" => 13,
"ES" => 7,
"MO" => 6,
"OC" => 8,
"OR" => 10,
"QJ" => 12,
"QS" => 11,
"SX" => 9,
"TX" => 12,
"UH" => 7,
"VZ" => 11,
"XT" => 2,
"YB" => 9,
"ZI" => 7
},
"GL" => %{
"AG" => 1,
"ES" => 12,
"MO" => 8,
"OC" => 8,
"OR" => 3,
"QJ" => 1,
"QS" => 9,
"RT" => 13,
"SX" => 10,
"TX" => 4,
"UH" => 8,
"VZ" => 11,
"XT" => 11,
"YB" => 7,
"ZI" => 6
},
"XT" => %{
"AG" => 11,
"ES" => 5,
"MO" => 4,
"OC" => 6,
"OR" => 8,
"QJ" => 10,
"QS" => 9,
"RT" => 2,
"SX" => 7,
"TX" => 10,
"UH" => 5,
"VZ" => 9,
"YB" => 7,
"ZI" => 5
},
"BY" => %{
"AG" => 7,
"ES" => 5,
"MO" => 3,
"OC" => 3,
"OR" => 4,
"QJ" => 6,
"QS" => 8,
"RT" => 6,
"SX" => 5,
"TX" => 7,
"UH" => 3,
"VZ" => 6,
"XT" => 4,
"YB" => 6,
"ZI" => 1
},
"QJ" => %{
"AG" => 2,
"ES" => 11,
"MO" => 7,
"OC" => 7,
"OR" => 2,
"QS" => 10,
"RT" => 12,
"SX" => 9,
"TX" => 5,
"UH" => 7,
"VZ" => 10,
"XT" => 10,
"YB" => 8,
"ZI" => 5
},
"QB" => %{
"AG" => 11,
"ES" => 1,
"MO" => 4,
"OC" => 5,
"OR" => 8,
"QJ" => 10,
"QS" => 9,
"RT" => 6,
"SX" => 3,
"TX" => 10,
"UH" => 5,
"VZ" => 8,
"XT" => 4,
"YB" => 7,
"ZI" => 5
},
"QH" => %{
"AG" => 4,
"ES" => 10,
"MO" => 6,
"OC" => 6,
"OR" => 1,
"QJ" => 3,
"QS" => 7,
"RT" => 11,
"SX" => 8,
"TX" => 2,
"UH" => 6,
"VZ" => 9,
"XT" => 9,
"YB" => 5,
"ZI" => 4
},
"SX" => %{
"AG" => 10,
"ES" => 2,
"MO" => 4,
"OC" => 2,
"OR" => 7,
"QJ" => 9,
"QS" => 9,
"RT" => 9,
"TX" => 10,
"UH" => 4,
"VZ" => 5,
"XT" => 7,
"YB" => 7,
"ZI" => 4
},
"ZI" => %{
"AG" => 6,
"ES" => 6,
"MO" => 2,
"OC" => 2,
"OR" => 3,
"QJ" => 5,
"QS" => 7,
"RT" => 7,
"SX" => 4,
"TX" => 6,
"UH" => 2,
"VZ" => 5,
"XT" => 5,
"YB" => 5
},
"OC" => %{
"AG" => 8,
"ES" => 4,
"MO" => 2,
"OR" => 5,
"QJ" => 7,
"QS" => 7,
"RT" => 8,
"SX" => 2,
"TX" => 8,
"UH" => 2,
"VZ" => 3,
"XT" => 6,
"YB" => 5,
"ZI" => 2
},
"NW" => %{
"AG" => 1,
"ES" => 13,
"MO" => 8,
"OC" => 9,
"OR" => 4,
"QJ" => 3,
"QS" => 7,
"RT" => 14,
"SX" => 11,
"TX" => 2,
"UH" => 9,
"VZ" => 12,
"XT" => 12,
"YB" => 5,
"ZI" => 7
},
"UH" => %{
"AG" => 8,
"ES" => 6,
"MO" => 2,
"OC" => 2,
"OR" => 5,
"QJ" => 7,
"QS" => 7,
"RT" => 7,
"SX" => 4,
"TX" => 8,
"VZ" => 5,
"XT" => 5,
"YB" => 5,
"ZI" => 2
},
"VZ" => %{
"AG" => 11,
"ES" => 7,
"MO" => 5,
"OC" => 3,
"OR" => 8,
"QJ" => 10,
"QS" => 10,
"RT" => 11,
"SX" => 5,
"TX" => 11,
"UH" => 5,
"XT" => 9,
"YB" => 8,
"ZI" => 5
},
"MO" => %{
"AG" => 8,
"ES" => 5,
"OC" => 2,
"OR" => 5,
"QJ" => 7,
"QS" => 5,
"RT" => 6,
"SX" => 4,
"TX" => 6,
"UH" => 2,
"VZ" => 5,
"XT" => 4,
"YB" => 3,
"ZI" => 2
},
"ZH" => %{
"AG" => 9,
"ES" => 5,
"MO" => 1,
"OC" => 1,
"OR" => 6,
"QJ" => 8,
"QS" => 6,
"RT" => 7,
"SX" => 3,
"TX" => 7,
"UH" => 3,
"VZ" => 4,
"XT" => 5,
"YB" => 4,
"ZI" => 3
},
"RU" => %{
"AG" => 5,
"ES" => 7,
"MO" => 3,
"OC" => 3,
"OR" => 2,
"QJ" => 4,
"QS" => 8,
"RT" => 8,
"SX" => 5,
"TX" => 5,
"UH" => 3,
"VZ" => 6,
"XT" => 6,
"YB" => 6,
"ZI" => 1
},
"FL" => %{
"AG" => 11,
"ES" => 1,
"MO" => 5,
"OC" => 3,
"OR" => 8,
"QJ" => 10,
"QS" => 10,
"RT" => 8,
"SX" => 1,
"TX" => 11,
"UH" => 5,
"VZ" => 6,
"XT" => 6,
"YB" => 8,
"ZI" => 5
},
"SM" => %{
"AG" => 1,
"ES" => 11,
"MO" => 7,
"OC" => 7,
"OR" => 2,
"QJ" => 3,
"QS" => 9,
"RT" => 12,
"SX" => 9,
"TX" => 4,
"UH" => 7,
"VZ" => 10,
"XT" => 10,
"YB" => 7,
"ZI" => 5
},
"AA" => %{
"AG" => 9,
"ES" => 3,
"MO" => 2,
"OC" => 4,
"OR" => 6,
"QJ" => 8,
"QS" => 7,
"RT" => 4,
"SX" => 5,
"TX" => 8,
"UH" => 3,
"VZ" => 7,
"XT" => 2,
"YB" => 5,
"ZI" => 3
},
"JR" => %{
"AG" => 7,
"ES" => 5,
"MO" => 3,
"OC" => 1,
"OR" => 4,
"QJ" => 6,
"QS" => 8,
"RT" => 8,
"SX" => 3,
"TX" => 7,
"UH" => 3,
"VZ" => 4,
"XT" => 6,
"YB" => 6,
"ZI" => 1
},
"QS" => %{
"AG" => 8,
"ES" => 10,
"MO" => 5,
"OC" => 7,
"OR" => 8,
"QJ" => 10,
"RT" => 11,
"SX" => 9,
"TX" => 5,
"UH" => 7,
"VZ" => 10,
"XT" => 9,
"YB" => 2,
"ZI" => 7
},
"AG" => %{
"ES" => 12,
"MO" => 8,
"OC" => 8,
"OR" => 3,
"QJ" => 2,
"QS" => 8,
"RT" => 13,
"SX" => 10,
"TX" => 3,
"UH" => 8,
"VZ" => 11,
"XT" => 11,
"YB" => 6,
"ZI" => 6
},
"JD" => %{
"AG" => 2,
"ES" => 10,
"MO" => 6,
"OC" => 6,
"OR" => 1,
"QJ" => 3,
"QS" => 9,
"RT" => 11,
"SX" => 8,
"TX" => 4,
"UH" => 6,
"VZ" => 9,
"XT" => 9,
"YB" => 7,
"ZI" => 4
},
"QZ" => %{
"AG" => 10,
"ES" => 4,
"MO" => 3,
"OC" => 5,
"OR" => 7,
"QJ" => 9,
"QS" => 8,
"RT" => 3,
"SX" => 6,
"TX" => 9,
"UH" => 4,
"VZ" => 8,
"XT" => 1,
"YB" => 6,
"ZI" => 4
},
"MG" => %{
"AG" => 2,
"ES" => 12,
"MO" => 7,
"OC" => 9,
"OR" => 4,
"QJ" => 4,
"QS" => 6,
"RT" => 13,
"SX" => 11,
"TX" => 1,
"UH" => 9,
"VZ" => 12,
"XT" => 11,
"YB" => 4,
"ZI" => 7
},
"UC" => %{
"AG" => 8,
"ES" => 4,
"MO" => 3,
"OC" => 4,
"OR" => 5,
"QJ" => 7,
"QS" => 8,
"RT" => 5,
"SX" => 6,
"TX" => 8,
"UH" => 4,
"VZ" => 7,
"XT" => 3,
"YB" => 6,
"ZI" => 2
},
"AX" => %{
"AG" => 9,
"ES" => 6,
"MO" => 1,
"OC" => 3,
"OR" => 6,
"QJ" => 8,
"QS" => 6,
"RT" => 7,
"SX" => 5,
"TX" => 7,
"UH" => 1,
"VZ" => 6,
"XT" => 5,
"YB" => 4,
"ZI" => 3
},
"HM" => %{
"AG" => 4,
"ES" => 11,
"MO" => 7,
"OC" => 7,
"OR" => 2,
"QJ" => 4,
"QS" => 6,
"RT" => 12,
"SX" => 9,
"TX" => 1,
"UH" => 7,
"VZ" => 10,
"XT" => 10,
"YB" => 4,
"ZI" => 5
},
"LF" => %{
"AG" => 7,
"ES" => 7,
"MO" => 3,
"OC" => 3,
"OR" => 4,
"QJ" => 6,
"QS" => 8,
"RT" => 8,
"SX" => 5,
"TX" => 7,
"UH" => 1,
"VZ" => 6,
"XT" => 6,
"YB" => 6,
...
},
"BH" => %{
"AG" => 4,
"ES" => 8,
"MO" => 4,
"OC" => 4,
"OR" => 1,
"QJ" => 3,
"QS" => 9,
"RT" => 9,
"SX" => 6,
"TX" => 4,
"UH" => 4,
"VZ" => 7,
"XT" => 7,
...
},
"OR" => %{
"AG" => 3,
"ES" => 9,
"MO" => 5,
"OC" => 5,
"QJ" => 2,
"QS" => 8,
"RT" => 10,
"SX" => 7,
"TX" => 3,
"UH" => 5,
"VZ" => 8,
"XT" => 8,
...
},
"GE" => %{
"AG" => 5,
"ES" => 9,
"MO" => 4,
"OC" => 6,
"OR" => 5,
"QJ" => 7,
"QS" => 3,
"RT" => 10,
"SX" => 8,
"TX" => 2,
"UH" => 6,
...
},
"QX" => %{
"AG" => 10,
"ES" => 2,
"MO" => 3,
"OC" => 5,
"OR" => 7,
"QJ" => 9,
"QS" => 8,
"RT" => 5,
"SX" => 4,
"TX" => 9,
...
},
"IZ" => %{
"AG" => 9,
"ES" => 3,
"MO" => 3,
"OC" => 1,
"OR" => 6,
"QJ" => 8,
"QS" => 8,
"RT" => 9,
"SX" => 1,
...
},
"PG" => %{
"AG" => 12,
"ES" => 6,
"MO" => 5,
"OC" => 7,
"OR" => 9,
"QJ" => 11,
"QS" => 10,
"RT" => 1,
...
},
"NX" => %{"AG" => 9, "ES" => 5, "MO" => 3, "OC" => 3, "OR" => 6, "QJ" => 8, "QS" => 8, ...},
"OP" => %{"AG" => 10, "ES" => 4, "MO" => 3, "OC" => 4, "OR" => 7, "QJ" => 9, ...},
"TA" => %{"AG" => 9, "ES" => 5, "MO" => 3, "OC" => 1, "OR" => 6, ...},
"IH" => %{"AG" => 7, "ES" => 9, "MO" => 4, "OC" => 6, ...},
"HB" => %{"AG" => 3, "ES" => 10, "MO" => 6, ...},
"PJ" => %{"AG" => 9, "ES" => 5, ...},
"OQ" => %{"AG" => 4, ...},
"NE" => %{...}
}
Task 1
defmodule Alone do
def visit(current, valves, paths, left, opened) when left >= 0 do
{left, rate, opened} =
case valves[current].rate do
0 -> {left, 0, opened}
other -> {left - 1, other, Map.put(opened, current, left - 1)}
end
rate = rate * left
paths[current]
|> Enum.map(fn
{next, weight} when weight + 1 < left and not is_map_key(opened, next) ->
{val, opened} = visit(next, valves, paths, left - weight, opened)
{val + rate, opened}
_ ->
{rate, opened}
end)
|> Enum.max_by(&elem(&1, 0))
end
end
{:module, Valves, <<70, 79, 82, 49, 0, 0, 11, ...>>, {:visit, 5}}
{t, v} = Alone.visit("AA", valves, paths, 30, %{})
{1820, %{"AG" => 6, "MO" => 23, "QJ" => 3, "QS" => 16, "TX" => 10, "UH" => 26, "YB" => 19}}
Task 2
defmodule Alone do
def visit(current, valves, paths, left, opened) when left >= 0 do
{left, rate, opened} =
case valves[current].rate do
0 -> {left, 0, opened}
other -> {left - 1, other, Map.put(opened, current, left - 1)}
end
rate = rate * left
paths[current]
|> Enum.map(fn
{next, weight} when weight + 1 < left and not is_map_key(opened, next) ->
{val, opened} = visit(next, valves, paths, left - weight, opened)
{val + rate, opened}
_ ->
{rate, opened}
end)
|> Enum.max_by(&elem(&1, 0))
end
end
