AoC 2022 Day 16

Mix.install([:kino, :libgraph])

defmodule Utils do
  def split(line, sep \\ "") do
    String.split(line, sep, trim: true)
  end

  def split_all_lines(text, sep \\ "") do
    text
    |> String.split("\n", trim: true)
    |> Enum.map(&split(&1, sep))
  end

  def to_numbers(number) when is_binary(number) do
    String.to_integer(number)
  end

  def to_numbers(numbers) when is_list(numbers) do
    Enum.map(numbers, &to_numbers/1)
  end

  def to_matrix(text, sep \\ "") do
    text
    |> split_all_lines(sep)
    |> then(fn data ->
      for {row, r} <- Enum.with_index(data), {col, c} <- Enum.with_index(row) do
        {{r, c}, col}
      end
    end)
    |> Map.new()
  end
end

Setup

import Utils

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

text = Kino.Input.read(input)

data =
  split(text, "\n")
  |> Map.new(fn line ->
    [from | to] =
      ~r/[A-Z]{2}/
      |> Regex.scan(line)
      |> List.flatten()

    rate =
      ~r/\d+/
      |> Regex.scan(line)
      |> List.flatten()
      |> to_numbers()
      |> List.first()

    {from, %{neighbours: to, rate: rate}}
  end)

P1

defmodule P1 do
  def solve(data, ticks \\ 30) do
    graph =
      Graph.add_edges(
        Graph.new(),
        data
        |> Enum.map(fn {k, v} -> Enum.map(v.neighbours, &{k, &1}) end)
        |> List.flatten()
      )

    rates = Map.new(data, fn {k, v} -> {k, v.rate} end)

    candidates =
      data |> Enum.filter(fn {_k, v} -> v.rate > 0 end) |> Enum.map(fn {k, _v} -> k end)

    cache =
      (for c <- candidates do
         {{"AA", c}, Graph.get_shortest_path(graph, "AA", c) |> length |> Kernel.-(1)}
       end ++
         for c1 <- candidates, c2 <- candidates, c1 != c2 do
           {{c1, c2}, Graph.get_shortest_path(graph, c1, c2) |> length |> Kernel.-(1)}
         end)
      |> Map.new()

    search(rates, "AA", candidates, ticks, cache)
  end

  def search(rates, curr, candidates, remaining, cache) do
    candidates
    |> Enum.map(fn next ->
      cost = cache[{curr, next}]
      remaining = remaining - cost - 1
      gain = rates[next] * remaining

      if remaining > 0 do
        gain + search(rates, next, candidates -- [next], remaining, cache)
      else
        0
      end
    end)
    |> Enum.max(fn -> 0 end)
  end
end

P1.solve(data)

P2

defmodule P2 do
  def solve(data, ticks \\ 26) do
    graph =
      Graph.add_edges(
        Graph.new(),
        data
        |> Enum.map(fn {k, v} -> Enum.map(v.neighbours, &{k, &1}) end)
        |> List.flatten()
      )

    rates = Map.new(data, fn {k, v} -> {k, v.rate} end)

    candidates =
      data |> Enum.filter(fn {_k, v} -> v.rate > 0 end) |> Enum.map(fn {k, _v} -> k end)

    cache =
      (for c <- candidates do
         {{"AA", c}, Graph.get_shortest_path(graph, "AA", c) |> length |> Kernel.-(1)}
       end ++
         for c1 <- candidates, c2 <- candidates, c1 != c2 do
           {{c1, c2}, Graph.get_shortest_path(graph, c1, c2) |> length |> Kernel.-(1)}
         end)
      |> Map.new()

    search(rates, [{ticks, "AA"}, {ticks, "AA"}], candidates, cache)
  end

  def search(rates, state, candidates, cache) do
    {{min, standby}, {max, curr}} = Enum.min_max(state)

    candidates
    |> Enum.map(fn next ->
      cost = cache[{curr, next}]
      remaining = max - cost - 1
      gain = rates[next] * remaining

      if remaining > 0 do
        gain + search(rates, [{min, standby}, {remaining, next}], candidates -- [next], cache)
      else
        if min > 0 do
          P1.search(rates, standby, candidates, min, cache)
        else
          0
        end
      end
    end)
    |> Enum.max(fn -> 0 end)
  end
end

P2.solve(data)