You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
129 lines
3.7 KiB
Elixir
129 lines
3.7 KiB
Elixir
defmodule Day16 do
|
|
def run do
|
|
map_list =
|
|
File.read!("data.txt")
|
|
|> String.trim()
|
|
|> String.split("\n")
|
|
|> Enum.map(&String.graphemes/1)
|
|
|
|
height = length(map_list)
|
|
width = length(hd(map_list))
|
|
|
|
# convert the map List to a map Map
|
|
map =
|
|
Enum.concat(map_list)
|
|
|> Enum.with_index()
|
|
|> Enum.reduce(%{}, fn {el, idx}, acc ->
|
|
Map.put(acc, {div(idx, height), rem(idx, width)}, el)
|
|
end)
|
|
|
|
# starting position always at bottom left, facing east
|
|
start = {height - 2, 1, {0, 1}}
|
|
# end is always at the top right
|
|
dest = {1, width - 2}
|
|
|
|
# create a map of visited nodes an a queue
|
|
visited = %{start => 100_000_000}
|
|
q = :queue.from_list([{start, 0, [{0, 0}]}])
|
|
|
|
{paths, shortest} = walk(map, q, dest, visited, [], 100_000_000_000)
|
|
dbg(shortest)
|
|
|
|
num_on_all_paths =
|
|
Enum.reduce(paths, [], fn p, acc -> Enum.concat(p, acc) end)
|
|
|> Enum.uniq()
|
|
|> length()
|
|
|
|
dbg(num_on_all_paths)
|
|
end
|
|
|
|
defp walk(map, q, {dx, dy} = dest, visited, paths, shortest_path) do
|
|
# dequeue the node with the lowest distnce
|
|
# no priority queue, so just find the lowest one and delete it from the queue
|
|
ql = :queue.to_list(q)
|
|
|
|
if length(ql) == 0 do
|
|
{paths, shortest_path}
|
|
else
|
|
lowest = Enum.min_by(ql, fn {_, dist, _} -> dist end)
|
|
{{x, y, dir}, dist, path} = lowest
|
|
new_q = :queue.delete(lowest, q)
|
|
|
|
# if we reached the destination
|
|
if x == dx and y == dy do
|
|
# remove everything from the queue with distances greater than shortest_path
|
|
new_q2 = :queue.filter(fn {_, d, _} -> d <= shortest_path end, new_q)
|
|
|
|
# add it to the list of paths if it's <= to the current shortest path
|
|
if dist <= shortest_path do
|
|
new_paths = [path | paths]
|
|
walk(map, new_q2, dest, visited, new_paths, dist)
|
|
else
|
|
walk(map, new_q2, dest, visited, paths, shortest_path)
|
|
end
|
|
else
|
|
dirs = [{-1, 0}, {0, 1}, {1, 0}, {0, -1}]
|
|
|
|
# find neighbors to enqueue
|
|
neighbors =
|
|
dirs
|
|
|> Enum.map(fn {dx, dy} -> {x + dx, y + dy} end)
|
|
|> Enum.map(fn key -> {key, Map.get(map, key, ".")} end)
|
|
|> Enum.filter(fn {_key, el} -> el != "#" end)
|
|
# visited must include the direction. You can validly visit a cell from multiple directions
|
|
|> Enum.reject(fn {{nx, ny}, _el} ->
|
|
key = {nx, ny, {nx - x, ny - y}}
|
|
Map.has_key?(visited, key)
|
|
end)
|
|
|> Enum.map(fn {key, _el} -> key end)
|
|
|
|
new_q2 =
|
|
Enum.reduce(neighbors, new_q, fn {nx, ny}, acc ->
|
|
# dir is the previous direction
|
|
new_dir = {nx - x, ny - y}
|
|
new_dist = dist + if dir == new_dir, do: 1, else: 1001
|
|
|
|
:queue.in({{nx, ny, new_dir}, new_dist, [{x, y} | path]}, acc)
|
|
end)
|
|
|
|
new_visited = Map.put(visited, {x, y, dir}, dist)
|
|
walk(map, new_q2, dest, new_visited, paths, shortest_path)
|
|
end
|
|
end
|
|
end
|
|
|
|
defp render(map, location \\ nil, visited \\ %{}) do
|
|
width = Map.keys(map) |> Enum.map(&elem(&1, 1)) |> Enum.max()
|
|
height = Map.keys(map) |> Enum.map(&elem(&1, 0)) |> Enum.max()
|
|
|
|
Enum.each(0..height, fn row ->
|
|
Enum.each(0..width, fn col ->
|
|
if !is_nil(location) and location == {row, col} do
|
|
IO.write(IO.ANSI.format([:red_background, "@"]))
|
|
else
|
|
el = Map.get(map, {row, col}, ".")
|
|
|
|
visited? = Enum.member?(visited, {row, col})
|
|
|
|
formatted =
|
|
if visited? do
|
|
IO.ANSI.format([:blue_background, el])
|
|
else
|
|
el
|
|
end
|
|
|
|
IO.write(formatted)
|
|
end
|
|
end)
|
|
|
|
IO.write("\n")
|
|
end)
|
|
|
|
IO.write("\n")
|
|
|
|
map
|
|
end
|
|
end
|
|
|
|
Day16.run()
|