Day 21: Keyboard Dilemma
Today’s challenge was difficult and it took me two days to solve it and fully understand the logic. I found this year that I had a hard time understanding the intent of the instructions.
I hope you learned something from this challenge and solution as I did. I find that I learn a lot every year I attend Advent of Code, which is why I love trying different languages or pushing myself outside of my comfort zone. I think Coming of Code is more of a learning/development opportunity where developers should share their knowledge and ideas rather than just treating it as a competition.
Tried Python again today and I’m happy with the solution. What I learned today is; immutable classes use @dataclass(frozen=True) Comments on class declaration.
I created Location category as a helper category to navigate and update coordinates (kind of like I used before Point Category in some C# solutions.
As someone with a strongly typed background in C#/.Net, I’m trying to add types to my code to help me visualize what I’m dealing with in this complex problem. I’m used to doing this when writing TypeScript, so it’s almost second nature.
Today’s question
**Part I** covers the problem of navigating and controlling multiple robots to pass instructions to the next robot to enter codes on a numeric keypad.
part two Solving this problem by adding complexity through a series of robots and directional pads demonstrates the exponential nature of multiple layers of dependencies.
drill
Since we already know the orientation and the layout of the keyboard, we can build a dictionary of all position mappings and the directions in which they can be moved.
Caching (cache and move_cache)
cache: Stores the shortest sequence of previously calculated calculations to avoid redundant calculations and improve performance.
Mobile cache: All valid movement sequences between any two buttons on the keyboard are stored and pre-calculated for quick finding.
Shortest length calculation (shortest_length)
Recursively calculates the shortest button press sequence for entering the given code.
Handle multiple levels of keyboard connections by iterating levels (cur_depth) up to the limit (depth_limit).
*Moves between positions (moves_ Between_positions)
*
Calculate all valid motion sequences between two buttons on the keyboard to ensure that the robot does not panic By pointing to an invalid location (gap).
Cache initialization (create_cache_moves)
Precomputes valid movement sequences for all pairs of buttons on the numeric and directional pads, saving runtime calculations.
The solver function then loops through the input, calculates its complexity by multiplying the length of the sequence by the numeric portion of the code, and then simply sums the complexity of all the code based on the requirements of the puzzle.
arrangement
What does arrangement do?
The permutation function in Python (from the itertools module) produces all possible ordered permutations of a collection of projects.
For example:
from itertools import permutations
items = ['a', 'b', 'c']
list(permutations(items))
This will produce:
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]
Each permutation is a unique sequence that contains all the items in the original set, but in a different order.
Why use permutations instead of combinations?
arrangement:
Generates all possible ordered permutations of a collection of items.
The order of items is important.
However,
combination:
Generates all possible unordered choices for a collection of items.
The order of the projects is not important.
Why does order matter in this case?
Keyboard navigation: The robot’s position on the keyboard changes after each move, so the order in which the moves are performed directly affects the results.
Valid move check: This function checks the validity of the intermediate position during navigation. Changing the move order may result in invalid paths.
When is combination useful?
Combinations can be useful in situations where move order doesn’t matter, or where you select a subset of moves or buttons and don’t care about their order.
Currently using arrangements is necessary because the order of movement is important for keyboard navigation. Replacing it with a combination would break the logic of the program. If the task requires finding all unique actions or sets of keys (regardless of order), then Combination would be more appropriate.
The hardest part of this puzzle was coming up with a nice and clean way to track the deep (initial) level of the bot’s instructions – it took me a while so that I could fully focus on it.