I think I was clever by precalculating a search area to iterate over:
Part 1 example (5.7ms): 0
Part 1 input (93.0ms): 1417
Part 2 example (17.5ms): 0
Part 2 input (2382.3ms): 1014683
1 Like
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)
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
1 Like
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.
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.
