Advent of Code 2024 Day 21 (BaseA Style)

[AlteryxCommunityTeam]

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

[ntakeda]

Solved, but not fully understood.

Spoiler

My workflow contains leftover garbage from earlier considerations, so it's not a good reference.

However, here’s a simple explanation of the content:

Part 1: Even if a test works, it may differ in production.
Multiple ways to reach the destination need to be considered.
For example, moving from 1 to 9 can be done using both ">>^^" and "^^>>".

Part 2: There are also multiple ways to use the directional keys, so I attempted to calculate several possibilities.
However, simply moving in the priority order  < → ^ → v→ > provided the correct answer (possibly because it returns to A at each turn?).
Since the number of records becomes enormous over 24 iterations, I used an aggregation tool.

[mmontgomery]

Day 21. More in spoiler

Spoiler

This was a doozy, for sure.
P1: Did an iterative macro for numeric mapping and didn't prune routes, fortunately 12 iterations of brute force gave me what I needed. The real key was creating a lookup table for the A=>v=>etc and the various steps involved going from A to a given directional key. That lookup table gave me what I needed to close out P1, which I put in a batch macro to run one case at a time
P2: I was in good shape to do this based on P1. I ended up grouping by recordID (the value of a given shortest run from numeric mapping macro), prior step, next step, and summed counts. I joined it to the same lookup table to get the relationships.

[Hub119]

I lost count of how many times I had to go back to the drawing board on this one... built out a solution to part 1 quickly enough (albeit with multiple macros)... then built the robot part of it into its own macro that would allow me to iterate through 25 robots instead of just 2.  Unfortunately, my dataset blew up as soon as I passed to Robot #3 so that approach didn't work at all.  SO... went back to the start (after my initial door code sequences had been determined) and built out a key of every possible sequential move order from one button to the next.  Using that I was able to finally build out a working iterative macro for part 2 that I could limit outputs with summary counts of move combinations (since that available list was finite).

[CoG]

Glad to be able to add my solution to this panel of pros. I understood about 90% of the optimization early on, but kept getting the wrong answer due a key insight that I was missing. I devoted a lot of effort to this problem and it frustrated me to no end that I could not get it. Now that I understand all the main components of the problem, I feel a great sense of accomplishment. I will include the 3 key insights that I had that helped me solve the problem as 3 hints below if it helps anybody else (ordered by significance)

Hints:

Spoiler

1.

Spoiler

In dealing with generating shortest paths, you should never intermix differing directions of movement (e.g. "<^<"). Doing so, forces us to make more moves on the next robot (iteration) to generate that pattern. Instead, all similar directions should be grouped into single contiguous units (e.g. "<<^" or "^<<"). This can be quickly demonstrated:
"<^<"  ==> "v<<A>^Av<A" (Len = 10)
"^<<"  ==> "<Av<AA" (Len = 6)

2.

Spoiler

The problem only asks for the Length of the shortest path (not the shortest path itself). We can thus avoid trying to construct such a path and focus only on ways to monitor the length of such a path. This can be done in several ways: @mmontgomery did by tracking connected pairs of moves (i.e. how many "<A", or "<^", etc. appear in the path string). In my approach, I realized that every path group ending in "A" formed a complete cycle that would start and stop on the 'A' of the next robot, which means that is was independent of all other cycles. Thus, the shortest path, S( P , n ), for a collection of such path groups, P, after n-iterations is the sum of the shortest paths for each path group after n-iterations.
Example: Let P = "<A<^Av<<A>>A", then P1 = "<A", ..., P4 = ">>A" and 
S( P ) = S( P1 ) + S( P2 ) + S( P3 ) + S( P4 )

This allows us to track only the count of those groups for each iteration.

3.

Spoiler

This for me was the key missing insight that allowed me solve the rest of the problem: Due to the problems constraints an optimal order exists for ordering of the direction, namely, it is better to go '<' before going '^'/'v', and it is better to go '^'/'v' before going '>'. With this insight you no longer have to deal with the complexities of the problem because there exists a single optimal path that can be generated for every path group (defined above in hint 2). This single optimal path is not only the shortest for the current iteration, but will always generate the shortest path for every successive iteration.

Solution:

Spoiler

Main Workflow:


Best Next Step Macro:


Simulate n-Robots Macro:

[DaisukeTsuchiya]

I think Day21P2 was the most challenging one in 2024 AoC.

Spoiler

As for P1, it took me an hour and a half just to correctly understand the problem description.

At first, I thought I could solve it without using a loop, but since some space for buttons on the passcode and remote control were missing, relying solely on coordinate differences didn’t work in some cases. I ended up treating it like a maze, exploring all possible routes from each button to create the necessary code.

Initially, the process took over a minute, but by eliminating the zigzag routes on the remote, it was reduced to just a few seconds. However, when the number of remotes increased, the data grew exponentially, making it unmanageable. There must have been some kind of rule, but I couldn’t figure it out.

For P2, I referred to @CoG  ’s spoiler. The solution involved breaking the task into blocks of "xxA", processing them, grouping the results, and counting them. The key was narrowing down the paths to a specific subset; once the paths were reduced to a single option, the process became significantly simpler. I’m deeply grateful to @CoG  for this insight.

After breaking it into "xxA" blocks, the next step was to transform it into an "AxxA" format and then calculate the next level. However, I got stuck for a long time due to mistakes in the grouping process at this stage. 

I'm really exhausted, but I'm truly happy to have solved this problem.

 

[gawa]

Day21 was the last puzzle for me. Now I earned 50 stars!

I've struggled with Day21 for way too long. My WF looks so messy  but "End justifies means".

Spoiler

[AkimasaKajitani]

Solved!

Spoiler

Part 1 would not finish if I tried all combinations. Therefore, I had to reduce the number of patterns. I was able to complete it by first removing the patterns of ">^>" and "<v<" from the cursor keys (this remove had a huge effect).

However, Part 2 required optimization because it had too much data amount. In the end, I verified which patterns could be reduced using three robots, and deleted all patterns that could be deleted (ultimately, a unique pattern was determined).

However, this still did not work for 25 robots. Since all A keys were basically passed through, the pattern was consolidated into 21 patterns when divided by A to A. All that remained was to find out how many times this pattern appeared. In grouping each trial of the macro,
I added up the counts, I was able to repeat it with a very small number of records. In the end, it was optimized too much, so Part 1 and 2 finished in 0.8 seconds combined.

Part 1:

Part 1+Part 2:

Finally, what happened to the other missing person in part2?

Spoiler

The button was pressed 441.6 billion times. Even if you pressed the button once per second, it would take 420,000 years.

[Tokimatsu]

Done.

Spoiler

There are 17 different Direction keypad seaquences, all ending in A. If the A delimiter combination is the same, the length of the string will be the same when the keypad seaquence is expanded.
At first, I tried to expand the A delimiter combination data to row direction. But debugging is very complicated about it in solving part 2.
Then I tried to find the only one expansion for each A delimiter combination.

 

[PangHC]

it tooks lot of time to debug. go through lot of methods, 5 macros built and deleted.

Spoiler

part1 and part2:

1. use start_x - end_x to get number of "<"/">" and y for "^"/"v"
2. then merge the "<>" and "^v" group, optimise by is "<^v>" i.e. "<" first and ">" last. (it based on observation)
3. remove it by hardcode all the not possible move. eg: vvv> for 7 to 0, and reverse the path to ">vvv"

groupby + count is the keys. because sorting not important here. it like day 6? the lantern fish thingy. it just need to 1 extra group by recordid. to calculate later.