Day 16

Mix.install([{:kino, "~>0.8.0"}])

Setup

input = Kino.Input.textarea("input file")

Common

defmodule Day16_2 do
  def parse_line(valve) do
    [[_, valve_id, flow_rate, valve_paths]] =
      Regex.scan(
        ~r/^Valve (.+) has flow rate=(\d+); tunnel[s]? lead[s]? to valve[s]? (.+)$/,
        valve
      )

    valves = valve_paths |> String.split(", ", trim: true)

    {valve_id, %{flow_rate: String.to_integer(flow_rate), tunnels: valves, valve: valve_id}}
  end
end

defmodule PathFinder_2 do
  defp async_mapper do
    fn input, callback ->
      input
      |> Task.async_stream(callback)
      |> Enum.map(fn {:ok, res} -> res end)
    end
  end

  def find_path(
        origin,
        remaining_minutes,
        distances,
        valves,
        acc_enabled_valves \\ [],
        mapper \\ async_mapper()
      ) do
    distances
    |> Map.fetch!(origin)
    |> Enum.reject(&(elem(&1, 0) in acc_enabled_valves))
    |> mapper.(fn
      {target, distance} when distance + 1 < remaining_minutes ->
        new_remaining_minutes = remaining_minutes - (distance + 1)

        released_pressure = new_remaining_minutes * Map.fetch!(valves, target).flow_rate

        released_pressure +
          find_path(
            target,
            new_remaining_minutes,
            distances,
            valves,
            [target | acc_enabled_valves],
            &amp;Enum.map/2
          )

      {_target, _distance} ->
        0
    end)
    |> Enum.max(fn -> 0 end)
  end

  def find_path_part_2(
        states,
        distances,
        valves,
        available_valves \\ [],
        mapper \\ async_mapper()
      ) do
    [{origin, remaining_minutes} | rest_states] = Enum.sort_by(states, &amp;elem(&amp;1, 1), :desc)

    available_valves
    |> Enum.map(&amp;{&amp;1, distances[{origin, &amp;1}]})
    |> mapper.(fn
      {target, distance} when distance + 1 < remaining_minutes ->
        remaining_minutes = remaining_minutes - (distance + 1)

        released_pressure = remaining_minutes * Map.fetch!(valves, target).flow_rate

        released_pressure +
          find_path(
            [{target, remaining_minutes} | rest_states],
            distances,
            valves,
            available_valves -- [target],
            &amp;Enum.map/2
          )

      {_target, _distance} when rest_states != [] ->
        find_path(
          rest_states,
          distances,
          valves,
          available_valves,
          &amp;Enum.map/2
        )

      {_target, _distance} ->
        0
    end)
    |> Enum.max(fn -> 0 end)
  end
end

Part 1 - Take 2

initial_position = "AA"
available_minutes = 30

valves_map =
  input
  |> Kino.Input.read()
  |> String.split("\n", trim: true)
  |> Enum.map(fn valve_description ->
    Day16_2.parse_line(valve_description)
  end)
  |> Map.new()

graph = :digraph.new()

for valve <- Map.keys(valves_map) do
  :digraph.add_vertex(graph, valve)
end

for {valve, %{tunnels: tunnels}} <- valves_map,
    target_valve <- tunnels do
  :digraph.add_edge(graph, valve, target_valve)
end

distances =
  for origin <- Map.keys(valves_map),
      origin == "AA" or valves_map[origin].flow_rate > 0,
      target <- Map.keys(valves_map),
      origin != target,
      valves_map[target].flow_rate > 0 do
    path = :digraph.get_short_path(graph, origin, target)
    {origin, target, length(path) - 1}
  end
  |> Enum.group_by(&amp;elem(&amp;1, 0), &amp;{elem(&amp;1, 1), elem(&amp;1, 2)})
  |> Map.new(&amp;{elem(&amp;1, 0), Map.new(elem(&amp;1, 1))})

:digraph.delete(graph)

initial_position
|> PathFinder_2.find_path(available_minutes, distances, valves_map)

Part 2 - take 2

initial_position = "AA"
available_minutes = 26

valves =
  input
  |> Kino.Input.read()
  |> String.split("\n", trim: true)
  |> Enum.map(fn valve_description ->
    Day16_2.parse_line(valve_description)
  end)
  |> Map.new()

graph = :digraph.new()

for valve <- Map.keys(valves) do
  :digraph.add_vertex(graph, valve)
end

for {valve, %{tunnels: tunnels}} <- valves,
    target_valve <- tunnels do
  :digraph.add_edge(graph, valve, target_valve)
end

non_zero_flow_rate_valves =
  valves
  |> Enum.filter(&amp;match?({_valve, %{flow_rate: flow_rate}} when flow_rate > 0, &amp;1))
  |> Enum.map(&amp;elem(&amp;1, 0))

distances =
  for origin <- ["AA" | non_zero_flow_rate_valves],
      target <- non_zero_flow_rate_valves,
      origin != target do
    path = :digraph.get_short_path(graph, origin, target)
    {origin, target, length(path) - 1}
  end
  |> Map.new(&amp;{{elem(&amp;1, 0), elem(&amp;1, 1)}, elem(&amp;1, 2)})

:digraph.delete(graph)

defmodule PathFinder_3 do
  defp async_mapper do
    fn input, callback ->
      input
      |> Task.async_stream(callback, timeout: :infinity, ordered: false)
      |> Enum.map(fn {:ok, res} -> res end)
    end
  end

  def find_path(
        states,
        distances,
        valves,
        available_valves \\ [],
        mapper \\ async_mapper()
      ) do
    [{origin, remaining_minutes} | rest_states] = Enum.sort_by(states, &amp;elem(&amp;1, 1), :desc)

    available_valves
    |> Enum.map(&amp;{&amp;1, distances[{origin, &amp;1}]})
    |> mapper.(fn
      {target, distance} when distance + 1 < remaining_minutes ->
        remaining_minutes = remaining_minutes - (distance + 1)

        released_pressure = remaining_minutes * Map.fetch!(valves, target).flow_rate

        released_pressure +
          find_path(
            [{target, remaining_minutes} | rest_states],
            distances,
            valves,
            available_valves -- [target],
            &amp;Enum.map/2
          )

      {_target, _distance} when rest_states != [] ->
        find_path(
          rest_states,
          distances,
          valves,
          available_valves,
          &amp;Enum.map/2
        )

      {_target, _distance} ->
        0
    end)
    |> Enum.max(fn -> 0 end)
  end
end

[{"AA", available_minutes}, {"AA", available_minutes}]
|> PathFinder_3.find_path(distances, valves, non_zero_flow_rate_valves)
|> IO.puts()