Day 16HEADmaster

1 files changed, 194 insertions, 0 deletions

diff --git a/src/day16.exs b/src/day16.exs
new file mode 100644
index 0000000..827dc25
--- /dev/null
+++ b/src/day16.exs
@@ -0,0 +1,194 @@
+defmodule Day16 do
+  defmodule State do
+    @enforce_keys [:pqueue, :map, :path, :dist]
+    defstruct [:pqueue, :map, :path, :dist]
+
+    def new(game) do
+      pqueue = :gb_sets.from_list([{0, game.start}])
+      map = :gb_trees.insert(game.start, 0, :gb_trees.empty())
+      path = Map.new([{game.start, []}])
+      dist = Map.new([{game.start, 0}])
+      %State{pqueue: pqueue, map: map, path: path, dist: dist}
+    end
+
+    def upsert(state, posdir, dist, prev) do
+      case :gb_trees.lookup(posdir, state.map) do
+        :none ->
+          pqueue = :gb_sets.insert({dist, posdir}, state.pqueue)
+          map = :gb_trees.insert(posdir, dist, state.map)
+          path = Map.put(state.path, posdir, [prev])
+          distmap = Map.update(state.dist, posdir, dist, &min(&1, dist))
+          %State{pqueue: pqueue, map: map, path: path, dist: distmap}
+        {_, odist} ->
+          distmap = Map.update!(state.dist, posdir, &min(&1, dist))
+          cond do
+            dist > odist ->
+              %State{state | dist: distmap}
+            dist == odist ->
+              path = Map.update!(state.path, posdir, &[prev | &1])
+              %State{state | path: path, dist: distmap}
+            true ->
+              pqueue = :gb_sets.delete({odist, posdir}, state.pqueue)
+              pqueue = :gb_sets.insert({dist, posdir}, pqueue)
+              map = :gb_trees.update(posdir, dist, state.map)
+              path = Map.put(state.path, posdir, [prev])
+              %State{pqueue: pqueue, map: map, path: path, dist: distmap}
+          end
+      end
+    end
+
+    def empty?(state) do
+      :gb_sets.is_empty(state.pqueue)
+    end
+
+    def pop(state) do
+      {v, pqueue} = :gb_sets.take_smallest(state.pqueue)
+      {v, %State{state | pqueue: pqueue}}
+    end
+
+    def optimal_dist(state, node) do
+      state.dist
+      |> Enum.filter(fn {{pos, _}, _} -> pos == node end)
+      |> Enum.map(fn {_, v} -> v end)
+      |> Enum.min()
+    end
+
+    def optimal_path_nodes(state, node) do
+      nodes = state.dist
+      |> Enum.filter(fn {{pos, _}, _} -> pos == node end)
+
+      mindist = nodes
+      |> Enum.map(fn {_, v} -> v end)
+      |> Enum.min()
+
+      nodes = nodes
+      |> Enum.filter(fn {_, v} -> v == mindist end)
+      |> Enum.map(fn {posdir, _} -> posdir end)
+
+      optimal_path_nodes(state, nodes, [])
+    end
+
+    defp optimal_path_nodes(state, queue, acc) do
+      case queue do
+        [] ->
+          acc
+          |> Enum.map(fn {pos, _} -> pos end)
+          |> Enum.uniq()
+        [h | t] ->
+          acc = [h | acc]
+          queue = Map.fetch!(state.path, h) ++ t
+          optimal_path_nodes(state, queue, acc)
+      end
+    end
+  end
+
+  defmodule Game do
+    @derive Inspect
+    defstruct [:grid, :start, :end]
+
+    def from_data(data) do
+      grid = data
+      |> String.split("\n", trim: true)
+      |> Enum.with_index()
+      |> Enum.flat_map(fn {s, i} ->
+        String.codepoints(s)
+        |> Enum.with_index()
+        |> Enum.map(fn {c, j} -> {{i, j}, c} end)
+      end)
+      |> Map.new()
+
+      start = grid
+      |> Enum.find_value(fn {pos, c} -> c == "S" and pos end)
+      |> then(& {&1, :right})
+
+      endpos = grid
+      |> Enum.find_value(fn {pos, c} -> c == "E" and pos end)
+
+      %Game{grid: grid, start: start, end: endpos}
+    end
+
+    def shortest(game) do
+      game
+      |> shortest(State.new(game))
+      |> State.optimal_dist(game.end)
+    end
+
+    def shortest_path_nodes(game) do
+      game
+      |> shortest(State.new(game))
+      |> State.optimal_path_nodes(game.end)
+    end
+
+    defp shortest(game, state) do
+      if State.empty?(state) do
+        state
+      else
+        {{dist, {pos, dir}}, state} = State.pop(state)
+        if pos == game.end do
+          shortest(game, state)
+        else
+          neighbors(game, {dist, {pos, dir}})
+          for {ndist, nposdir} <- neighbors(game, {dist, {pos, dir}}), reduce: state do
+            state -> State.upsert(state, nposdir, ndist, {pos, dir})
+          end
+          |> then(& shortest(game, &1))
+        end
+      end
+    end
+
+    defp neighbors(game, {dist, {{i, j}, dir}}) do
+      case dir do
+        :right ->
+          [{dist+1, {{i, j+1}, :right}},
+           {dist+1001, {{i-1, j}, :up}},
+           {dist+1001, {{i+1, j}, :down}},
+           {dist+2001, {{i, j-1}, :left}}]
+        :left ->
+          [{dist+1, {{i, j-1}, :left}},
+           {dist+1001, {{i-1, j}, :up}},
+           {dist+1001, {{i+1, j}, :down}},
+           {dist+2001, {{i, j+1}, :right}}]
+        :up ->
+          [{dist+1, {{i-1, j}, :up}},
+           {dist+1001, {{i, j-1}, :left}},
+           {dist+1001, {{i, j+1}, :right}},
+           {dist+2001, {{i+1, j}, :down}}]
+        :down ->
+          [{dist+1, {{i+1, j}, :down}},
+           {dist+1001, {{i, j-1}, :left}},
+           {dist+1001, {{i, j+1}, :right}},
+           {dist+2001, {{i-1, j}, :up}}]
+      end
+      |> Enum.filter(fn {_, {p, _}} ->
+        case Map.fetch(game.grid, p) do
+          :error -> false
+          {:ok, "#"} -> false
+          _ -> true
+        end
+      end)
+    end
+  end
+
+  def part1(data) do
+    data
+    |> Game.from_data()
+    |> Game.shortest()
+  end
+
+  def part2(data) do
+    data
+    |> Game.from_data()
+    |> Game.shortest_path_nodes()
+    |> Enum.count()
+  end
+end
+
+data = IO.read(:stdio, :eof)
+
+{time1, ans1} = :timer.tc(fn -> Day16.part1(data) end)
+IO.puts("Time  : #{time1 / 1000000}")
+IO.puts("Answer: #{ans1}")
+
+{time2, ans2} = :timer.tc(fn -> Day16.part2(data) end)
+IO.puts("Time  : #{time2 / 1000000}")
+IO.puts("Answer: #{ans2}")