Advent of Code Day Keypad Conundrum
Day 21 : Keypad conundrum
GitHub Repo - Solution
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.
The above is the detailed content of Advent of Code Day Keypad Conundrum. For more information, please follow other related articles on the PHP Chinese website!

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics











Python is suitable for data science, web development and automation tasks, while C is suitable for system programming, game development and embedded systems. Python is known for its simplicity and powerful ecosystem, while C is known for its high performance and underlying control capabilities.

You can learn basic programming concepts and skills of Python within 2 hours. 1. Learn variables and data types, 2. Master control flow (conditional statements and loops), 3. Understand the definition and use of functions, 4. Quickly get started with Python programming through simple examples and code snippets.

Python excels in gaming and GUI development. 1) Game development uses Pygame, providing drawing, audio and other functions, which are suitable for creating 2D games. 2) GUI development can choose Tkinter or PyQt. Tkinter is simple and easy to use, PyQt has rich functions and is suitable for professional development.

You can learn the basics of Python within two hours. 1. Learn variables and data types, 2. Master control structures such as if statements and loops, 3. Understand the definition and use of functions. These will help you start writing simple Python programs.

Python is easier to learn and use, while C is more powerful but complex. 1. Python syntax is concise and suitable for beginners. Dynamic typing and automatic memory management make it easy to use, but may cause runtime errors. 2.C provides low-level control and advanced features, suitable for high-performance applications, but has a high learning threshold and requires manual memory and type safety management.

To maximize the efficiency of learning Python in a limited time, you can use Python's datetime, time, and schedule modules. 1. The datetime module is used to record and plan learning time. 2. The time module helps to set study and rest time. 3. The schedule module automatically arranges weekly learning tasks.

Python is widely used in the fields of web development, data science, machine learning, automation and scripting. 1) In web development, Django and Flask frameworks simplify the development process. 2) In the fields of data science and machine learning, NumPy, Pandas, Scikit-learn and TensorFlow libraries provide strong support. 3) In terms of automation and scripting, Python is suitable for tasks such as automated testing and system management.

Python excels in automation, scripting, and task management. 1) Automation: File backup is realized through standard libraries such as os and shutil. 2) Script writing: Use the psutil library to monitor system resources. 3) Task management: Use the schedule library to schedule tasks. Python's ease of use and rich library support makes it the preferred tool in these areas.
