input = Kino.Input.textarea("Please input data:")data =
input
|> Kino.Input.read()
|> String.split("\n", trim: true)
|> Enum.map(&String.to_charlist/1)
|> Enum.map(fn line ->
Enum.map(line, fn char -> List.to_integer([char]) end)
end)coords =
data
|> Enum.with_index()
|> Enum.map(fn {line, row_idx} ->
Enum.with_index(line)
|> Enum.map(fn {col, col_idx} ->
{{col_idx, row_idx}, col}
end)
end)
|> Enum.concat()
|> Enum.into(%{})defmodule PriorityQueue do
@moduledoc "A not very efficient priority queue."
@type priority_queue :: {list(), map()}
@spec new() :: priority_queue()
@doc "Creates an empty priority queue."
def new() do
# 2-element tuple
# list contains the sorted priorities
# map contains pairs key (prio) => value (elements with that prio)
{_priorities = [], _values = %{}}
end
@spec insert(priority_queue(), integer(), any()) :: priority_queue()
def insert({priorities, values}, prio, value) do
# just insert the priority, sort it and make sure no duplicates
new_priorities = [prio | priorities] |> Enum.sort() |> Enum.uniq()
# add the value in the bucket of the priority
new_values = Map.update(values, prio, [value], &[value | &1])
{new_priorities, new_values}
end
@spec min(priority_queue()) :: {any(), priority_queue()}
@doc "Returns the element with the lowest priority value."
def min({[], _} = pq), do: {nil, pq}
def min({[prio | rest_prios] = all_prio, values}) do
[value | rest_values] = values |> Map.get(prio)
if Enum.empty?(rest_values) do
{value, {rest_prios, Map.delete(values, prio)}}
else
{value, {all_prio, Map.put(values, prio, rest_values)}}
end
end
enddefmodule Pathfinder do
@moduledoc """
A functional rewrite of wikipedia's Djikstra pseudocode.
See https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
"""
defp djikstra(dist_map, prev_map, _pq, _edges, end_node, end_node) do
# finally finished
{dist_map, prev_map}
end
defp djikstra(dist_map, prev_map, pq, edges, u = {x, y}, end_node) do
{_, edges} = Map.pop(edges, u)
cost_u = dist_map[u]
# explore all neighbors
neighbors =
[
{x - 1, y},
{x, y - 1},
{x + 1, y},
{x, y + 1}
]
|> Enum.map(fn key -> {key, edges[key]} end)
|> Enum.reject(fn {_, cost} -> is_nil(cost) end)
{dist_map, prev_map, pq} =
Enum.reduce(neighbors, {dist_map, prev_map, pq}, fn
{v, cost_v}, {dist_map, prev_map, pq} ->
new_dist = cost_u + cost_v
prev_dist = dist_map[v]
# elixir fact that helps here: any number < nil
if new_dist < prev_dist do
{
Map.put(dist_map, v, new_dist),
Map.put(prev_map, v, u),
PriorityQueue.insert(pq, new_dist, v)
}
else
{dist_map, prev_map, pq}
end
end)
# recurse
djikstra(dist_map, prev_map, pq, edges, end_node)
end
defp djikstra(dist_map, prev_map, pq, edges, end_node) do
{k, pq} = PriorityQueue.min(pq)
# k = {0, 0}
djikstra(dist_map, prev_map, pq, edges, k, end_node)
end
defp get_path(_map, start_node, start_node, acc), do: acc
defp get_path(map, current_node, start_node, acc) do
next_node = map[current_node]
get_path(map, next_node, start_node, [next_node | acc])
end
@doc """
Performs a shortest path search using [Djikstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm).
Returns one shortest path from `start_node` to `end_node`.
"""
def search(edges, start_node, end_node) do
dist_map = %{start_node => 0}
prev_map = %{}
pq =
PriorityQueue.new()
|> PriorityQueue.insert(0, start_node)
{_dist_map, prev_map} = djikstra(dist_map, prev_map, pq, edges, end_node)
get_path(prev_map, end_node, start_node, [end_node])
end
@doc """
Prints a path in the same way as on the AoC page.
"""
def print_path(path, grid) do
{{max_x, _}, _} = Enum.max_by(grid, fn {{x, _y}, _} -> x end)
{{_, max_y}, _} = Enum.max_by(grid, fn {{_x, y}, _} -> y end)
set = MapSet.new(path)
for y <- 0..max_y do
IO.puts(
for x <- 0..max_x do
val = grid[{x, y}]
if {x, y} in set do
"#{IO.ANSI.bright()}#{val}#{IO.ANSI.clear()}"
else
"#{IO.ANSI.normal()}#{val}#{IO.ANSI.clear()}"
end
end
)
end
path
end
end{{max_x, max_y}, _} = Enum.max_by(coords, fn {k, _v} -> k end)
[{0, 0} | path] =
Pathfinder.search(coords, {0, 0}, {max_x, max_y})
|> Pathfinder.print_path(coords)
# count the costs along the path
Enum.reduce(path, 0, &(&2 + coords[&1]))defmodule PathExpansion do
defp step_mapper(:x, x, y, amount, {max_x, _max_y}), do: {x + (max_x + 1) * amount, y}
defp step_mapper(:y, x, y, amount, {_max_x, max_y}), do: {x, y + (max_y + 1) * amount}
def map_coords(coords, x_or_y, amount) do
{{max_x, max_y}, _} = Enum.max_by(coords, fn {k, _v} -> k end)
Enum.map(coords, fn {{x, y}, risk} ->
new_risk = if risk + amount >= 10, do: rem(risk + amount, 10) + 1, else: risk + amount
{step_mapper(x_or_y, x, y, amount, {max_x, max_y}), new_risk}
end)
|> Enum.into(%{})
end
end
# it's ugly, but it works
coords_x =
coords
|> Map.merge(PathExpansion.map_coords(coords, :x, 1))
|> Map.merge(PathExpansion.map_coords(coords, :x, 2))
|> Map.merge(PathExpansion.map_coords(coords, :x, 3))
|> Map.merge(PathExpansion.map_coords(coords, :x, 4))
coords =
coords_x
|> Map.merge(PathExpansion.map_coords(coords_x, :y, 1))
|> Map.merge(PathExpansion.map_coords(coords_x, :y, 2))
|> Map.merge(PathExpansion.map_coords(coords_x, :y, 3))
|> Map.merge(PathExpansion.map_coords(coords_x, :y, 4))
{{max_x, max_y}, _} = Enum.max_by(coords, fn {k, _v} -> k end)
[{0, 0} | path] = Pathfinder.search(coords, {0, 0}, {max_x, max_y})
# |> Pathfinder.print_path(coords)
Enum.reduce(path, 0, fn node, acc -> acc + coords[node] end)