edgesText = File.stream!("inputs/day9.txt")

costs =
  Enum.reduce(edgesText, %{}, fn line, acc ->
    [_, a, b, distance] = Regex.run(~r/(\w+) to (\w+) = (\d+)/, line)
    {distance, ""} = Integer.parse(distance)

    {_, newAcc} =
      Map.get_and_update(acc, a, fn
        nil -> {nil, %{b => distance}}
        aToBeDistances -> {aToBeDistances, Map.put(aToBeDistances, b, distance)}
      end)

    {_, newAcc} =
      Map.get_and_update(newAcc, b, fn
        nil -> {nil, %{a => distance}}
        bToADistances -> {bToADistances, Map.put(bToADistances, a, distance)}
      end)

    newAcc
  end)

defmodule MemoizedTravellingSanta do
  use Agent

  def start do
    Agent.start_link(fn -> %{} end, name: __MODULE__)
  end

  def findShortestPath(costs) do
    pathCosts =
      Enum.map(costs, fn {start, _} ->
        shortestStartingHere =
          MemoizedTravellingSanta.findShortestPath(costs, MapSet.new([start]), start)

        shortestStartingHere
      end)

    min =
      Enum.map(pathCosts, fn {min, _} -> min end)
      |> Enum.min()

    max =
      Enum.map(pathCosts, fn {_, max} -> max end)
      |> Enum.max()

    {min, max}
  end

  def findShortestPath(costs, visited, current) do
    if map_size(costs) == MapSet.size(visited) do
      {0, 0}
    else
      cached_value = Agent.get(__MODULE__, &Map.get(&1, {costs, visited, current}))

      if cached_value do
        cached_value
      else
        leavingCosts = Map.get(costs, current, %{})

        pathCosts =
          Enum.filter(leavingCosts, fn {next, _} -> !MapSet.member?(visited, next) end)
          |> Enum.map(fn {next, cost} ->
            {minSubcost, maxSubcost} =
              MemoizedTravellingSanta.findShortestPath(
                costs,
                MapSet.put(visited, next),
                next
              )

            {cost + minSubcost, cost + maxSubcost}
          end)

        min =
          Enum.map(pathCosts, fn {min, _} -> min end)
          |> Enum.min()

        max =
          Enum.map(pathCosts, fn {_, max} -> max end)
          |> Enum.max()

        result = {min, max}
        Agent.update(__MODULE__, &Map.put(&1, {costs, visited, current}, result))
        result
      end
    end
  end
end

{:ok, _} = MemoizedTravellingSanta.start()

{min, max} = MemoizedTravellingSanta.findShortestPath(costs)

IO.puts("Shortest distance: #{min}")
IO.puts("Longest distance: #{max}")