After getting the correct answer for both parts, I spent some time optimizing the execution time. Now the combined time for both parts is 3.4 seconds.
1 Like
For part 1, I used a fairly straightforward priority queue implementation - we’ve had quite a few puzzles like this before.
Part 2 was an interesting one… I ended up implementing some weird “store how we got here” logic as different paths reached the same point and then backtracking over all of those once I found the fastest solution.
I think it might not work correctly if there are two paths to the destination that don’t converge before the destination, but I don’t have that case in any of my inputs so yay!
Name ips average deviation median 99th %
day 16, part 1 12.91 77.43 ms ±5.49% 77.14 ms 86.71 ms
day 16, part 2 13.07 76.51 ms ±5.00% 76.09 ms 85.69 ms
Now I have some boxes from yesterday to go and argue with some more…
2 Likes
It went smoothly, even if this implementation is not very fast 
defmodule Y2024.D16 do
use Day, input: "2024/16", part1: ~c"l", part2: ~c"l"
@n {-1, 0}
@e {0, +1}
@s {+1, 0}
@w {0, -1}
defp part1(input) do
partX(input, fn lowest, end_rc ->
lowest
|> Enum.filter(fn {{rc, _}, _} -> rc == end_rc end)
|> Enum.map(fn {{_, _}, score} -> score end)
|> Enum.min()
end)
end
defp part2(input) do
partX(input, fn lowest, end_rc ->
lowest_end =
lowest
|> Enum.filter(fn {{rc, _}, _} -> rc == end_rc end)
|> Enum.min_by(fn {{_, _}, score} -> score end)
MapSet.new([lowest_end])
|> backtrack(lowest, lowest_end)
|> Enum.map(&elem(&1, 0))
|> Enum.uniq_by(&elem(&1, 0))
|> Enum.count()
end)
end
defp partX(input, postprocess) do
map =
input
|> parse_input()
|> Matrix.to_rc_map()
{start_rc, "S"} = Enum.find(map, &(elem(&1, 1) == "S"))
{end_rc, "E"} = Enum.find(map, &(elem(&1, 1) == "E"))
%{}
|> walk(map, start_rc, @e, 0)
|> postprocess.(end_rc)
end
defp walk(lowest, map, rc, dir, score) do
case Map.get(lowest, {rc, dir}) do
nil ->
walk(Map.put_new(lowest, {rc, dir}, score), map, rc, Map.get(map, rc), dir, score)
previous_score ->
if score < previous_score do
walk(Map.replace(lowest, {rc, dir}, score), map, rc, Map.get(map, rc), dir, score)
else
lowest
end
end
end
defp walk(lowest, _, _, "#", _, _), do: lowest
defp walk(lowest, _, _, "E", _, _), do: lowest
defp walk(lowest, map, rc, _, dir, score) do
lowest
|> walk(map, forward(rc, dir), dir, score + 1)
|> walk(map, forward(rc, cw(dir)), cw(dir), score + 1001)
|> walk(map, forward(rc, ccw(dir)), ccw(dir), score + 1001)
end
defp backtrack(best, lowest, to) do
matching_previous =
lowest
|> Enum.filter(&match_previous?(to, &1))
|> MapSet.new()
Enum.reduce(
MapSet.difference(matching_previous, best),
MapSet.union(best, matching_previous),
&backtrack(&2, lowest, &1)
)
end
defp match_previous?({{to_rc, to_dir}, to_score}, {{from_rc, from_dir}, from_score}) do
from_rc == backward(to_rc, to_dir) and
((from_dir == to_dir and from_score == to_score - 1) or
(from_dir == cw(to_dir) and from_score == to_score - 1001) or
(from_dir == ccw(to_dir) and from_score == to_score - 1001))
end
defp forward({r, c}, {dr, dc}), do: {r + dr, c + dc}
defp backward({r, c}, {dr, dc}), do: {r - dr, c - dc}
defp cw(@n), do: @e
defp cw(@e), do: @s
defp cw(@s), do: @w
defp cw(@w), do: @n
defp ccw(@n), do: @w
defp ccw(@w), do: @s
defp ccw(@s), do: @e
defp ccw(@e), do: @n
defp parse_input(input), do: Enum.map(input, &Utils.splitrim/1)
end
The first part builds a map of the lowest score possible to reach each reachable cell in a given direction, giving the shortest path length for the end cell.
The second part backtracks this map fo flag cells that are part of the shortest path to the end.
I have a solution that takes less than 100ms but I had to rewrite a path finding algorithm that let me pass a function to take the cost in account.
The solution:
The pathfinding code:
And as often the grid:
I used Dijkstra’s shortest path algorithm for this question and implemented this using a min heap. Runtime for both the problems was around 30ms.
My solution for both parts: AdventOfCodeElixir/lib/advent/year2024/day16.ex at main · divxvid/AdventOfCodeElixir · GitHub
Benchee results:
Name ips average deviation median 99th %
part_1 29.20 34.25 ms ±11.38% 33.76 ms 50.57 ms
part_2 29.84 33.51 ms ±13.54% 32.51 ms 62.69 ms
3 Likes
Rather prescient of me yesterday 
But not enough, because my naive initial exhaustive recursive attempt blew up on the actual input and I gave up.
I’m stumped on this one. My solution for part 1 so far can solve both examples as well as every example listed here:
https://www.reddit.com/r/adventofcode/comments/1hfhgl1/2024_day_16_part_1_alternate_test_case/
Any clues?
defmodule ReindeerMaze do
def solve(input) do
{map, grid} = parse(input)
{start, _} = map |> Enum.find(&(elem(&1, 1) == "S"))
{fin, _} = map |> Enum.find(&(elem(&1, 1) == "E"))
find_min(map, grid, start, {1, 0}, MapSet.new, fin)
end
def find_min(_, _, fin, _, _, fin), do: 0
def find_min(map, grid, {x, y} = coord, facing, seen, fin) do
if cache = Process.get({coord, facing}) do
cache
else
q = Grid2D.neighbors(coord, grid, :straight)
|> Stream.reject(&MapSet.member?(seen, &1))
|> Stream.reject(&(Map.get(map, &1) == "#"))
|> Stream.map(fn {xx, yy} = p ->
dir = {xx - x, yy - y}
next = find_min(map, grid, p, dir, MapSet.put(seen, coord), fin)
if next != :infinity do
(if dir == facing, do: 1, else: 1001) + next
else
:infinity
end
end)
|> Enum.min(fn -> :infinity end)
Process.put({coord, facing}, q)
q
end
end
def parse(input) do
map =
for {line, y} <- input |> String.split("\n", trim: true) |> Stream.with_index(),
{c, x} <- line |> String.graphemes() |> Stream.with_index(),
into: %{} do
{{x, y}, c}
end
max = map |> Map.keys() |> Enum.max()
grid =
Grid2D.new(
(max |> elem(0)) + 1,
(max |> elem(1)) + 1
)
{map, grid}
end
end
Grid2D code:
defmodule Grid2D do
defstruct width: nil, height: nil
@directions %{
straight: [
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
],
diagonal: [
{1, 1},
{1, -1},
{-1, 1},
{-1, -1}
]
}
def new(width, height) do
%Grid2D{width: width, height: height}
end
@doc """
## Examples
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 0)
{0,0}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 5)
{0,1}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 6)
{1,1}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 3)
{3,0}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 24)
{4, 4}
"""
def index_to_coord(%Grid2D{width: w}, index) do
{rem(index, w), floor(index / w)}
end
@doc """
## Examples
iex> Grid2D.coord_to_index( Grid2D.new(5,5), {0,0})
0
iex> Grid2D.coord_to_index( Grid2D.new(5,5), {4,4})
24
iex> Grid2D.coord_to_index( Grid2D.new(5,5), {2,2})
12
"""
def coord_to_index(%Grid2D{width: w}, {x, y}) do
y * w + x
end
@doc """
## Examples
iex> Grid2D.neighbors({0, 0}, Grid2D.new(5,5)) |> MapSet.new()
MapSet.new([{0, 1}, {1, 1}, {1,0}])
iex> Grid2D.neighbors({2, 2}, Grid2D.new(5,5)) |> MapSet.new()
[{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}, {3, 3}] |> MapSet.new()
iex> Grid2D.neighbors({4, 4}, Grid2D.new(5,5)) |> MapSet.new
[{3, 3}, {3, 4}, {4, 3}] |> MapSet.new
"""
def neighbors(p, g, allowed_directions \\ :all) do
directions(allowed_directions)
|> Stream.map(&add(p, &1))
|> Stream.filter(&is_in_grid?(&1, g))
end
@doc """
Distance from two points in a grid
iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {0,1}, :radial)
1
iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {1,1}, :radial)
1
iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {1,2}, :radial)
2
"""
def distance(grid, p1, p2, type)
def distance(_, {x, y}, {a, b}, :radial), do: max(abs(x - a), abs(y - b))
@doc """
Add two points together pairwise
iex> Grid2D.add({0,0}, {0,1})
{0,1}
iex> Grid2D.add({2,3}, {3,2})
{5,5}
"""
def add({x, y}, {j, k}), do: {x + j, y + k}
@doc """
Test if a point is in a grid
iex> Grid2D.is_in_grid?({1, 2}, %Grid2D{width: 3, height: 4})
true
iex> Grid2D.is_in_grid?({2, 2}, %Grid2D{width: 2, height: 4})
false
"""
def is_in_grid?({x, y}, %Grid2D{width: w, height: h}), do: x < w and y < h and x >= 0 and y >= 0
@spec directions(allowed :: :all | :straight | :diagonal) :: any()
def directions(allowed \\ :all)
def directions(:all), do: directions(:straight) ++ directions(:diagonal)
def directions(:straight), do: @directions |> Map.get(:straight)
def directions(:diagonal), do: @directions |> Map.get(:diagonal)
def mul({x, y}, n), do: {n*x, n*y}
end
I found the issue here was I was trying to memoize the cost of the path from a point, p and a heading, h but that cost is dependent on the path taken, so there were cases where the memoized value could be incorrect for some paths.
I ended up scratching all of this code and rewriting it with Djikstra’s. Still haven’t solved part 2. 
Finally found a solution for Part 2! I just need to twist Dijkstra a bit, so that it continues to find other paths until the total weight exceeds the minimum total weight.
I have no desire nor time anymore to slam my head on these harder and harder challenges. Last time I implemented dijkstra was in collage in Java. 
I feel I’m not there yet skill wise to solve these challenges efficiently and in satisfactory time. Luckily, I have heads of you fine folks to slam right through. 
Again I learned from your code @bjorng. I do vibe with your style. 
First time playing with :gb_sets also. 
I changed some things per my liking but the code is pretty much the same.
defmodule Aoc2024.Solutions.Y24.Day16 do
alias AoC.Input
def parse(input, _part) do
input
|> Input.stream!(trim: true)
|> Stream.with_index()
|> Enum.reduce({{}, {}, %{}}, fn {line, x}, acc ->
line
|> String.to_charlist()
|> Enum.with_index()
|> Enum.reduce(acc, fn
{?S, y}, {_start, finish, map} -> {{x, y}, finish, Map.put(map, {x, y}, ?.)}
{?E, y}, {start, _finish, map} -> {start, {x, y}, Map.put(map, {x, y}, ?E)}
{e, y}, {start, finish, map} -> {start, finish, Map.put(map, {x, y}, e)}
end)
end)
end
def part_one({start, finish, map}) do
element = {_score = 0, _position = start, _direction = {0, 1}, _passed = MapSet.new()}
set = :gb_sets.singleton(element)
find_paths(set, map, finish, _visited = MapSet.new(), _max_score = nil)
end
def part_two({start, finish, map}) do
element = {_score = 0, _position = start, _direction = {0, 1}, _passed = MapSet.new()}
set = :gb_sets.singleton(element)
find_paths(set, map, finish, _visited = MapSet.new(), _max_score = :infinity)
|> Enum.reduce(MapSet.new(), fn set, acc -> MapSet.union(acc, set) end)
|> MapSet.size()
end
defp find_paths(set, map, finish, visited, max_score) do
case if not :gb_sets.is_empty(set), do: :gb_sets.take_smallest(set) do
nil ->
[]
# part 1 case
{{score, ^finish, _direction, _passed}, _set} when is_nil(max_score) ->
score
# part 2 case
{{score, ^finish, _direction, passed}, set} ->
if score <= max_score do
max_score = min(max_score, score)
[MapSet.put(passed, finish) | find_paths(set, map, finish, visited, max_score)]
else
[]
end
{{score, position, direction, passed}, set} ->
visited = MapSet.put(visited, {position, direction})
passed = if is_nil(max_score), do: MapSet.new(), else: MapSet.put(passed, position)
forward_path = forward_path(map, finish, score, position, direction, passed)
rotated_paths = rotated_paths(map, score, position, direction, passed)
paths = [forward_path | rotated_paths]
set = update_set(paths, set, map, visited)
find_paths(set, map, finish, visited, max_score)
end
end
defp forward_path(map, finish, score, {x, y} = _position, {xd, yd} = direction, passed) do
{xn, yn} = next_position = {x + xd, y + yd}
next_left_position = {xn - yd, yn + xd}
next_right_position = {xn + yd, yn - xd}
if next_position != finish and
Map.get(map, next_position) != ?# and
Map.get(map, next_left_position) == ?# and
Map.get(map, next_right_position) == ?# do
passed = MapSet.put(passed, next_position)
forward_path(map, finish, score + 1, next_position, direction, passed)
else
{score + 1, next_position, direction, passed}
end
end
defp rotated_paths(map, score, {x, y} = position, {xd, yd} = _direction, passed) do
left_position = {x - yd, y + xd}
left_path = {score + 1000, position, {-yd, xd}, passed}
right_position = {x + yd, y - xd}
right_path = {score + 1000, position, {yd, -xd}, passed}
paths = if Map.get(map, left_position) != ?#, do: [left_path], else: []
if Map.get(map, right_position) != ?#, do: [right_path | paths], else: paths
end
defp update_set(paths, set, map, visited) do
Enum.reduce(paths, set, fn {_score, position, direction, _passed} = element, set ->
cond do
Map.get(map, position) == ?# -> set
MapSet.member?(visited, {position, direction}) -> set
true -> :gb_sets.add(element, set)
end
end)
end
end
1 Like
I heard people complain that AoC basically monopolizes their free time around the holiday. Yikes. I’ll still give it a go after my dust settles but, not a good sign. Thanks for confirming the impression.
1 Like
Yeah the puzzles aren’t going anywhere, do them at your leisure 
(I stopped a few days ago because a) Christmas and b) 40 degree weather the last few days so my brain is cooked. Might pick it up again when it cools down)
2 Likes
