General Discussions

AlteryxCommunityTeam

Discussion thread for day 16 of the Advent of Code - https://adventofcode.com/2024/day/16

CoG

This problem is not as complicated as it may seem initially (once you understand the algorithm behind it):

This is another Breadth First Search (BFS) problem. That being said, we will want to be able to re-visit tiles if we can find a better score when moving in a certain direction.

Trying to only find the minimum score to reach the end can be tricky to formulate an approach to, but if instead we make it our goal to identify the lowest score required to reach every tile on the map from any direction, the problem (albeit counterintuitively) becomes easier to approach. We can think about the problem this way: The minimum score for a given target tile can only be reached if we had the minimum score possible on the tile just before the target. Working in reverse, if we know that our starting position has score 0, then its neighbors minimum score can be achieved by moving directly to the neighboring tile from the start. If we iterate over the entire maze, keeping track of the minimum score needed to reach any cell (defaulting to 99999999 or -1, except for the starting tile which has a score of 0 as mentioned before), We can successively move from any tile we've already visited, to its 3 neighbors based on the direction we are facing (we exclude going backwards since that will never result in a lower score), where we can update the minimum scores of the neighbors if and only if moving there from our current tile would result in a lower score, otherwise we ignore the movement. When no more improvements can be made, the algorithm is done, and we have the answer to part 1.

Algorithm constructed as Iterative macro:
Minimize Score.png

Part 2 seems way harder at first, but a shift in perspective makes this part a breeze with our understanding & work from part 1. The trick is identifying what feature of any tile would guarantee that it lives on a minimal path (a path that takes a reindeer from start to finish with minimum score). The sneaky way to answer this question: repeat our algorithm from part 1, but this time backwards from the end. Part 1 calculated the minimum score required to reach any point within the maze from the start. This new calculation would give us a table with the minimum scores required to reach any point in the maze from the end (or... when thought of from a new perspective) the minimum score required to reach the end from any point in the maze!!!) If we add these two scores together, we get the minimum score achievable when navigating the maze from start to finish, going through the given point. If that minimum score equals the absolute minimum score to go from start to end then that point lies on a minimum path. The count of the collection of all such points gives you the answer to part 2! (Note: don't forget when running the BFS from the End point that our direction is no longer restricted as it was with the start, since it doesn't matter how we reach the end)

Main workflow:

This is another Breadth First Search (BFS) problem. That being said, we will want to be able to re-visit tiles if we can find a better score when moving in a certain direction.Trying to only find the minimum score to reach the end can be tricky to formulate an approach to, but if instead we make it our goal to identify the lowest score required to reach every tile on the map from any direction, the problem (albeit counterintuitively) becomes easier to approach. We can think about the problem this way: The minimum score for a given target tile can only be reached if we had the minimum score possible on the tile just before the target. Working in reverse, if we know that our starting position has score 0, then its neighbors minimum score can be achieved by moving directly to the neighboring tile from the start. If we iterate over the entire maze, keeping track of the minimum score needed to reach any cell (defaulting to 99999999 or -1, except for the starting tile which has a score of 0 as mentioned before), We can successively move from any tile we've already visited, to its 3 neighbors based on the direction we are facing (we exclude going backwards since that will never result in a lower score), where we can update the minimum scores of the neighbors if and only if moving there from our current tile would result in a lower score, otherwise we ignore the movement. When no more improvements can be made, the algorithm is done, and we have the answer to part 1.Algorithm constructed as Iterative macro:Part 2 seems way harder at first, but a shift in perspective makes this part a breeze with our understanding & work from part 1. The trick is identifying what feature of any tile would guarantee that it lives on a minimal path (a path that takes a reindeer from start to finish with minimum score). The sneaky way to answer this question: repeat our algorithm from part 1, but this time backwards from the end. Part 1 calculated the minimum score required to reach any point within the maze from the start. This new calculation would give us a table with the minimum scores required to reach any point in the maze from the end (or... when thought of from a new perspective) the minimum score required to reach the end from any point in the maze!!!) If we add these two scores together, we get the minimum score achievable when navigating the maze from start to finish, going through the given point. If that minimum score equals the absolute minimum score to go from start to end then that point lies on a minimum path. The count of the collection of all such points gives you the answer to part 2! (Note: don't forget when running the BFS from the End point that our direction is no longer restricted as it was with the start, since it doesn't matter how we reach the end)Main workflow:

gawa

I love spatial analysis. For part2, it took 10min but I'm satisfied with it.

Spoiler

First ,identify the points at branch, and made line objects. I don't recommend to trace next points one by one because it will require way too long calculation process.
Recommend to exclude the points at dead-end because the path that reaches to the dead-end have no chance of getting the lowest score.(=no need to trace them)

