Day 16: Proboscidea Volcanium

Mix.install([:nimble_parsec, :heap])
text = File.read!("Code/aoc.ex/input/2022/16.txt")

Proboscidea Volcanium

defmodule Parser do
  import NimbleParsec

  valve = ignore(string(" ")) |> ascii_string([?A..?Z], min: 2)

  line =
    ignore(string("Valve"))
    |> unwrap_and_tag(valve, :source)
    |> ignore(string(" has flow rate="))
    |> unwrap_and_tag(integer(min: 1), :flow)
    |> ignore(choice([string("; tunnels lead to valves"), string("; tunnel leads to valve")]))
    |> tag(valve |> repeat(ignore(string(",")) |> concat(valve)), :destinations)

  defparsec(:line, line)
end

example = """
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
"""

data =
  for line <- String.split(text, "\n", trim: true),
      {:ok, parsed, _, _, _, _} = Parser.line(line),
      do: Map.new(parsed)

nodes = for d <- data, d.flow > 0 or length(d.destinations) != 2, do: d.source

data_by_source = Map.new(data, &amp;{&amp;1.source, &amp;1})

flows = for d <- data, into: %{}, do: {d.source, d.flow}

follow = fn node, next ->
  [next, node]
  |> Stream.iterate(fn [h | t] ->
    if h not in nodes, do: [hd(data_by_source[h].destinations -- t), h | t]
  end)
  |> Enum.take_while(&amp; &amp;1)
  |> List.last()
end

lengths =
  for node <- nodes, dest <- data_by_source[node].destinations, into: %{} do
    path = follow.(node, dest)
    {[node, hd(path)], length(path) - 1}
  end

destinations =
  lengths
  |> Map.keys()
  |> Enum.group_by(&amp;Enum.at(&amp;1, 0), &amp;Enum.at(&amp;1, 1))

fill_in_distances = fn known_distances ->
  new_pairs =
    for {p, dp} <- known_distances,
        {q, dq} <- known_distances,
        p != q,
        MapSet.intersection(p, q) |> MapSet.size() == 1,
        pq = MapSet.difference(MapSet.union(p, q), MapSet.intersection(p, q)),
        not is_map_key(known_distances, pq),
        do: {pq, dp + dq}

  best_computed_distances =
    new_pairs
    |> Enum.group_by(&amp;elem(&amp;1, 0), &amp;elem(&amp;1, 1))
    |> Map.new(fn {p, ds} -> {p, Enum.min(ds)} end)

  Map.merge(known_distances, best_computed_distances)
end

initial = for {p, d} <- lengths, into: %{}, do: {MapSet.new(p), d}

all_distances =
  initial
  |> then(fill_in_distances)
  |> then(fill_in_distances)
  |> then(fill_in_distances)

all_distances_from =
  all_distances
  |> Enum.flat_map(fn {pair, d} ->
    [p, q] = Enum.to_list(pair)
    [{p, q, d}, {q, p, d}]
  end)
  |> Enum.reduce(%{}, fn {p, q, d}, acc ->
    Map.update(acc, p, %{q => d}, &amp;Map.put(&amp;1, q, d))
  end)

# dynp

defmodule ProboscideaVolcanium do
  def paths(starting, other_nodes, remaining_time, flows, distances) do
    f = remaining_time * flows[starting]
    no_move = %{p: [starting], t: 0, total: f}

    other_moves =
      for q <- other_nodes,
          d = distances[starting][q],
          d < remaining_time,
          remaining = List.delete(other_nodes, q),
          path <- paths(q, remaining, remaining_time - d - 1, flows, distances),
          do: %{path | p: [starting | path.p], total: f + path.total}

    [no_move | other_moves]
  end
end

Part One

%{total: best_strategy_for_part_1} =
  "AA"
  |> ProboscideaVolcanium.paths(nodes -- ["AA"], 30, flows, all_distances_from)
  |> Enum.max_by(& &1.total)

Part Two

p26 =
  "AA"
  |> ProboscideaVolcanium.paths(nodes -- ["AA"], 26, flows, all_distances_from)
  |> Enum.reduce(%{}, fn x, acc ->
    Map.update(acc, Enum.sort(x.p -- ["AA"]), x.total, &max(&1, x.total))
  end)

Enum.max(
  for {p, c} <- p26,
      {ep, ec} <- p26,
      c + ec > best_strategy_for_part_1,
      p -- ep == p,
      ep -- p == ep,
      do: c + ec
)

2348 is too low