Advent of Code 2024 - Day 20

I solved today’s problem by precalculating the distances from End to Start. Then I started the traversal again from Start to End and for each non wall tile, I checked all the neighboring tiles that are <= 2 or 20 units apart and calculated the total distance as:

total_distance = distance from start + distance to end + manhattan distance to tile

Total distance calculation was O(1) as I’m maintaining distance from start during traversal and distance to end was precalculated in the previous traversal.

I got the following timings for both the parts:

Name             ips        average  deviation         median         99th %
part_1         13.72       72.87 ms    ±33.96%       67.47 ms      224.52 ms
part_2          0.66         1.51 s    ±23.69%         1.38 s         2.03 s

Code can be found on my github: AdventOfCodeElixir/lib/advent/year2024/day20.ex at main · divxvid/AdventOfCodeElixir · GitHub

I had a “too high” result for part 2 because I forgot to check if the cheat was <= 20 tiles . It took me some time to figure out that I just totally forgot the basic rule.

I rewrote part 1 with the same algorithm as part 2, and I get similar time for both (around 520ms), because for each track I have to check a possible cheat with all remaining track positions

I found small optimizations to go down to 350ms but not worth the noise in the code.

My algorithm is quite simple: for each tile of the ordered track, compute the manhattan distance to each tile of the rest of the track (but skip the first 101), compare with the normal distance, and count +1 if the cheat is saving more than 100.

defmodule AdventOfCode.Solutions.Y24.Day20 do
  alias AdventOfCode.Grid
  alias AoC.Input

  def parse(input, _part) do
    {grid, _, %{start: start, finish: finish}} =
      input
      |> Input.stream!(trim: true)
      |> Grid.parse_lines(fn
        _, ?# -> :ignore
        _, ?. -> {:ok, :track}
        xy, ?E -> {:ok, :track, finish: xy}
        xy, ?S -> {:ok, :track, start: xy}
      end)

    {grid, start, finish}
  end

  def part_one({grid, start, finish}, save_at_least \\ 100) do
    solve(grid, start, finish, 2, save_at_least)
  end

  def part_two({grid, start, finish}, save_at_least \\ 100) do
    solve(grid, start, finish, 20, save_at_least)
  end

  defp solve(grid, start, finish, max_cheat, save_at_least) do
    track = compute_path(grid, start, finish)
    count_cheats(track, max_cheat, save_at_least)
  end

  defp compute_path(grid, start, finish) do
    compute_path(grid, start, _prev = nil, finish, 0, [])
  end

  defp compute_path(_grid, finish, _prev, finish, index, acc) do
    :lists.reverse([{finish, index} | acc])
  end

  defp compute_path(grid, pos, prev, finish, index, acc) do
    [next] = pos |> Grid.cardinal4() |> Enum.filter(&(&1 != prev && Map.has_key?(grid, &1)))
    compute_path(grid, next, pos, finish, index + 1, [{pos, index} | acc])
  end

  defp count_cheats(track, max_cheat, save_at_least, count \\ 0)

  defp count_cheats([_last], _, _, count) do
    count
  end

  defp count_cheats([current_pos | track], max_cheat, save_at_least, count) do
    {activation_pos, activation_index} = current_pos

    count =
      track
      |> Enum.drop(save_at_least + 1)
      |> Enum.reduce(count, fn {dest_pos, dest_index}, count ->
        cheat_dist = manhattan(activation_pos, dest_pos)

        if cheat_dist <= max_cheat && dest_index - activation_index - cheat_dist >= save_at_least do
          count + 1
        else
          count
        end
      end)

    count_cheats(track, max_cheat, save_at_least, count)
  end

  def manhattan({x1, y1}, {x2, y2}), do: abs(x1 - x2) + abs(y1 - y2)
end

This was a fun one! My initial implementation, before I looked at the data, tried a similar technique as the one with the guard and the rocks - delete each wall square, rerun path calculation, note difference - which worked for part 1, but was stupidly slow (like 70 seconds). And then I saw part 2 and it didn’t work there anyway

So I thought about it a bit, looked at the data, noted that every single floor square was part of the path, so I didn’t need to do any path recalculation - I just needed to slice parts out of the calculated path. And I didn’t even need to do that, I could index each item in the path and work out the difference.

Part 2 is a wee bit slow because I worked out allllll the options within 20 squares of each path square and calculated the difference, but it’s still under a second!

(and trying to optimize with Task.async_stream made it an order of magnitude slower)

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

Name                     ips        average  deviation         median         99th %
day 20, part 1         13.45       74.33 ms     ±6.84%       74.14 ms       83.83 ms
day 20, part 2          1.30      771.43 ms     ±1.61%      767.13 ms      796.90 ms

Agree, this one was fun. Creating these cheat paths, though, relies on the shortest non-cheat path having only one solution. I could probably make it faster w/ Task, but it runs fast enough to get the answer, and I’ve spent too much time on it already.

https://github.com/rvnash/aoc2024/blob/main/lib/d20.ex

Part 1: 1351 in 31.232ms
Part 2: 966130 in 2879.704ms

This one was pretty fun in the end, but I spent some time to understand the instructions well.
Here is my solution :

defmodule Y2024.D20 do
  use Day, input: "2024/20", part1: ~c"g", part2: ~c"g"

  @n {-1, 0}
  @e {0, +1}
  @s {+1, 0}
  @w {0, -1}

  defp partX(input, max_cheat_size, save) do
    raw_map = Matrix.to_rc_map(input)

    start_rc = find_key(raw_map, "S")
    end_rc = find_key(raw_map, "E")

    raw_map
    |> Map.replace(start_rc, ".")
    |> Map.replace(end_rc, ".")
    |> path(nil, start_rc, end_rc, [])
    |> count_cheats(max_cheat_size, save)
  end

  defp part1(input), do: partX(input, 2, 100)
  defp part2(input), do: partX(input, 20, 100)

  def count_cheats([], _, _), do: 0

  def count_cheats([from | tail], max_cheat_size, save) do
    tail
    |> Enum.drop(save)
    |> Enum.with_index()
    |> Enum.count(fn {to, index} ->
      cheat_size = distance(from, to)
      cheat_size <= max_cheat_size and index + 1 >= cheat_size
    end)
    |> Kernel.+(count_cheats(tail, max_cheat_size, save))
  end

  def path(_, _, target_rc, target_rc, wip), do: Enum.reverse([target_rc | wip])

  def path(map, previous_rc, current_rc, target_rc, wip) do
    [next_rc] =
      [@n, @e, @s, @w]
      |> Enum.map(&forward(current_rc, &1))
      |> Enum.reject(&(&1 == previous_rc))
      |> Enum.filter(&(Map.get(map, &1) == "."))

    path(map, current_rc, next_rc, target_rc, [current_rc | wip])
  end

  defp distance({r1, c1}, {r2, c2}), do: abs(r2 - r1) + abs(c2 - c1)
  defp forward({r, c}, {dr, dc}), do: {r + dr, c + dc}

  defp find_key(map, value) do
    map
    |> Enum.find(&(elem(&1, 1) == value))
    |> elem(0)
  end
end

Part 2 run in ~1640ms on my machine.

It took me a long time to find a bug in part 2. The runtime was about 4 seconds when I had fixed that bug. I then spent some additional time to clean up and optimize the code.

The combined runtime for both parts and the examples is 0.6 seconds.

https://github.com/bjorng/advent-of-code/blob/main/2024/day20/lib/day20.ex