Day 9

1 files changed, 95 insertions, 0 deletions

diff --git a/2015/day9.exs b/2015/day9.exs
new file mode 100644
index 0000000..d50b51b
--- /dev/null
+++ b/2015/day9.exs
@@ -0,0 +1,95 @@
+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}")