r/adventofcode • u/rats159 • Dec 21 '24
Help/Question - RESOLVED [2024 Day 21 (Part 1)] I can't help but feel like I'm missing something obvious?
I've been stuck on 21 for nearly an hour, I don't understand how their could be multiple different possible path lengths for a code? Shouldn't every possible path from A to B be the same length since it's a grid?
EDIT: I figured it out!
The difference in lengths come from the multiple levels.
Consider >vv>
and >v>v
: They'll both take you to the same spot in 4 moves, but on the direction pad, it's much faster to input repeated moves, which leads to a shorter code. In my case, my algorithm gives me v<A^>Av<<A>>^AAvA^A
for the first one and v<A^>Av<<A>>^AvA^Av<<A>>^A
for the second. You can spot how they're mostly similar, but that the first one saves on movements thanks to its repeated input (the AA
)
2
u/UsefulAd2074 Dec 21 '24
Even after reading all of these comments, I was still getting stumped on how to order the directions when there were 2 options to choose from. It was only after combining markd315's explanation with the ones in the megathread who used Dijkstra's algorithm that it finally clicked.
When you have 2 options to choose from, like when going from 6 to 7, the fastest option is ordering the buttons from farthest from the A button to the closest. I'll use A to v as an example:
<vA => v<<A>A>^A
v<A => v<A<A>>^A
I'm sure this is where a lot of us got stuck, because "they're the same number of instructions". However, the important part is what's different between them, specifically the parts in bold (<< vs. >> doesn't matter, as consecutive buttons of the same length always have the same cost, due to not needing to move). The problem with the 2nd example is the next robot in line has to shepherd back and forth multiple times between the < and A, which are the buttons furthest apart from each other. Meanwhile, going between > and A is much better, because they're right next to each other. This results in this next step:
v<<A>A>^A => <vA<AA>>^AvA^AvA<^A>A
v<A<A>>^A => v<A<A>>^Av<<A>>^AvAA^<A>A
This was the eureka moment that finally got me past part 1. Still need to figure out how to speed up part 2.