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)
The idea of "cheating" is a sort of red herring. It may lead you to believe that you need to concern yourself with maze's walls, but thankfully, you do not! All that matters is where you start and where you end up, and as long as you start and end within the maze path within the time duration for each part (2 moves vs 20 moves), you have successfully cheated.
Thus, you can join each maze point to all reachable points within the time duration (accounting for double joining, by filtering on position or index of each point in the maze), then take the difference between the indices of the maze positions - difference in maze position (to account for time taken to cheat: ABS([row1] - [row2]) + ABS([col1] - [col2])) and you have found the time save!
Maze Solver (optimization is the top filter tool):
Main Workflow:
Day 20. More in spoiler
P2: Created a grid of -20 to 20 for rows and columns, and matched it with the path I already generated. Calculated Final Steps based on steps away and the grid absolute value points
\
Solved!
I don't have time to solve them in real time, so I'm rushing to catch up.
First I needed to get the route from the start to the goal. Since it's a linear path, I didn't need any algorithms, just a simple iterative macro. It's so simple!
Since I had to create neighbor points many times, I created a point creation macro for when searching for the next point...
Actually, my part1 algorithm is not good.
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.
