--- Day 21: Keypad Conundrum ---
As you teleport onto Santa's Reindeer-class starship, The Historians begin to panic: someone from their search party is missing. A quick life-form scan by the ship's computer reveals that when the missing Historian teleported, he arrived in another part of the ship.
The door to that area is locked, but the computer can't open it; it can only be opened by physically typing the door codes (your puzzle input) on the numeric keypad on the door.
The numeric keypad has four rows of buttons:
789,456,123, and finally an empty gap followed by0A. Visually, they are arranged like this:+---+---+---+ | 7 | 8 | 9 | +---+---+---+ | 4 | 5 | 6 | +---+---+---+ | 1 | 2 | 3 | +---+---+---+ | 0 | A | +---+---+Unfortunately, the area outside the door is currently depressurized and nobody can go near the door. A robot needs to be sent instead.
The robot has no problem navigating the ship and finding the numeric keypad, but it's not designed for button pushing: it can't be told to push a specific button directly. Instead, it has a robotic arm that can be controlled remotely via a directional keypad.
The directional keypad has two rows of buttons: a gap /
^(up) /A(activate) on the first row and<(left) /v(down) />(right) on the second row. Visually, they are arranged like this:+---+---+ | ^ | A | +---+---+---+ | < | v | > | +---+---+---+When the robot arrives at the numeric keypad, its robotic arm is pointed at the
Abutton in the bottom right corner. After that, this directional keypad remote control must be used to maneuver the robotic arm: the up / down / left / right buttons cause it to move its arm one button in that direction, and theAbutton causes the robot to briefly move forward, pressing the button being aimed at by the robotic arm.For example, to make the robot type
029Aon the numeric keypad, one sequence of inputs on the directional keypad you could use is:
<to move the arm fromA(its initial position) to0.Ato push the0button.^Ato move the arm to the2button and push it.>^^Ato move the arm to the9button and push it.vvvAto move the arm to theAbutton and push it.In total, there are three shortest possible sequences of button presses on this directional keypad that would cause the robot to type
029A:<A^A>^^AvvvA,<A^A^>^AvvvA, and<A^A^^>AvvvA.Unfortunately, the area containing this directional keypad remote control is currently experiencing high levels of radiation and nobody can go near it. A robot needs to be sent instead.
When the robot arrives at the directional keypad, its robot arm is pointed at the
Abutton in the upper right corner. After that, a second, different directional keypad remote control is used to control this robot (in the same way as the first robot, except that this one is typing on a directional keypad instead of a numeric keypad).There are multiple shortest possible sequences of directional keypad button presses that would cause this robot to tell the first robot to type
029Aon the door. One such sequence isv<<A>>^A<A>AvA<^AA>A<vAAA>^A.Unfortunately, the area containing this second directional keypad remote control is currently
-40degrees! Another robot will need to be sent to type on that directional keypad, too.There are many shortest possible sequences of directional keypad button presses that would cause this robot to tell the second robot to tell the first robot to eventually type
029Aon the door. One such sequence is<vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A.Unfortunately, the area containing this third directional keypad remote control is currently full of Historians, so no robots can find a clear path there. Instead, you will have to type this sequence yourself.
Were you to choose this sequence of button presses, here are all of the buttons that would be pressed on your directional keypad, the two robots' directional keypads, and the numeric keypad:
<vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A v<<A>>^A<A>AvA<^AA>A<vAAA>^A <A^A>^^AvvvA 029AIn summary, there are the following keypads:
- One directional keypad that you are using.
- Two directional keypads that robots are using.
- One numeric keypad (on a door) that a robot is using.
It is important to remember that these robots are not designed for button pushing. In particular, if a robot arm is ever aimed at a gap where no button is present on the keypad, even for an instant, the robot will panic unrecoverably. So, don't do that. All robots will initially aim at the keypad's
Akey, wherever it is.To unlock the door, five codes will need to be typed on its numeric keypad. For example:
029A 980A 179A 456A 379AFor each of these, here is a shortest sequence of button presses you could type to cause the desired code to be typed on the numeric keypad:
029A: <vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A 980A: <v<A>>^AAAvA^A<vA<AA>>^AvAA<^A>A<v<A>A>^AAAvA<^A>A<vA>^A<A>A 179A: <v<A>>^A<vA<A>>^AAvAA<^A>A<v<A>>^AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>A 456A: <v<A>>^AA<vA<A>>^AAvAA<^A>A<vA>^A<A>A<vA>^A<A>A<v<A>A>^AAvA<^A>A 379A: <v<A>>^AvA^A<vA<AA>>^AAvA<^A>AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>AThe Historians are getting nervous; the ship computer doesn't remember whether the missing Historian is trapped in the area containing a giant electromagnet or molten lava. You'll need to make sure that for each of the five codes, you find the shortest sequence of button presses necessary.
The complexity of a single code (like
029A) is equal to the result of multiplying these two values:
- The length of the shortest sequence of button presses you need to type on your directional keypad in order to cause the code to be typed on the numeric keypad; for
029A, this would be68.- The numeric part of the code (ignoring leading zeroes); for
029A, this would be29.In the above example, complexity of the five codes can be found by calculating
68 * 29,60 * 980,68 * 179,64 * 456, and64 * 379. Adding these together produces126384.Find the fewest number of button presses you'll need to perform in order to cause the robot in front of the door to type each code. What is the sum of the complexities of the five codes on your list?
First, read the codes, and store their numeric values.
show nums: "J"$-1_/: 0N!codes: read0 `21.txt
("029A";"980A";"179A";"456A";"379A")
29 980 179 456 379
Now, let's define some variables, for the number pad, and direction pad.
show npad:("789";"456";"123";" 0A")
"789"
"456"
"123"
" 0A"
show dpad:(" ^A"; "<v>")
" ^A"
""
Now, define a function that finds an index of a value in a 2d array.
find:{first raze til[count x]{x,/:where y}'x=y}
We can see this works as expected as so:
npad find/: "3872" 2 2 0 1 0 0 2 1
We need to path find from one location to the other.
This path should be represented using arrows, and it can go any direction, other than crossing the blank square.
Let's build this step by step. We can start by finding the indices of the two locations:
{x find/: (y;z)}[npad; "3"; "4"]
2 2
1 0
Now, we want to construct all the valid paths from the start to the end.
Start by defining a function that will take a start and end value, and simply return all paths of the correct length starting at the start value.
Efficiency isn't so important here, as the maximum path length is small.
First, define a dictionary of directions.
show d:(-1 0;0 1;1 0;0 -1)!"^>v<" -1 0 | ^ 0 1 | > 1 0 | v 0 -1| <
Now, we can write a function that will extend a given path by all 4 directions. The -1# is so the last value is already enlisted.
{x,/:key[d]+/:\:-1#x} (2 3;4 5)
2 3 4 5 3 5
2 3 4 5 4 6
2 3 4 5 5 5
2 3 4 5 4 4
We want to apply this to each path in a list of paths, and raze the results. The initial value is a (1 item) list of (1 item) paths.
4{raze{x,/:key[d]+/:\:-1#x}each x}/2 enlist/ 5 5
5 5 4 5 3 5 2 5 1 5
5 5 4 5 3 5 2 5 2 6
5 5 4 5 3 5 2 5 3 5
5 5 4 5 3 5 2 5 2 4
5 5 4 5 3 5 3 6 2 6
5 5 4 5 3 5 3 6 3 7
5 5 4 5 3 5 3 6 4 6
5 5 4 5 3 5 3 6 3 5
5 5 4 5 3 5 4 5 3 5
5 5 4 5 3 5 4 5 4 6
5 5 4 5 3 5 4 5 5 5
5 5 4 5 3 5 4 5 4 4
5 5 4 5 3 5 3 4 2 4
5 5 4 5 3 5 3 4 3 5
5 5 4 5 3 5 3 4 4 4
5 5 4 5 3 5 3 4 3 3
5 5 4 5 4 6 3 6 2 6
5 5 4 5 4 6 3 6 3 7
5 5 4 5 4 6 3 6 4 6
5 5 4 5 4 6 3 6 3 5
5 5 4 5 4 6 4 7 3 7
5 5 4 5 4 6 4 7 4 8
The number of times we need to expand our paths is equal to the manhattan distance.
Define a function to return all paths, that will be filtered after.
ap: {(sum abs x-y){raze{x,/:key[d]+/:\:-1#x}each x}/2 enlist/x}
Now, we want to filter this, requiring the last value to be the end, and none of the values to pass through spaces.
Define a function to return these new valid paths.
vp: {p where (not" "in/:x ./:/:p)&e~/:last each p:ap . (s;e):x find/:(y;z)}
Now we have a list of valid paths, they just need to be converted to arrows. We find the differences, and use the dictionary to lookup the correct direction.
paths: {{d 1_deltas x} each vp[x;y;z]}
Let's test it by seeing the paths from two different values.
paths[npad; "3"; "4"] "^<<" "<^<" "<<^"
We can see this goes left twice, and up once, as desired.
Also, let's check for another case, it doesn't go through the blank space.
paths[npad; "A"; "7"] "^^^<<" "^^<^<" "^^<<^" "^<^^<" "^<^<^" "^<<^^" "<^^^<" "<^^<^" "<^<^^"
We can see it goes the correct distances in both directions, but never starts with a left twice. This would end up over the gap, which isn't allowed.
Now we have this function, we can work on converting a list of values to instructions. For a given code, we always start with "A", and we can use Each Prior to find the correct path between two values.
"A" {paths[npad;y;x]}': "029A"
,,"<"
,,"^"
("^^>";"^>^";">^^")
,"vvv"
We need to append an A to every path, as it is always pressed at the end. To find all possible instruction sequences, we take these lists, and find all combinations of concatenations.
{raze x,/:\:y}over "A" {paths[npad;y;x],\:"A"}': "029A"
"AvvvA"
"^AvvvA"
"^^AvvvA"
Let's define this as a function, and pass the pad we're using as an argument.
ins:{{raze x,/:\:y} over "A"{paths[z;y;x],\:"A"}[;;x]':y}
Now, we could use this to solve part 1, or we can try and optimise.
First of all, one useful thing would be to consider each "chunk" of instructions ending in an "A".
Let's write a function to split a string into its constituent chunks.
chunks:{(0,where "A"=prev x)_x}; show chunks "0123A456AA7A"
"0123A"
"456A"
,"A"
"7A"
We want to find the optimal (minimal) length after two "encodings" using the dpad. We can consider the optimal encoding for each chunk separately, and then add them.
Let's write a function that takes the number of steps as x and the string we want to encode as y. If the number of steps is 0, return the length of y.
Otherwise, for each possible instruction sequence, we split it into chunks, and find the sum of the optimal values with (x-1) steps. The result is then the minimum of these.
opt:{$[x~0; count y; min (sum opt[x-1] each chunks @) each ins[dpad; y]]}
Let's find the number pad encodings of our codes, and then the optimal double encoding lengths of them.
show lens: {2 opt/: ins[npad; x]} each codes
68 76 68
,60
68 76
64 78 66 72 74
68 82 70 76 78 64
The result is then the minimum of each, multiplied by our numeric values.
sum nums*min each lens 126384
--- Part Two ---
Just as the missing Historian is released, The Historians realize that a second member of their search party has also been missing this entire time!
A quick life-form scan reveals the Historian is also trapped in a locked area of the ship. Due to a variety of hazards, robots are once again dispatched, forming another chain of remote control keypads managing robotic-arm-wielding robots.
This time, many more robots are involved. In summary, there are the following keypads:
- One directional keypad that you are using.
- 25 directional keypads that robots are using.
- One numeric keypad (on a door) that a robot is using.
The keypads form a chain, just like before: your directional keypad controls a robot which is typing on a directional keypad which controls a robot which is typing on a directional keypad... and so on, ending with the robot which is typing on the numeric keypad.
The door codes are the same this time around; only the number of robots and directional keypads has changed.
Find the fewest number of button presses you'll need to perform in order to cause the robot in front of the door to type each code. What is the sum of the complexities of the five codes on your list?
Now we want to do this 25 times.
As it is, our function would be too slow, but we can introduce caching to avoid recomputing values.
We define a new function, with the same name, so recursion works. We also pass in the old function, so we can use it to compute new values. This is very similar to the cache decorator in Python.
We need to define an empty cache as well. Here, for ease of use, we cast the arguments to a symbol.
cache:(1#`)!1#0; opt:{$[not null c: cache S: `$string[x],y; c; cache[S]: z[x;y]]}[;;opt]
Now our answer for part 2 is:
sum nums*{min 25 opt/: ins[npad;x]} each codes
154115708116294
nums: "J"$-1_/: codes: read0 `21.txt
npad:("789";"456";"123";" 0A")
dpad:(" ^A"; "")
find:{first raze til[count x]{x,/:where y}'x=y}
d:(-1 0;0 1;1 0;0 -1)!"^>v<"
ap: {(sum abs x-y){raze{x,/:key[d]+/:\:-1#x}each x}/2 enlist/x}
vp: {p where (not" "in/:x ./:/:p)&e~/:last each p:ap . (s;e):x find/:(y;z)}
paths: {{d 1_deltas x} each vp[x;y;z]}
ins:{{raze x,/:\:y} over "A"{paths[z;y;x],\:"A"}[;;x]':y}
chunks:{(0,where "A"=prev x)_x}
opt:{$[x~0; count y; min (sum opt[x-1] each chunks @) each ins[dpad; y]]}
cache:(1#`)!1#0; opt:{$[not null c: cache S: `$string[x],y; c; cache[S]: z[x;y]]}[;;opt]
sum nums*{min 2 opt/: ins[npad;x]} each codes
sum nums*{min 25 opt/: ins[npad;x]} each codes