Discussion thread for day 20 of the Advent of Code - https://adventofcode.com/2024/day/20
Another good one today. Nice to have something that isn't a skill tester on nested iterative macros or find the one math trick to finish before the heat death of the universe.
Also, this was my PR global leaderboard rank. Good times.
My solution.
Part1.
Count the number of steps from the goal. (Similar to day 16)
Subtract the number of warp seconds from the ABS of up/down or left/right steps. That's the cheat time.
Part2.
I stopped focusing on #.
Warp from field to field.
Excellent Explanation, @ScottLewis! Today was another very nice problem, and I must say AoC has definitely delivered this year with the exception of day 6 (Day 15 was also needlessly tough, but that was my own fault, not the problem itself)
Day 20. More in spoiler
Solved!
I don't have time to solve them in real time, so I'm rushing to catch up.
In Part 1, neighbor points were created for the completed route, and then a point was created at the end of that straight line. This was then combined with the walking (?) route. This was able to identify the cheat points, but there were also cheat points that went back in time, so the number of seconds elapsed on the walking route was compared, and only points that were later in time than the points before the cheat were extracted as combined points. However, this did not tell me whether the route passes through a wall, so I checked whether the neighbor points on the original route are walls, and then combined them with the wall data to create the final cheat point. After doing Part 2, I knew that I did something very roundabout.
In Part 2, routes with a Manhattan distance of 20 or less for each walking point are candidate points for cheating (because the route must return to the original route within 20 steps). I simply Cartesian combine the walking routes, and extract points with a Manhattan distance of 20 or less that are chronologically later than each point. The saved time is calculated by subtracting the Manhattan distance from the time difference.
If you change the 20 in Part 2 to 2, it will also fit in Part 1.
Day20 seems similar to Day18 at the biginning but it is different.
I tried utilizing the macro optimized for Day 18, but even if a single check only takes a few seconds, the process would require 10,000 iterations, resulting in an unfeasible amount of time. I gave up on this approach. After discussing it with @gawa , I realized that the routee is a single path from S to E, and all . tiles are part of the path. With this insight, I changed my approach and rebuilt the workflow.
For the single path, I calculated the time from S for each tile. Then, the tiles adjacent to each # are identified and calculated the time difference between them. However, I overlooked including S and E in the calculations, which cost me some time in debugging.
For P2, I first narrowed down the candidate tiles, but there were over a million cases. I initially tried checking whether the tiles between two points were connected by #, but the loop process for a million cases was far too heavy and had to be abandoned.
After consulting @CoG's spoiler, I learned that the path does not necessarily have to pass exclusively through ###; it can briefly enter ... and then return to ###. This meant that I could simply select tiles with an XY-coordinate difference of 20 or less and calculate from there. With this adjustment, I was able to solve the problem relatively simply.
Now, the workflow completes in 2 minutes.