summaryrefslogtreecommitdiffstats
path: root/src/day16.exs
diff options
context:
space:
mode:
authorAlexandre Jesus <adbjesus@gmail.com>2024-12-16 19:51:33 +0000
committerAlexandre Jesus <adbjesus@gmail.com>2024-12-16 19:52:12 +0000
commit11ab619de9e4d4116dd7727347a9eba9dd72c584 (patch)
tree79a9d4991995737d250687ace23dd8a118a6cc4e /src/day16.exs
parentf7d640f6c26921cdc65831a780470ccd93c53870 (diff)
downloadaoc2024-11ab619de9e4d4116dd7727347a9eba9dd72c584.tar.gz
aoc2024-11ab619de9e4d4116dd7727347a9eba9dd72c584.zip
Day 16
Diffstat (limited to 'src/day16.exs')
-rw-r--r--src/day16.exs194
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}")