Advent of Code 2024 Day 21 (BaseA Style)
- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
Discussion thread for day 21 of the Advent of Code - https://adventofcode.com/2024/day/21
- Labels:
- Advent of Code
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
Solved, but not fully understood.
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
Day 21. More in spoiler
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
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).
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
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:
"<^<" ==> "v<<A>^Av<A" (Len = 10)
"^<<" ==> "<Av<AA" (Len = 6)
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.
Solution:
Best Next Step Macro:
Simulate n-Robots Macro:
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
I think Day21P2 was the most challenging one in 2024 AoC.
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
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".
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
Solved!
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?
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
Done.
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
it tooks lot of time to debug. go through lot of methods, 5 macros built and deleted.
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.
