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.
113 lines
3.2 KiB
Elixir
113 lines
3.2 KiB
Elixir
defmodule Day20 do
|
|
def run do
|
|
{map, width, height, start, dest} = parse_input("data.txt")
|
|
|
|
# create a map of visited nodes an a queue
|
|
visited = %{start => 100_000_000}
|
|
q = :queue.from_list([{start, 0, []}])
|
|
|
|
{path, shortest} = walk(map, q, dest, visited, [], 100_000_000_000, width, height)
|
|
path = Enum.reverse(path)
|
|
|
|
part1 = run(2, path)
|
|
part2 = run(20, path)
|
|
dbg({part1, part2})
|
|
end
|
|
|
|
# walk every step along the path
|
|
# find coordinates that we can get to within <cheat> number of steps, that save us 100 picoseconds
|
|
defp run(cheats, path) do
|
|
Enum.with_index(path)
|
|
|> Enum.reduce(0, fn {el, idx}, acc ->
|
|
res =
|
|
path
|
|
|> Enum.with_index()
|
|
|> Enum.filter(fn {el2, idx2} ->
|
|
dist = distance(el, el2)
|
|
dist <= cheats and idx + dist + 100 <= idx2
|
|
end)
|
|
|> length
|
|
|
|
acc + res
|
|
end)
|
|
end
|
|
|
|
defp distance({x1, y1}, {x2, y2}) do
|
|
abs(x2 - x1) + abs(y2 - y1)
|
|
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 = next_from_queue(ql, dest)
|
|
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
|
|
{[{x, y} | 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, ".")} end)
|
|
|> Enum.filter(fn {{x, y}, el} ->
|
|
el != "#" 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
|
|
|
|
defp parse_input(file) do
|
|
map_list =
|
|
File.read!(file)
|
|
|> 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, grabbing start and dest along the way
|
|
{map, start, dest} =
|
|
Enum.concat(map_list)
|
|
|> Enum.with_index()
|
|
|> Enum.reduce({%{}, nil, nil}, fn {el, idx}, {map, start, dest} ->
|
|
row = div(idx, height)
|
|
col = rem(idx, width)
|
|
|
|
map = Map.put(map, {row, col}, el)
|
|
start = if el == "S", do: {row, col}, else: start
|
|
dest = if el == "E", do: {row, col}, else: dest
|
|
|
|
{map, start, dest}
|
|
end)
|
|
|
|
{map, width, height, start, dest}
|
|
end
|
|
end
|
|
|
|
Day20.run()
|