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.
117 lines
3.5 KiB
Elixir
117 lines
3.5 KiB
Elixir
defmodule Day18 do
|
|
def run do
|
|
map_list =
|
|
File.read!("data.txt")
|
|
|> String.trim()
|
|
|> String.split("\n")
|
|
|> Enum.map(fn line -> String.split(line, ",") |> Enum.map(&String.to_integer/1) end)
|
|
|
|
height = 71
|
|
width = 71
|
|
|
|
map_list1 = Enum.take(map_list, 1024)
|
|
|
|
# create the grid as a map
|
|
map1 =
|
|
Enum.reduce(0..(height - 1), %{}, fn row, acc ->
|
|
Enum.reduce(0..(width - 1), acc, fn col, acc2 ->
|
|
char = if Enum.member?(map_list1, [col, row]), do: :wall, else: :empty
|
|
Map.put(acc2, {col, row}, char)
|
|
end)
|
|
end)
|
|
|
|
start = {0, 0}
|
|
dest = {width - 1, height - 1}
|
|
|
|
# create a map of visited nodes an a queue
|
|
visited = %{start => 100_000_000}
|
|
q = :queue.from_list([{start, 0, [{0, 0}]}])
|
|
|
|
{_path, shortest} = walk(map1, q, dest, visited, [], 100_000_000_000, width, height)
|
|
dbg(shortest)
|
|
|
|
# count up from 1024 and create a new map each time, until we create an impassable map
|
|
part2 =
|
|
Enum.reduce(1024..length(map_list), nil, fn idx, acc ->
|
|
if !is_nil(acc) do
|
|
# exit early, we already found the coord
|
|
acc
|
|
else
|
|
# take the first N coords
|
|
map_list = Enum.take(map_list, idx)
|
|
|
|
# generate a new map with that many blocks fallen
|
|
map =
|
|
Enum.reduce(0..(height - 1), %{}, fn row, acc ->
|
|
Enum.reduce(0..(width - 1), acc, fn col, acc2 ->
|
|
char = if Enum.member?(map_list, [col, row]), do: :wall, else: :empty
|
|
Map.put(acc2, {col, row}, char)
|
|
end)
|
|
end)
|
|
|
|
start = {0, 0}
|
|
dest = {width - 1, height - 1}
|
|
|
|
# create a map of visited nodes an a queue
|
|
visited = %{start => 100_000_000}
|
|
q = :queue.from_list([{start, 0, [{0, 0}]}])
|
|
|
|
res = walk(map, q, dest, visited, [], 100_000_000_000, width, height)
|
|
|
|
if is_nil(res) do
|
|
List.last(map_list)
|
|
else
|
|
nil
|
|
end
|
|
end
|
|
end)
|
|
|
|
dbg(part2)
|
|
end
|
|
|
|
defp walk(map, q, {dx, dy} = dest, visited, paths, shortest_path, width, height) 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
|
|
nil
|
|
else
|
|
lowest = Enum.min_by(ql, fn {_, dist, _} -> dist end)
|
|
{{x, y}, dist, path} = lowest
|
|
new_q = :queue.delete(lowest, q)
|
|
|
|
# if we reached the destination
|
|
if x == dx and y == dy do
|
|
{path, dist}
|
|
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, :empty)} end)
|
|
|> Enum.filter(fn {{x, y}, el} ->
|
|
el != :wall and x >= 0 and y >= 0 and x < width and y < height
|
|
end)
|
|
|> Enum.reject(fn {{nx, ny}, _el} -> Map.has_key?(visited, {nx, ny}) end)
|
|
|> Enum.reject(fn {{nx, ny}, _el} ->
|
|
Enum.any?(:queue.to_list(q), fn {pos, _, _} -> pos == {nx, ny} end)
|
|
end)
|
|
|> Enum.map(fn {key, _el} -> key end)
|
|
|
|
new_q2 =
|
|
Enum.reduce(neighbors, new_q, fn {nx, ny}, acc ->
|
|
:queue.in({{nx, ny}, dist + 1, [{x, y} | path]}, acc)
|
|
end)
|
|
|
|
new_visited = Map.put(visited, {x, y}, dist)
|
|
walk(map, new_q2, dest, new_visited, paths, shortest_path, width, height)
|
|
end
|
|
end
|
|
end
|
|
end
|
|
|
|
Day18.run()
|