Advent of Code 2024 Day 21
Part 1
Solvable without writing a program?
For a few puzzles in this series, I opted to attempt solving them manually. That means I used some means other than writing a program to discover the correct answer. It's obviously not the intended way. But I loved the puzzle - and lacked the necessary computer science skills - so much that I felt joy nonetheless.
This feels like another one of those puzzles, because:
- I can explain how to come upon the solution
- Doing the work by hand doesn't feel too daunting
- Especially since the sandbox is two arrangements of 10 and 5 symbol groups
This one, unlike yesterday's puzzle, is worth attempting.
Confirming my understanding of how to solve
The instructions play out this example keycode: 029A
First, I must figure out the fewest moves to make the robot press those buttons:
<A^A>^^AvvvA
That's 12 commands. Four activate button presses.
Next, I must figure out the fewest moves to make the next robot execute each of those commands:
v<<A>>^A<A>AvA<^AA>A<vAAA>^A
That's 28 commands. 12 activate button presses.
Lastly, I must figure out the fewest moves to make the third robot execute each of those commands:
<vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A
That's over twice as many commands. 28 activate button presses.
The trick is in locating the correct shortest path:
- There will be multiple for each robot
- But for the more distant robot, one of the closer robot's paths will prove faster to traverse on the directional keypad based on the arrangement of moves
So, while >^> is equally as short as ^>> and >>^, having the next distant robot give instructions to execute each of those will result in varying length paths - the ones with repeat directions require fewer movement commands.
First full walkthrough attempt
I'll use the second example, 980A, and try to manually arrive at the shortest path:
<v<A>>^AAAvA^A<vA<AA>>^AvAA<^A>A<v<A>A>^AAAvA<^A>A<vA>^A<A>A
For the first robot, it's a counter-clockwise rectangle:
^^^A<AvvvA>A
That's 12 commands. I can't think of a shorter path.
Next, the robot that must command the first one to execute each of those 12 commands:
<AAA>Av<<A>>^Av<AAA^>AvA^A
That's 26 commands. 12 activate button presses.
I used the path with the most repeat commands.
Finally, the robot that must command the second one to execute each of those 26 commands:
v<<A>>^AAAvA^Av<A<AA>>^AvAA<^A>Av<A<A>>^AAA<Av>A^Av<A>^A<A>A
That 60 commands. 26 activate button presses.
Below, I'll copy-paste the path from the example, then mine again:
<v<A>>^AAAvA^A<vA<AA>>^AvAA<^A>A<v<A>A>^AAAvA<^A>A<vA>^A<A>A
v<<A>>^AAAvA^Av<A<AA>>^AvAA<^A>Av<A<A>>^AAA<Av>A^Av<A>^A<A>A
Well, they are both the same length. And largely similar.
Second full walkthrough attempt
Now for the code 179A.
First robot's instructions:
^<<A^^A>>AvvvA
14 commands.
Second robot's instructions:
<Av<AA>>^A<AA>AvAA^Av<AAA>^A
14 activation button presses. 29 commands.
Third robot's instructions:
v<<A>>^Av<A<AA>>^AAvAA^<A>Av<<A>>^AAvA^AV<A>^AA<A>AV<A<A>>^AAAvA<^A>A
Comparing my path to the one in the instructions:
Mine:
v<<A>>^Av<A<AA>>^AAvAA^<A>Av<<A>>^AAvA^Av<A>^AA<A>Av<A<A>>^AAAvA<^A>A
Authors:
<v<A>>^A<vA<A>>^AAvAA<^A>A<v<A>>^AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>A
Huh. One less than mine.
Only 28 commands. One less than mine.
How?
I have to walk the author's path backward:
<Av<AA>>^A<AA>AvAA^A<vAAA>^A
28 commands.
Walking that back:
^<<A^^A>>AvvvA
14 commands.
Comparing to mine:
Mine:
^<<A^^A>>AvvvA
Authors:
^<<A^^A>>AvvvA
Identical!
So, what about the 28-command one?
Mine:
<Av<<AA>>^A<AA>AvAA^Av<AAA>^A
Authors:
<Av<AA>>^A<AA>AvAA^A<vAAA>^A
Wow. A typo. I mistakenly added an extra < at the 5th spot.
Well, good news is I got it right. Bad news is I have to be careful when transcribing.
Third full walkthrough
Next code is 456A.
Paths:
^^<<A>A>AvvA
<AAv<AA>>^AvA^AvA^Av<AA>^A
v<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^A<A>Av<A>^A<A>Av<A<A>>^AAvA<^A>A
Comparing mine and the authors:
Mine:
v<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^A<A>Av<A>^A<A>Av<A<A>>^AAvA<^A>A
Authors:
<v<A>>^AA<vA<A>>^AAvAA<^A>A<vA>^A<A>A<vA>^A<A>A<v<A>A>^AAvA<^A>A
Same length! Woohoo!
Fourth full walkthrough
Last example code is 379A.
Paths:
^A^^<<A>>AvvvA
<A>A<AAv<AA>>^ AvAA^Av<AAA>^A
v<<A>>^AvA^Av<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^AA<A>Av<A<A>>^AAAvA<^A>A
Comparing mine and the authors:
Mine:
v<<A>>^AvA^Av<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^AA<A>Av<A<A>>^AAAvA<^A>A
Authors:
<v<A>>^AvA^A<vA<AA>>^AAvA<^A>AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>A
Wow. Mine has four steps extra.
Could that be due to going up then left from 3 to 7, instead of going left then up?
Only one way - for me, lacking sufficient CS skills - to find out!
Paths:
^A<<^^A>>AvvvA
<A>Av<<AA>^AA>AvAA^Av<AAA>^A
v<<A>>^AvA^Av<A<AA>>^AAvA^<A>AAvA^Av<A>^AA<A>Av<A<A>>^AAAvA^<A>A
Comparing mine and the authors:
Mine:
v<<A>>^AvA^Av<A<AA>>^AAvA^<A>AAvA^Av<A>^AA<A>Av<A<A>>^AAAvA^<A>A
Authors:
<v<A>>^AvA^A<vA<AA>>^AAvA<^A>AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>A
Yup, that was it.
Maybe it has to do with putting the ^ and A closer to one another?
I'm not entirely sure. But it seems like a good strategy.
Inspecting my input codes
These are my five codes:
985A
540A
463A
671A
382A
Considering the shortest path based on the strategies I learned from walking through the examples:
- Rectangle
- Tricky
- Similar to
456A - Seems obvious
- Tricky
Hmm. 2 and 5 have me re-thinking walking through all five only to come out wrong.
It's worth a try, right?
First straight-forward code: 985A
Paths:
^^^A<AvAvv>A
<AAA>Av<<A>>^Av<A>^Av<AA>A^A
v<<A>^^AAAvA^Av<A<AA>>^AvAA^<A>Av<A<A>>^AvA^<A>Av<A<A>>^AAvA^A<A>A
^^^A<AvA>vvA
<AAA>Av<<A>>^Av<A>^AvA<AA>^A
v<<A>^^AAAvA^Av<A<AA>>^AvAA^<A>Av<A<A>>^AvA^<A>Av<A^>Av<<A>>^AAvA^<A>A
I walked through two paths, where the only difference was how it goes from the 5 to the A: go right first or last?
Turns out that going right last can save four steps!
Hopefully the shorter of my two paths is one of the shortest paths for that code.
Second straight-forward code: 463A
Paths:
^^<<A>>AvAvA
<AAv<AA>>^AvAA^Av<A^>Av<A^>A
v<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^AA<A>Av<A<A>>^A<Av>A^Av<A<A>>^A<Av>A^A
<AAv<AA>>^AvAA^A<vA^>A<vA^>A
v<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^AA<A>Av<<A>A>^A<Av>A^Av<<A>A>^A<Av>A^A
I walked two paths again, one being a very minor variant of the other. Both paths ended up being the same length.
Third code: 671A
Paths:
^^A <<^A vvA >>vA
<AA>A v<<AA>^A>A v<AA^>A vAA<A^>A
v<<A>>^AAvA^A v<A<AA>>^AAvA^<A>AvA^A v<A<A>>^AA<Av>A^A v<A^>AAv<<A>>^A<Av>A^A
^<<A
<Av<AA>>^A
v<<A>>^Av<A<A>>^AAvAA^<A>A
Again, I explored one path and one variant of part of that path.
The pattern is emerging: avoid <A as much as possible. That makes sense.
Fourth code: 382A
Paths:
^A <^^A vvA v>A
<A>A v<<A>^AA>A <vAA^>A <vA>A^A
v<<A>>^AvA^A v<A<AA>>^AvA^<A>AAvA^A v<<A>A>^AA<Av>A^A v<<A>A>^AvA^A<A>A
^^<A >vA
<AAv<A>>^A vA<A>^A
v<<A>>^AAv<A<A>>^AvAA^<A>A v<<A>A>^AA<Av>A^A v<A>^Av<<A>>^AVA^<A>A
This time I explored two variants of a single path. Each variant was longer because it featured an extra <A.
Fifth code: 540A
Paths:
<^^A <A >vvA >A
v<<A>^AA>A v<<A>>^A vA<AA>^A vA^A
v<A<AA>>^AvA^<A>AAvA^A v<A<AA>>^AvAA^<A>A v<A>^Av<<A>>^AAvA^<A>A v<A^>A<A>A
I feel good about that path. No need to explore variants.
I think that's all of them.
Collecting shortest paths
All paths:
985A
v<<A>^^AAAvA^Av<A<AA>>^AvAA^<A>Av<A<A>>^AvA^<A>Av<A<A>>^AAvA^A<A>A
66
540A
v<A<AA>>^AvA^<A>AAvA^Av<A<AA>>^AvAA^<A>Av<A>^Av<<A>>^AAvA^<A>Av<A^>A<A>A
72
463A
v<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^AA<A>Av<A<A>>^A<Av>A^Av<A<A>>^A<Av>A^A
70
671A
v<<A>>^AAvA^Av<A<AA>>^AAvA^<A>AvA^Av<A<A>>^AA<Av>A^Av<A^>AAv<<A>>^A<Av>A^A
74
382A
v<<A>>^AvA^Av<A<AA>>^AvA^<A>AAvA^Av<<A>A>^AA<Av>A^Av<<A>A>^AvA^A<A>A
68
And now for my equation:
985*66 65010
+ 540*72 38880
+ 463*70 32410
+ 671*74 49654
+ 382*68 25976
--------
211930
To be clear, even with my thorough walkthroughs, I still don't expect this to be the correct answer.
Why not? Because I don't think I'm that lucky. And I probably mis-typed something.
But, here goes nothing...
Submitting my answer
...
OH MY GOODNESS, IT IS THE CORRECT ANSWER!!!
Wow. I was not expecting that.
Incredible!
Well, Part 2 is likely to require a performant algorithm.
Let's see what twist it brings.
Part 2
Yup, more robots
I'm not about to walk through over 20 paths for each code by hand.
Part 1 was a fun manual test.
But my journey today stops here.
I am beyond happy to have a hard-earned - though not programmatic - gold star.
Top comments (0)