Dead-end point
By using these lines, starting from "S", trace the next line that touches with the previous line. In order to record the history, I combined all of line objects that record has ever passed as field name "path" by ST_Combine([Path],[Line]). By comparing the "path" and next target line whether next line is within the "path" by ST_Within(), we can avoid having the duplicated lines in the same path(avoid back-and-forward movements.

Tips to shorten the calculation time:
1) Remember the minimum score, and use it for threshold to drop the iterative records; record having score more than minimum score ever, no chance of getting the lowest score).
*If you already solved part1, that result can be used as a threshold for part2 iteration.
2) Pick the minimum score of the current location and direction in every iteration.
* For part2, we are supposed to get all possible lowest path. There may be multiple minimum record in each group. Don't use Sort and Sample since it picks only one record that might miss the other lowest candidates.

In my dataset, there exist 39 unique paths.

First ,identify the points at branch, and made line objects. I don't recommend to trace next points one by one because it will require way too long calculation process.Recommend to exclude the points at dead-end because the path that reaches to the dead-end have no chance of getting the lowest score.(=no need to trace them)Dead-end point By using these lines, starting from "S", trace the next line that touches with the previous line. In order to record the history, I combined all of line objects that record has ever passed as field name "path" by ST_Combine([Path],[Line]). By comparing the "path" and next target line whether next line is within the "path" by ST_Within(), we can avoid having the duplicated lines in the same path(avoid back-and-forward movements. Tips to shorten the calculation time:1) Remember the minimum score, and use it for threshold to drop the iterative records; record having score more than minimum score ever, no chance of getting the lowest score). *If you already solved part1, that result can be used as a threshold for part2 iteration.2) Pick the minimum score of the current location and direction in every iteration. * For part2, we are supposed to get all possible lowest path. There may be multiple minimum record in each group. Don't use Sort and Sample since it picks only one record that might miss the other lowest candidates. In my dataset, there exist 39 unique paths.

ScottLewis

I do like to trace a path. Part 2 wasn't any harder than Part1 since you already have the target number.

Assorted notes:

Spoiler

My method for these is usually to step through each possible path and find ways to prune them so the volume doesn't get out of control.
You can almost always prune anything that reverse the previous step.
In this case, you can prune anything where there is another path in the current set that gets to the same space with a lower cost (this is a lighter but less thorough version of CoG's approach.)
Once you have found any solution, you can prune anything with cost greater than that solution, even if the threshold isn't optimal. For some path tracing problems you may need to run under made up limits until you find a single answer so that you can apply this sort of pruning and then remove the limits.

My method for these is usually to step through each possible path and find ways to prune them so the volume doesn't get out of control.You can almost always prune anything that reverse the previous step. In this case, you can prune anything where there is another path in the current set that gets to the same space with a lower cost (this is a lighter but less thorough version of CoG's approach.) Once you have found any solution, you can prune anything with cost greater than that solution, even if the threshold isn't optimal. For some path tracing problems you may need to run under made up limits until you find a single answer so that you can apply this sort of pruning and then remove the limits.

PangHC

runtime: 30mins

mmontgomery

D16. More in spoiler

Spoiler

P1: It took me a minute to figure out the score calc properly and my path reduction required me to make my point a string (0002,0001) instead of 2,1 cause when I'd filter it out, it would treat 22,1 and 2,1 the same. Once I did the result ran somewhat quickly. Also I sorted by row, column and min points then took the first record of that point to prune routes
P2: Added a variable for target points to prune out runs over a certain size. Also had to expand the sample done in step 1 to include the first 10 point totals for a given row/column combo since 1 and 5 didn't work.

2 min run time for p2

P1: It took me a minute to figure out the score calc properly and my path reduction required me to make my point a string (0002,0001) instead of 2,1 cause when I'd filter it out, it would treat 22,1 and 2,1 the same. Once I did the result ran somewhat quickly. Also I sorted by row, column and min points then took the first record of that point to prune routesP2: Added a variable for target points to prune out runs over a certain size. Also had to expand the sample done in step 1 to include the first 10 point totals for a given row/column combo since 1 and 5 didn't work.2 min run time for p2

Tokimatsu

Done.

Spoiler

P1 tracking the neighbor from start. P2 tracking the neighbor from end with P1 result.
スクリーンショット 2024-12-17 101458.png

DaisukeTsuchiya

I revised the (WF over and over again, but I finally managed to complete it. WF runs in 8 seconds for P1 and P2.

Spoiler

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.

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.

Hub119

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...

Spoiler