Day 16

day16.livemd

Bryan Oltman

@bryanoltman

adventofcode2022

Share to X

Share to Bluesky

More notebooks

Day 16

Setup

https://adventofcode.com/2022/day/16

defmodule Valve do
  defstruct name: "", flow_rate: 0, neighbor_names: MapSet.new()

  def new(line) do
    regex =
      ~r/Valve (?\w+) has flow rate=(?\d+); tunnel[s]? lead[s]? to valve[s]? (?.*)/

    map = Regex.named_captures(regex, line)
    flow_rate = map["flow_rate"] |> Integer.parse() |> elem(0)

    neighbor_names =
      map["neighbors"]
      |> String.split(",", trim: true)
      |> Enum.map(fn str -> String.trim(str) end)
      |> MapSet.new()

    %Valve{name: map["name"], flow_rate: flow_rate, neighbor_names: neighbor_names}
  end
end

Valve.new("Valve HH has flow rate=22; tunnel leads to valve GG")

defmodule Load do
  def input do
    File.read!(Path.join(Path.absname(__DIR__), "input/16.txt"))
  end
end

defmodule Parse do
  # returns a tuple of {first_valve, map of valve names to valves}
  def input(input_str) do
    valves =
      input_str
      |> String.split("\n", trim: true)
      |> Enum.map(&amp;Valve.new(&amp;1))

    tree = :digraph.new()

    Enum.each(valves, fn valve -> :digraph.add_vertex(tree, valve) end)

    Enum.each(valves, fn valve ->
      valve.neighbor_names
      |> Enum.each(fn neighbor_name ->
        neighbor = valves |> Enum.find(fn valve -> valve.name == neighbor_name end)
        :digraph.add_edge(tree, valve, neighbor)
      end)
    end)

    tree
  end
end

