Day 21 : Keypad conundrum
Today's challenge was difficult and it's taken me 2 days to have some time to solve, as well as fully understand the logic. Something I've found this year is, I've struggled understanding the intentions of the instructions.
I hope like myself you've learnt something from this challenge and solution. I find each year I take part in Advent of Code, I learn a lot, which is why I like to try different languages or pushing myself out of my comfort zone. I think of Advent of Code as more of a learning / development opportunity where developers should share their knowledge and ideas, rather than treating it as just a competition.
Another stab at Python today and I'm happy with the solution. Something I learn today was; Immutable classes using the @dataclass(frozen=True) annotation on a class declaration.
I created the Location class as a helper class to navigate and update co-ordinates (bit like I did previously with the Point class in some C# solutions.
As someone coming from a strongly typed background of C# / .Net, I tried adding types to my code to help me visualise what I was working with during this complex problem. I'm also used to do this whilst writing TypeScript, so almost second nature.
Today's Problem
**Part One **introduces the problem of navigating and controlling a multiple robots to pass instructions onto the next robot to input codes on a numeric keypad.
Part Two builds on the problem by increasing complexity through a chain of robots and directional keypads, demonstrating the exponential nature of multi-level dependencies.
Walkthrough
As we already know the layout of the directions and keypad, we can build the dictionaries of all the location mappings and directions in which they can move in.
Caching (cache and moves_cache)
cache: Stores previously computed shortest sequences to avoid redundant calculations, improving performance.
moves_cache: Stores all valid move sequences between any two buttons on a keypad, precomputed for quick lookup.
Shortest Length Calculation (shortest_length)
Recursively calculates the shortest sequence of button presses to type a given code.
Handles multi-level chaining of keypads by iterating through the levels (cur_depth) up to the limit (depth_limit).
*Moves Between Positions (moves_between_positions)
*
Computes all valid sequences of movements between two buttons on a keypad, ensuring robots don't panic by pointing at invalid positions (the gaps).
Cache Initialisation (create_cache_moves)
Precomputes valid move sequences for all button pairs on both numeric and directional keypads, saving runtime computation.
The solving functions, then loop through the input calculating its complexity by multiplying the sequence length by the numeric part of the code, and then simply sums up the complexities for all codes as per the requirements of the puzzle.
Permutations
What Does permutations do?
The permutations function in Python (from the itertools module) generates all possible ordered arrangements of a collection of items.
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 containing all the items in the original collection, but in a different order.
Why use permutations and not combinations?
permutations:
Generates all possible ordered arrangements of a collection of items.
The order of the items matters.
whereas,
combinations:
Generates all possible unordered selections of a collection of items.
The order of the items does not matter.
Why is order important in this scenario?
Keypad Navigation: The robot's position on the keypad changes after each move, so the sequence in which moves are performed directly impacts the result.
Valid Moves Check: The function checks the validity of intermediate positions during navigation. Changing the order of moves may lead to an invalid path.
When Would combinations Be Useful Instead?
combinations could be useful in scenarios where the order of moves doesn't matter or you are selecting a subset of moves or buttons without concern for their sequence.
The current use of permutations is necessary because the order of moves matters for keypad navigation. Replacing it with combinations would break the logic of the program. If the task required finding all unique groups of movements or keys regardless of sequence, then combinations would be more appropriate.
The hardest part of the puzzle was thinking of a nice and clean way of keeping track of the depth (inception) level of robot instructions -- took me a bit of time where I could give my full attention to it.
Top comments (0)