Advent of Code 2024 - Day 16

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!

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2024/day16.ex

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…

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:
https://github.com/lud/adventofcode/blob/main/lib/solutions/2024/day16.ex

The pathfinding code:
https://github.com/lud/adventofcode/blob/main/lib/advent_of_code/path_finder/multi.ex

And as often the grid:
https://github.com/lud/adventofcode/blob/main/lib/advent_of_code/grid.ex

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

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:

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.

https://github.com/Aetherus/advent-of-code/blob/719c475eeb2cc409cf1c0c9598ce4acbd3389d74/2024/day-16.livemd

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

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.