test_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
  """
  |> Parse.input()

real_input =
  Load.input()
  |> Parse.input()

Part 1

defmodule Part1 do
  # No more valves left to close
  def visit_valves(_, [], opened_valves, _, _, _) do
    {opened_valves}
  end

  # We ran out of time before getting to this valve
  def visit_valves(_, _, opened_valves, _, _, minutes_left) when minutes_left <= 0 do
    {opened_valves}
  end

  def visit_valves(
        current_valve,
        closed_valves,
        opened_valves,
        valve_graph,
        route_map,
        minutes_left
      ) do
    new_closed_valves = MapSet.delete(closed_valves, current_valve)

    # If the starting valve has a flow rate of 0 (it does), we don't actually close it.
    # Don't count it against our running time.
    {new_opened_valves, minutes_after_opening} =
      case current_valve.flow_rate do
        0 ->
          {opened_valves, minutes_left}

        _ ->
          {opened_valves ++ [{current_valve, minutes_left - 1}], minutes_left - 1}
      end

    if Enum.count(new_closed_valves) == 0 do
      {new_opened_valves}
    else
      new_closed_valves
      |> Enum.map(fn valve ->
        route = route_map[current_valve][valve]

        # -1 to exclude current_valve from the path
        distance = Enum.count(route) - 1

        visit_valves(
          valve,
          new_closed_valves,
          new_opened_valves,
          valve_graph,
          route_map,
          minutes_after_opening - distance
        )
      end)
    end
  end

  def get_valve(valve_graph, name) do
    valve_graph
    |> :digraph.vertices()
    |> Enum.find(fn valve -> valve.name == name end)
  end

  def solve(valve_graph) do
    minutes = 30

    first_valve = get_valve(valve_graph, "AA")

    nonzero_valves =
      valve_graph
      |> :digraph.vertices()
      |> Enum.filter(fn valve -> valve.flow_rate > 0 end)

    valves_to_visit = [first_valve] ++ nonzero_valves

    # Paths from starting and nonzero-flow-rate valves to each other
    # {
    #   valveA -> {
    #     valveB -> [shortest_path]
    #     valveC -> [shortest_path]
    #   },
    #   valveB -> {
    #     ...
    #   }
    # }
    route_map =
      Enum.map(valves_to_visit, fn a ->
        paths =
          valves_to_visit
          |> Enum.reject(fn valve -> valve == a end)
          |> Enum.map(fn b -> {b, :digraph.get_short_path(valve_graph, a, b)} end)
          |> Map.new()

        {a, paths}
      end)
      |> List.flatten()
      |> Map.new()

    visit_valves(first_valve, MapSet.new(valves_to_visit), [], valve_graph, route_map, minutes)
    # Comleted route, minute pairs are put in tuples to allow for the flattening of the
    # deeply- and unevenly-nested list returned by visit_valves.
    |> List.flatten()
    |> Enum.map(fn {route_minutes} -> route_minutes end)
    |> Enum.map(fn route ->
      # create a list of routes to their pressure scores
      {route,
       route
       |> Enum.reduce(0, fn {valve, minutes}, acc ->
         acc + valve.flow_rate * minutes
       end)}
    end)
    |> Enum.max_by(fn {_, pressure} -> pressure end)
    |> elem(1)
  end
end

Part1.solve(test_input)

Part1.solve(real_input)

Part 2

defmodule Part2 do
  # No more valves left to close
  def visit_valves(_, [], opened_valves, _, _, _) do
    [{opened_valves}]
  end

  # We ran out of time before getting to this valve
  def visit_valves(_, _, opened_valves, _, _, minutes_left) when minutes_left <= 0 do
    [{opened_valves}]
  end

  def visit_valves(
        current_valve,
        closed_valves,
        opened_valves,
        valve_graph,
        route_map,
        minutes_left
      ) do
    new_closed_valves = MapSet.delete(closed_valves, current_valve)

    # If the starting valve has a flow rate of 0 (it does), we don't actually close it.
    # Don't count it against our running time.
    {new_opened_valves, minutes_after_opening} =
      case current_valve.flow_rate do
        0 ->
          {opened_valves, minutes_left}

        _ ->
          {opened_valves ++ [{current_valve, minutes_left - 1}], minutes_left - 1}
      end

    if Enum.count(new_closed_valves) == 0 do
      [{new_opened_valves}]
    else
      new_closed_valves
      |> Enum.map(fn valve ->
        route = route_map[current_valve][valve]

        # -1 to exclude current_valve from the path
        distance = Enum.count(route) - 1

        stop_here_open_valves =
          cond do
            # Because there are two simultaneous runners, stopping here may yield an optimal route.
            # 3 is arbitrarily chosen and may need to be tuned.
            Enum.count(new_opened_valves) > 2 -> [{new_opened_valves}]
            true -> []
          end

        visit_valves(
          valve,
          new_closed_valves,
          new_opened_valves,
          valve_graph,
          route_map,
          minutes_after_opening - distance
        ) ++ stop_here_open_valves
      end)
    end
  end

  def get_valve(valve_graph, name) do
    valve_graph
    |> :digraph.vertices()
    |> Enum.find(fn valve -> valve.name == name end)
  end

  def solve(valve_graph) do
    minutes = 26

    first_valve = get_valve(valve_graph, "AA")

    nonzero_valves =
      valve_graph
      |> :digraph.vertices()
      |> Enum.filter(fn valve -> valve.flow_rate > 0 end)

    valves_to_visit = [first_valve] ++ nonzero_valves

    # Paths from starting and nonzero-flow-rate valves to each other
    # {
    #   valveA -> {
    #     valveB -> [shortest_path]
    #     valveC -> [shortest_path]
    #   },
    #   valveB -> {
    #     ...
    #   }
    # }
    route_map =
      Enum.map(valves_to_visit, fn a ->
        paths =
          valves_to_visit
          |> Enum.reject(fn valve -> valve == a end)
          |> Enum.map(fn b -> {b, :digraph.get_short_path(valve_graph, a, b)} end)
          |> Map.new()

        {a, paths}
      end)
      |> List.flatten()
      |> Map.new()

    route_flows =
      visit_valves(
        first_valve,
        MapSet.new(valves_to_visit),
        [],
        valve_graph,
        route_map,
        minutes
      )
      |> List.flatten()
      |> Enum.map(fn {route_minutes} -> route_minutes end)
      |> Enum.map(fn route_minutes ->
        route =
          route_minutes
          |> Enum.map(&amp;elem(&amp;1, 0))

        # create a list of routes to their pressure scores
        {MapSet.new(route),
         route_minutes
         |> Enum.reduce(0, fn {valve, minutes}, acc ->
           acc + valve.flow_rate * minutes
         end)}
      end)
      |> Enum.sort_by(fn {_, pressure} -> pressure end, :desc)
      |> Enum.uniq_by(fn {route, _} -> route end)

    IO.puts("Comparing " <> inspect(Enum.count(route_flows)) <> " routes")

    {mine, elephants} =
      Enum.reduce(route_flows, [], fn {a_route, a_pressure}, acc ->
        acc ++
          Enum.reduce(route_flows, [], fn {b_route, b_pressure}, acc ->
            cond do
              a_route == b_route -> acc
              MapSet.disjoint?(a_route, b_route) -> acc ++ [{a_pressure, b_pressure}]
              true -> acc
            end
          end)
      end)
      |> Enum.max_by(fn {a, b} -> a + b end)

    mine + elephants
  end
end

Part2.solve(test_input)

Part2.solve(real_input)

Other notebooks:

Goody27
@Goody27

elixir_segmantation

Untitled notebook

setup.livemd

kino evision axon table_rex axon_onnx nx exla stb_image flow

2023-10-9
Andrey Marchenko
@anmarchenko

notebooks

Howlongtobeat

howlongtobeat.livemd

httpoison jason floki kino

2024-11-20
Shozo Fukuda
@shoz-f

onnx_interp

Monocular Depth Estimation: SC-DepthV3

ScDepth.livemd

onnx_interp cimg nx kino

2024-5-18
Sebastian Heiden
@sehHeiden

poll_election_bavaria_202...

Bavarian Election

election_bavaria.livemd

httpoison explorer kino_vega_lite exla kino_bumblebee bumblebee adbc tucan scholar nx

2023-8-14
@DockYard-Academy

curriculum

OpenAI Chat API

deprecated_open_ai_chat.livemd

jason finch kino youtube hidden_cell

2023-6-5
Numerical Elixir (Nx)
@elixir-nx

nx_signal

The Discrete Fourier Transform (DFT)

fft.livemd

nx_signal vega_lite kino_vega_lite

2025-1-28
Tyler Johnson
@tylerj

aoc

Day 8 - Advent of Code 2023

day-08.livemd

kino benchee math

2023-12-9

Back