diff options
| -rw-r--r-- | src/day16.exs | 194 |
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}") |