Discussion thread for day 16 of the Advent of Code - https://adventofcode.com/2024/day/16
This problem is not as complicated as it may seem initially (once you understand the algorithm behind it):
I love spatial analysis. For part2, it took 10min but I'm satisfied with it.
I do like to trace a path. Part 2 wasn't any harder than Part1 since you already have the target number.
Assorted notes:
D16. More in spoiler
Done.
I revised the (WF over and over again, but I finally managed to complete it. WF runs in 8 seconds for P1 and P2.
In P1, progressing one cell at a time was too time-consuming, so process is optimized by using "Make Group" Tool to group linear sections. Within the iterative macro, only cases with the minimum length for each point at the same loop were retained for processing.
In P2, running the normal approach caused the number of cases to increase exponentially. To address this, only the paths that matched the shortest length to each point determined in P1 are remainind in iterative macro. Since the required path was determined as a straight polyline, Spatial Match Tool is ussd to identify the points along the path.
Not sure whether to be very happy that my original part 1 approach only needed the SLIGHTEST of tweaks to work extremely well and fast to get me the solution to part 2... or to be very mad at the fact that I wasted much of my afternoon/evening going down different paths trying to get other things to work first before coming back to what I had originally...
Finally, solved!
This puzzle is my final solved puzzle this year.
In Part 1, I used Dijkstra's algorithm.
In Part 2, I knew that the amount of calculations would be large, so I grouped the straight-line paths together and converted them into a graph problem. This shortened the workflow of Part 1, which took 20 minutes, to 3 minutes. However, this algorithm became very redundant because it took a lot of trial and error to solve it.
The approach of Part 2 solved the puzzle by finding the shortest distance from an intersection node to another intersection node among the optimization paths calculated in Part 1. Basically, the cost of generating a different path from one point to another point is more than 1000 points, so this reduces the number of searches.
It's very concise if I just write the main points, but it took a lot of debugging and trial and error. This is one of the most difficult puzzle this year for me.