General Discussions

AlteryxCommunityTeam · ‎12-19-2024

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

ScottLewis · ‎12-19-2024

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.

Spoiler

This one is a reminder that you don't always have to build a workflow that solves the whole problem end to end.
You can solve pieces of the problem and save your state. This is particularly useful for problems where you have to assemble some portion of the problem space first, such as building the route here.

Building the route is an iterative macro not unlike other recent days. I went with outputting each step as a row rather than trying to track path. That gave me a list of each position on the route along with the step count (if you're being cute, that could be the iteration number.) Note the need to add back the start position to the route output.

From there, applying the 2 pico cheat is just another version of taking a step. The step happens to be exactly two spaces in one direction (the way they build the walls prohibits 1 row 1 column cheats). Try that from every position, check if your destination is also on the path and if so, whether it is more than two steps further along, calculate the savings as destination-(source+2) and you're done. The 2 term is to account for the time spent executing the cheat.

Part two requires a small extra component. Given the larger cheat range you now have mixed row/column options. I used generate rows (-20 to 20) on rows and columns, threw out everything with SUM(ABS) greater than 20 and saved that as the set of all possible cheats.

From there, Part 2 is fundamentally the same as part 1. Instead of moving one 2 pico step, you're moving every distance in the set of all possible cheats. After that, you apply the same is it on the path and is it better logic. The only extra hangup is that the -2 term in the savings calculation becomes -steps. The way I built it this was conveniently the SUM(ABS) of the row and column moves.

This one is a reminder that you don't always have to build a workflow that solves the whole problem end to end. You can solve pieces of the problem and save your state. This is particularly useful for problems where you have to assemble some portion of the problem space first, such as building the route here. Building the route is an iterative macro not unlike other recent days. I went with outputting each step as a row rather than trying to track path. That gave me a list of each position on the route along with the step count (if you're being cute, that could be the iteration number.) Note the need to add back the start position to the route output.From there, applying the 2 pico cheat is just another version of taking a step. The step happens to be exactly two spaces in one direction (the way they build the walls prohibits 1 row 1 column cheats). Try that from every position, check if your destination is also on the path and if so, whether it is more than two steps further along, calculate the savings as destination-(source+2) and you're done. The 2 term is to account for the time spent executing the cheat.Part two requires a small extra component. Given the larger cheat range you now have mixed row/column options. I used generate rows (-20 to 20) on rows and columns, threw out everything with SUM(ABS) greater than 20 and saved that as the set of all possible cheats. From there, Part 2 is fundamentally the same as part 1. Instead of moving one 2 pico step, you're moving every distance in the set of all possible cheats. After that, you apply the same is it on the path and is it better logic. The only extra hangup is that the -2 term in the savings calculation becomes -steps. The way I built it this was conveniently the SUM(ABS) of the row and column moves.

ntakeda · ‎12-19-2024

My solution.

Spoiler

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.

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.

CoG · ‎12-19-2024

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)

Spoiler

Breaking this problem into 2 parts is definitely the best strategy. First, you need to know how long it takes to get to each tile in the maze, for that I used my new favorite Maze solving macro, that I updated to slightly improve efficiency (by removing previously visited positions from the calculation). Once you know this (I cached the workflow up to this point), the rest of this problem is trivial, assuming you don't make any trivial errors in coding things up that you then have to spend 20 minutes debugging.

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):
Maze Navigation.png

Main Workflow:

Breaking this problem into 2 parts is definitely the best strategy. First, you need to know how long it takes to get to each tile in the maze, for that I used my new favorite Maze solving macro, that I updated to slightly improve efficiency (by removing previously visited positions from the calculation). Once you know this (I cached the workflow up to this point), the rest of this problem is trivial, assuming you don't make any trivial errors in coding things up that you then have to spend 20 minutes debugging.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:

dhavaldoshi · ‎12-20-2024

Spoiler

Part1: Didn't do it very different from Day 16, I sacrificed run time for being lazy and wrapped the Day 16 macro with possible iterations on this one, guilty pleasure of just having additional star.
Part2: Obviously same approach wouldn't work because I didn't have patience, realized I was able to calculate min. effort to reach at each point using same Day 16 and kind of moved what I was doing earlier i.e. iterating versions of map to later, and multiplied all path after finding using Generate Rows (+-20)... Run time reduced by 10x. Going back to working for the last Friday of this year.

Part1: Didn't do it very different from Day 16, I sacrificed run time for being lazy and wrapped the Day 16 macro with possible iterations on this one, guilty pleasure of just having additional star.Part2: Obviously same approach wouldn't work because I didn't have patience, realized I was able to calculate min. effort to reach at each point using same Day 16 and kind of moved what I was doing earlier i.e. iterating versions of map to later, and multiplied all path after finding using Generate Rows (+-20)... Run time reduced by 10x. Going back to working for the last Friday of this year.

mmontgomery · ‎12-20-2024

Day 20. More in spoiler

Spoiler

P1: Same macro with some tweaks from D18 and shoutout to @ScottLewis for the approach (p1/p2). It helped me with the final approach vs the very tempting but unrealistic brute force of each combo removed
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
\ Main Workflow.png

P1: Same macro with some tweaks from D18 and shoutout to for the approach (p1/p2). It helped me with the final approach vs the very tempting but unrealistic brute force of each combo removedP2: 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\

Hub119 · ‎12-20-2024

Was happy this turned out not needing any crazy nesting of macros. Repurposed the simple "path finding" macro build that has been used a few times now to build my path and then did some quick generate rows work for both parts 1 and 2. 40*s down, just 10 more to go!

Spoiler

Workflow

Spoiler

Path Macro

AkimasaKajitani · ‎12-21-2024

Solved!

I don't have time to solve them in real time, so I'm rushing to catch up.

Spoiler

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.

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.

DaisukeTsuchiya · ‎12-21-2024

Day20 seems similar to Day18 at the biginning but it is different.

Spoiler

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.

スクリーンショット 2024-12-22 102450.png スクリーンショット 2024-12-22 102517.png スクリーンショット 2024-12-22 102546.png

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