General Discussions
Discuss any topics that are not product-specific here.
This problem was tough. I spent a lot of time thinking about good ways to simplify this problem prior to running my search, but the constraints seemed to ruin everything that I wanted to try although the problem itself may not have been super well suited to the methods I was initially thinking through. I ended up taking the iterative macro approach (I'd be truly surprised if someone can do this without one). I found that Part 2 wasn't actually that much harder than Part 1 today. My method was basically the same (I just needed to add a couple tools to account for the additional constraint). Both ran in ~5 minutes
Algorithm Hint 1 (based off of my approach):
Spoiler
Brute forcing a problem like this will cause an explosion of possible routes. How can you prune your search to keep only valuable information while minimizing wasteful calculations?
Things to Think (T2T) about:
1. Searching is a good way to solve this problem, but you need to be smart about it
2. What information do you need to track iteratively in order to ensure that you are pruning (i.e. stopping unnecessary searches ASAP) properly?
3. How do handle the case when a branch you're searching overlaps a branch you've previously pruned?
Things to Think (T2T) about:
1. Searching is a good way to solve this problem, but you need to be smart about it
2. What information do you need to track iteratively in order to ensure that you are pruning (i.e. stopping unnecessary searches ASAP) properly?
3. How do handle the case when a branch you're searching overlaps a branch you've previously pruned?
Algorithm Hint 2:
Spoiler
The fields that I tracked in my iterative macro were: Active_Status, Row, Column, Movement_Direction, Remaining_Steps (i.e. how many steps can be taken in the same direction before a turn would be required), and Total_Heat_Loss
Things to Think (T2T) about:
1. How can these fields be used to track progress, prune unnecessary searches, and progress toward solution?
2. In which cases should a cell that was inactivated be reactivated? How can you do this?
Things to Think (T2T) about:
1. How can these fields be used to track progress, prune unnecessary searches, and progress toward solution?
2. In which cases should a cell that was inactivated be reactivated? How can you do this?
Workflow Screenshots:
Spoiler
Main:
Crucible (Iterative Macro for Part 1):
Ultra-Crucible (Iterative Macro for Part 2):
Notice how similar Macros are for parts 1 & 2.
Crucible (Iterative Macro for Part 1):
Ultra-Crucible (Iterative Macro for Part 2):
Notice how similar Macros are for parts 1 & 2.
After the uncountable attempt, finally solved it. I write the logic I applied in the spoiler. I apologize for my wording is not so good as I'm not English speaker...and not good at thinking clever logic.
Spoiler
1) Use iterative macro, and move one step per one iteration, following the rule described in question
2) Record A)X-Y coordinate of the current location, B) how many straight steps so far &its direction (part1:this is 1 to3), and C) running total of heat loss.
*For each X-Y coordinates, from left 1 straight step, 2 straight step, 3 straight step, from right 1 strait step, 2 straight step...total 12 unique pattern exist
3) Within the all of history record in 2), group by "current location" and "straight steps so far", and find the records having the minimum heat loss value within that group
Repeating these process until X-Y coordinate reaches the goal.
Some Tips:
A) You can calculate any dummy route(from start to end) outside of macro in advance, and get the heat loss value of that route. It is sure that your correct answer never exceeds that value, thereby that value can be used as the threshold to drop the unnecessary records having larger heat loss in iterative macro.(you can manually configure the threshold in Filter tool, like I did.)
B) You can drop record having "X+Y <[iteration_number]-50"
This is not theoretical one, but worked for my dataset to make iteration faster, maintaining the correct answer. This logic is aiming to drop the records that are deemed "no chance". For example, if iteration number is almost 200 but they still search around (X,Y)=(10,10), that search would be no worth(too far from the other candidates searching near the goal). For that purpose, I set "50" without specific reason, but you can adjust it by yourself. (Larger value will be safer so as not to miss the correct answer, but will allow more record iteration and consequently longer execution time. Vice versa.)
WF overview
2) Record A)X-Y coordinate of the current location, B) how many straight steps so far &its direction (part1:this is 1 to3), and C) running total of heat loss.
*For each X-Y coordinates, from left 1 straight step, 2 straight step, 3 straight step, from right 1 strait step, 2 straight step...total 12 unique pattern exist
3) Within the all of history record in 2), group by "current location" and "straight steps so far", and find the records having the minimum heat loss value within that group
Repeating these process until X-Y coordinate reaches the goal.
Some Tips:
A) You can calculate any dummy route(from start to end) outside of macro in advance, and get the heat loss value of that route. It is sure that your correct answer never exceeds that value, thereby that value can be used as the threshold to drop the unnecessary records having larger heat loss in iterative macro.(you can manually configure the threshold in Filter tool, like I did.)
B) You can drop record having "X+Y <[iteration_number]-50"
This is not theoretical one, but worked for my dataset to make iteration faster, maintaining the correct answer. This logic is aiming to drop the records that are deemed "no chance". For example, if iteration number is almost 200 but they still search around (X,Y)=(10,10), that search would be no worth(too far from the other candidates searching near the goal). For that purpose, I set "50" without specific reason, but you can adjust it by yourself. (Larger value will be safer so as not to miss the correct answer, but will allow more record iteration and consequently longer execution time. Vice versa.)
WF overview
This is so tough. I spent long time for debugging and got the answer finally.
Spoiler
I got some hint from @gawa and @Tokimatsu . Thank you so much.
I spent more time for P2 debugging beause start point was set as "S" wrongly.
My WF runs in 10 minitues for P1 and P2.
<WF>
<P1 Macro>
<P2 Macro>
I spent more time for P2 debugging beause start point was set as "S" wrongly.
My WF runs in 10 minitues for P1 and P2.
<WF>
<P1 Macro>
<P2 Macro>
Oh man, this was a learning experience! P1 and P2 logic in the spoiler.
Spoiler
Figuring out P1 took a long time primarily around the idea of pruning. Brute forcing all combos will lead to a disaster, so getting rid of the *likely* unnecessary branches took a ton of back and forth in terms of process and execution.
Ultimately I went with using the current point, direction count, and next direction as part of my sample grouping to eliminate *unlikely* branches.
I had a lot of wrong guesses but was able to use that logic to remove routes over a certain path length.
The P2 macro is nearly identical to P1 except in the order in which removes branches (upstream in P2 vs downstream in P1).
It took an hour and a half to run both parts. This was the final tradeoff between not removing possibly correct branches while trying to eliminate a lot of known wrong branches. The art of this problem led me to various answers depending on how I tweaked my parameters.
I'm just glad it's done now and I got the two stars!
Ultimately I went with using the current point, direction count, and next direction as part of my sample grouping to eliminate *unlikely* branches.
I had a lot of wrong guesses but was able to use that logic to remove routes over a certain path length.
The P2 macro is nearly identical to P1 except in the order in which removes branches (upstream in P2 vs downstream in P1).
It took an hour and a half to run both parts. This was the final tradeoff between not removing possibly correct branches while trying to eliminate a lot of known wrong branches. The art of this problem led me to various answers depending on how I tweaked my parameters.
I'm just glad it's done now and I got the two stars!
run both in 4mins~
Spoiler
1. create a path list, (to cut if visit before)
2. unique by new_x, new_y and number of repeat in direction. (to keep only the min step if visit to same location)
3. create a yxdb file to store each cells min. (cut if other path use less point to reach same location)
4. update if route is found, and cut any path the exceed the new min.
4. cut if [distance_with end point] + [new min] >= [new mins] (to cut any route still in the top left corner)
plan to have sample tool to keep in 50k in like last year, but need not with all these cutting path method.
workflow
part1_macro
part2 macro:
2. unique by new_x, new_y and number of repeat in direction. (to keep only the min step if visit to same location)
3. create a yxdb file to store each cells min. (cut if other path use less point to reach same location)
4. update if route is found, and cut any path the exceed the new min.
4. cut if [distance_with end point] + [new min] >= [new mins] (to cut any route still in the top left corner)
plan to have sample tool to keep in 50k in like last year, but need not with all these cutting path method.
workflow
part1_macro
part2 macro:
Finally, I got the two stars on Day17.
I solved the part 1 puzzle using Dijkstra's algorithm. But it was not fast at Alteryx, however it worked.
At the part 2, I used brute force algorithm(BFS). The data for part 2 is too many nodes for Dijkstra's algorithm. So I went to BFS route.
Spoiler
I made many bugs in BFS, so it took so much time for solving.
At part 1, it took 6 hours using Dijkstra's algorithm. If I can use normal Dijkstra's algorithm, it took only five minutes. But at this time, we can only walk up to 3 step in the same direction, so I need many nodes (they contain x, y, direction and steps.), the data is 12 times more than normal Dijkstra.
If I use Dijkstra, the data is 28 times more than normal one. I can't wait more than 12 hours to solve it. So, I went to BFS.
- Route that follows previously walked routes
- Routes with the same arrival point, direction, and number of steps walked this time other than the lowest cost
- Record whose cost is greater than the number of steps walked so far x 4 (cost is assumed to be 4 on average)
- The sum of x and y coordinates is 60 steps less than the number of steps walked
- Set the reference cost to 1000 and use something larger
- The route is different, but surprisingly the same thing
At part 1, it took 6 hours using Dijkstra's algorithm. If I can use normal Dijkstra's algorithm, it took only five minutes. But at this time, we can only walk up to 3 step in the same direction, so I need many nodes (they contain x, y, direction and steps.), the data is 12 times more than normal Dijkstra.
At part 2, it took 4.5 hours using BFS.
If I use Dijkstra, the data is 28 times more than normal one. I can't wait more than 12 hours to solve it. So, I went to BFS.
I dispose the data as follows in this macro.
- Route that follows previously walked routes
- Routes with the same arrival point, direction, and number of steps walked this time other than the lowest cost
- Record whose cost is greater than the number of steps walked so far x 4 (cost is assumed to be 4 on average)
- The sum of x and y coordinates is 60 steps less than the number of steps walked
- Set the reference cost to 1000 and use something larger
- The route is different, but surprisingly the same thing
I hope that the Alteryx iterative macro run more fast.
