The Mobile Numeric Keypad Challenge is a graph traversal combinatorial issue inspired by the limitations (arrangement and movement) associated with the keypad of a mobile device. Hence, the objective is to determine the total number of distinct sequences of a defined length n of numbers that can be generated by pressing keys on the keypad while adhering strictly to adjacency regulations. The standard layout of a mobile keypad is as follows:
1 2 3
4 5 6
7 8 9
0
In this configuration of the keypad, keys are identified as nodes within a graph, with neighboring keys being those connected by an edge either horizontally, vertically, or diagonally. For instance, key 5 is connected to keys 2, 4, 6, and 8, while key 0 is solely linked to 8. The permissible transitions between keys when constructing sequences adhere to these adjacency connections.
The task involves determining the number of sequences of length n that adhere to the adjacency constraints when starting from any digit on the keypad. For instance, when n=2, valid sequences include 52, 54, 56, 58, and so on. This concept can be illustrated through big O notation. With increasing n, the quantity of feasible sequences grows exponentially, thereby escalating the complexity of the problem.
This problem has practical applications in various fields, including:
- Telecommunications: It analyses keypad-based input patterns, which are critical in creating the user-friendly mobile interfaces.
- Robotics and Graph Traversal: Key and its neighbors make up a graph, and it is a foundational problem for graph theory path algorithms.
- Game Design and Security: Application to pattern recognition, game mechanics, or building secure input system, can understand the possible sequences of movements on a keypad.
Mapping the keypad onto a graph with nodes corresponding to individual keys and edges linking neighboring keys is employed in addressing the Mobile Numeric Keypad Problem. Ultimately, a dynamic programming strategy is adopted to tackle this issue. By considering a sequence of length n, we are able to effectively determine the quantity of interconnected sequences. More precisely, the conditions are established based on the present key and sequence length, leveraging outcomes from preceding sequence lengths to construct solutions for lengthier sequences.
Approach-1: Brute Force Approach (Recursive Backtracking)
The initial solution to the Mobile Numeric Keypad Problem involves a brute force method, which systematically examines every sequence of a specific length, starting from each individual digit on the keypad. This methodology treats the keypad as a graphical structure, with each digit serving as a node, and permissible movements between adjacent keys represented by edges. By employing recursion coupled with backtracking, the algorithm effectively explores this graph, facilitating the generation of all feasible sequences.
We employ a recursive approach that begins with a initial digit, navigates to neighboring valid digits, and shortens the sequence length iteratively. Upon reaching a length of 1, a valid sequence is logged. Through backtracking, the algorithm ensures comprehensive coverage of all potential combinations by backtracking after establishing a path to explore alternative options.
Program:
Let's consider a scenario to demonstrate the Mobile Numeric Keypad issue in C++ by employing the Brute Force method.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Function to display the keypad layout (for clarity)
void displayKeypadLayout() {
cout << "Mobile Numeric Keypad Layout:" << endl;
cout << "1 2 3" << endl;
cout << "4 5 6" << endl;
cout << "7 8 9" << endl;
cout << " 0" << endl;
}
// Function to get the neighbors of a given digit
vector<int> getNeighbors(int digit) {
// Define the neighbors for each digit
vector<vector<int>> neighbors = {
{0, 8}, // Neighbors of 0
{1, 2, 4}, // Neighbors of 1
{2, 1, 3, 5}, // Neighbors of 2
{3, 2, 6}, // Neighbors of 3
{4, 1, 5, 7}, // Neighbors of 4
{5, 2, 4, 6, 8}, // Neighbors of 5
{6, 3, 5, 9}, // Neighbors of 6
{7, 4, 8}, // Neighbors of 7
{8, 5, 7, 9, 0}, // Neighbors of 8
{9, 6, 8} // Neighbors of 9
};
// Return the neighbors for the given digit
return neighbors[digit];
}
// Function to display all neighbors for debugging
void displayNeighbors(int digit) {
vector<int> neighbors = getNeighbors(digit);
cout << "Neighbors of " << digit << ": ";
for (int neighbor : neighbors) {
cout << neighbor << " ";
}
cout << endl;
}
// Function to validate the input length
bool validateInputLength(int n) {
if (n <= 0) {
cout << "Invalid input! Sequence length must be greater than 0." << endl;
return false;
}
return true;
}
// Function to display the current sequence
void displaySequence(const vector<int>& sequence) {
for (int digit : sequence) {
cout << digit;
}
cout << endl;
}
// Recursive function to generate sequences of the given length
int generateSequences(int currentDigit, int remainingLength, vector<int>& currentSequence) {
// Base case: When the sequence length becomes 1
if (remainingLength == 1) {
// Display the sequence for debugging
displaySequence(currentSequence);
return 1;
}
// Get all neighbors of the current digit
vector<int> neighbors = getNeighbors(currentDigit);
// Initialize a count for the total number of sequences
int totalCount = 0;
// Traverse each neighbor and recursively generate sequences
for (int neighbor : neighbors) {
// Add the neighbor to the current sequence
currentSequence.push_back(neighbor);
// Recursive call with updated sequence length
totalCount += generateSequences(neighbor, remainingLength - 1, currentSequence);
// Backtrack: Remove the last digit after processing
currentSequence.pop_back();
}
// Return the total count of sequences from this digit
return totalCount;
}
// Function to calculate the total number of sequences of a given length
int calculateTotalSequences(int n) {
// Validate input
if (!validateInputLength(n)) {
return 0;
}
// Initialize the total count of sequences
int totalCount = 0;
// Traverse all starting digits on the keypad
for (int digit = 0; digit <= 9; ++digit) {
// Debugging: Display neighbors of the current digit
cout << "Processing digit: " << digit << endl;
displayNeighbors(digit);
// Initialize a sequence for tracking the current path
vector<int> currentSequence = {digit};
// Generate sequences starting from the current digit
totalCount += generateSequences(digit, n, currentSequence);
// Debugging: Print progress
cout << "Completed processing for digit " << digit << endl;
}
// Return the total count of sequences
return totalCount;
}
// Function to explain the process in detail (for user clarity)
void explainProcess() {
cout << "This program calculates the total number of sequences of a specified length\n";
cout << "that can be formed on a mobile numeric keypad. The rules are as follows:\n";
cout << "1. You can start from any digit on the keypad.\n";
cout << "2. You can only move to adjacent keys (up, down, left, or right).\n";
cout << "3. The keypad layout and movement constraints are modeled as a graph.\n";
cout << "4. The result is the total number of valid sequences following these rules.\n";
}
// Main function
int main() {
// Display program explanation
explainProcess();
// Display the keypad layout
displayKeypadLayout();
// Input: Get the sequence length from the user
int n;
cout << "Enter the length of the sequences to generate: ";
cin >> n;
// Calculate the total number of sequences
int result = calculateTotalSequences(n);
// Output the result
cout << "Total number of sequences of length " << n << " is: " << result << endl;
// End of program
cout << "Program execution completed. Thank you!" << endl;
return 0;
}
Output:
This program calculates the total number of sequences of a specified length
that can be formed on a mobile numeric keypad. The rules are as follows:
1. You can start from any digit on the keypad.
2. You can only move to adjacent keys (up, down, left, or right).
3. The keypad layout and movement constraints are modeled as a graph.
4. The result is the total number of valid sequences following these rules.
Mobile Numeric Keypad Layout:
1 2 3
4 5 6
7 8 9
0
Enter the length of the sequences to generate: 2
Processing digit: 0
Neighbors of 0: 0 8
00
08
Completed processing for digit 0
Processing digit: 1
Neighbors of 1: 1 2 4
11
12
14
Completed processing for digit 1
Processing digit: 2
Neighbors of 2: 2 1 3 5
22
21
23
25
Completed processing for digit 2
Processing digit: 3
Neighbors of 3: 3 2 6
33
32
36
Completed processing for digit 3
Processing digit: 4
Neighbors of 4: 4 1 5 7
44
41
45
47
Completed processing for digit 4
Processing digit: 5
Neighbors of 5: 5 2 4 6 8
55
52
54
56
58
Completed processing for digit 5
Processing digit: 6
Neighbors of 6: 6 3 5 9
66
63
65
69
Completed processing for digit 6
Processing digit: 7
Neighbors of 7: 7 4 8
77
74
78
Completed processing for digit 7
Processing digit: 8
Neighbors of 8: 8 5 7 9 0
88
85
87
89
80
Completed processing for digit 8
Processing digit: 9
Neighbors of 9: 9 6 8
99
96
98
Completed processing for digit 9
Total number of sequences of length 2 is: 36
Program execution completed. Thank you!
Explanation:
The keypad is considered as a graph, comprising of nodes representing digits and edges representing valid moves between neighboring keys. This technique involves utilizing recursion combined with backtracking to produce all feasible sequences of digits within the specified graph.
Key Components:
- Keypad Representation: The keypad is represented by an adjacency list, which defines the valid neighbors for each digit. For example, the neighbors of digit 5 are 2, 4, 6, 8 and 5 itself.
- Recursive Function: The recursive function generateSequences is the heart of the implementation. It starts with a starting digit and walks all its neighbors, which reduces the sequence length with each 'step'. If the remaining length becomes 1 at thacpp tutorial, we form a valid sequence, and it is counted.
- Backtracking: This approach uses backtracking to ensure that all possible sequences will be explored. The function iteratively explores paths after putting a digit in sequence, and then backtracks does something new by removing the digit at the back and exploring other paths.
- Sequence Tracking: While traversing, we store the current sequence in a vector. This vector serves as an aid for debugging and actually following what is generated in the sequence.
- Input Validation and Visualization: The implementation validates input to ensure the sequence length is greater than zero. It also visualizes the keypad and gives details about each neighbor to help users better understand what is happening.
- Computation: It starts from each digit on the keypad and recursively goes through all valid sequences. All starting digits are summed, and their total number of sequences is accumulated.
Complexity Analysis:
Time Complexity:
The time complexity of the aforementioned brute force method can be evaluated by examining the recursive traversal of all potential sequences originating from each numeral on the keypad:
- Key Insights: Every digit can connect to a maximum of 5 adjacent digits, except for the boundary digits like 1, 3, 7, and 9, which may have fewer connections (ranging from none to 2). The length of the sequence, denoted as n, corresponds to the depth of recursion. The function systematically investigates all valid neighboring digits of the current numeral at each recursion level.
- Recursion Depth: Each digit within a sequence of length n triggers up to 5 recursive invocations. Consequently, every recursive call leads to an additional recursive call at the subsequent level, resulting in an exponential growth in the number of function calls.
Space Complexity:
- Recursion Stack: The maximum amount of space required for the recursion stack (i.e., the recursion depth) is O(n).
- Current Sequence Vector: A vector tracks the current sequence underflow. It also requires O(n) space complexity because it needs to store the digits of the current sequence.
- Final Calculation: Combining the recursion stack and sequence vector, the overall space complexity is O(n).
Approach-2: Breadth-First Search (BFS) Approach
Breadth First Search (BFS) stands as a technique for navigating graphs that methodically follows all feasible paths layer by layer starting from the initial node (or lone number on the keypad) and expanding outward. This approach is applied to produce valid sequences of a particular length n, regardless of the chosen digit as the initial point for addressing the Mobile Numeric Keypad Problem. Every digit (0-9) is depicted as a node within the graph, with the permissible movements between digits forming the edges. The hallmark of BFS lies in its systematic progression through sequences in incremental stages (levels), where each level represents a sequence containing one additional digit compared to the preceding level.
Program:
Let's consider a scenario to demonstrate the Mobile Numeric Keypad dilemma in C++ by implementing the Breadth-First Search (BFS) technique.
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
// Define keypad mapping to its valid neighbors
unordered_map<int, vector<int>> keypad = {
{0, {0, 8}}, // Key 0 has neighbors 0, 8
{1, {1, 2, 4}}, // Key 1 has neighbors 1, 2, 4
{2, {1, 2, 3, 5}}, // Key 2 has neighbors 1, 2, 3, 5
{3, {2, 3, 6}}, // Key 3 has neighbors 2, 3, 6
{4, {1, 4, 5, 7}}, // Key 4 has neighbors 1, 4, 5, 7
{5, {2, 4, 5, 6, 8}}, // Key 5 has neighbors 2, 4, 5, 6, 8
{6, {3, 5, 6, 9}}, // Key 6 has neighbors 3, 5, 6, 9
{7, {4, 7, 8}}, // Key 7 has neighbors 4, 7, 8
{8, {5, 7, 8, 0}}, // Key 8 has neighbors 5, 7, 8, 0
{9, {6, 8, 9}} // Key 9 has neighbors 6, 8, 9
};
// Structure to represent the state of a sequence
struct SequenceState {
int digit; // Current digit in the sequence
int length; // Length of the current sequence
};
// Function to initialize BFS with starting digits and a sequence length
void initializeBFS(queue<SequenceState>& bfsQueue, int sequenceLength) {
for (int i = 0; i < 10; ++i) {
bfsQueue.push({i, 1}); // Start with length 1 for each digit
}
}
// Function to explore neighbors and expand sequences
void exploreNeighbors(queue<SequenceState>& bfsQueue, int currentDigit, int currentLength, int targetLength) {
// If the current sequence reaches the target length, stop exploring further
if (currentLength == targetLength) {
return;
}
// Otherwise, explore all neighbors of the current digit
for (int neighbor : keypad[currentDigit]) {
bfsQueue.push({neighbor, currentLength + 1});
}
}
// Function to count sequences of a given length using BFS
int countSequences(int n) {
// Queue for BFS, stores pairs of (current_digit, current_length)
queue<SequenceState> bfsQueue;
int totalSequences = 0;
// Initialize BFS with sequences of length 1 for each digit
initializeBFS(bfsQueue, n);
// Perform BFS to explore all sequences
while (!bfsQueue.empty()) {
auto [digit, length] = bfsQueue.front();
bfsQueue.pop();
// If the sequence has reached length n, count it
if (length == n) {
totalSequences++;
}
// Otherwise, explore all valid neighbors and add to queue
else {
exploreNeighbors(bfsQueue, digit, length, n);
}
}
return totalSequences;
}
// Function to print the keypad for visualization
void printKeypad() {
cout << "Keypad Layout:" << endl;
cout << "1 2 3" << endl;
cout << "4 5 6" << endl;
cout << "7 8 9" << endl;
cout << " 0" << endl;
}
// Function to validate the input sequence length
bool validateInput(int n) {
if (n <= 0) {
cout << "Error: Sequence length must be greater than 0!" << endl;
return false;
}
return true;
}
// Function to handle user interaction and output
void handleUserInput() {
int n;
cout << "Enter the length of the sequences (positive integer): ";
cin >> n;
// Validate the input length
if (!validateInput(n)) {
return;
}
// Print the keypad layout for visualization
printKeypad();
// Call BFS function to calculate number of valid sequences of length n
int result = countSequences(n);
// Output the result
cout << "Total number of sequences of length " << n << ": " << result << endl;
}
int main() {
// Start the program by handling user input
handleUserInput();
return 0;
}
Output:
Enter the length of the sequences (positive integer): 3
Keypad Layout:
1 2 3
4 5 6
7 8 9
0
Total number of sequences of length 3: 130
Explanation:
Keypad Representation:
We possess an unsorted map of keys (unordered_map<int, vector<int>>), where each key corresponds to valid adjacent keys ranging from 0 to 9. As an illustration:
Key 0 has the capability to shift to positions 0 and 8. The accessibility of positions 1, 4, and 2 is granted by key 1.
Structure:
SequenceState: In BFS, the status of a sequence is denoted by the SequenceState construct, encompassing two attributes:
- digit: Denotes the most recent digit in the sequence.
- length: Indicates the current length of this particular sequence.
Helper Methods:
- setupBFS: This method commences by assigning keys ranging from 0 to 9 and one-character sequences to the BFS queue. Each digit from 0 to 9 is represented in the BFS queue by a SequenceState object containing the digit and a sequence length of 1.
- traverseNeighbors: This method navigates through the neighboring digits of a given digit and constructs sequences of increasing lengths. In cases where the current sequence length matches the specified length, exploration of that specific sequence ceases. Otherwise, valid neighboring digits are enqueued for further processing in the BFS queue.
Complexity Analysis:
Time Complexity:
Breadth-First Search (BFS) approach for the Mobile Numeric Keypad Problem has time complexity associated with the number of possible sequences generated by the BFS traversal.
- Initial State: Thus, 10 initial sequences, each of length 1, are put into the queue, which starts from 0 to 9.
- BFS Traversal: BFS looks at what each digit could be and its valid neighbors, which generates new sequences that increase the sequence length by 1 for each digit. At each level of BFS, we can generate at most 5 new sequences based on each existing sequence having at most 5 neighbors.
- Number of Levels: The algorithm creates sequences at increasing levels, i.e., sequence level by level, each of which consists of sequences of a given length. The levels for that sequence for length n add an extra level that represents another digit in the sequence, so they're n deep in total.
- Total Sequences: Up to 5 new sequences are generated for each sequence at each level. Therefore, the number of all the sequences of length n is about 5^n because each digit has at most 5 possible neighbors. The generation of the sequences dominates the time complexity with respect to the number of sequences processed. Since we explore 5n sequences in the worst case, the overall time complexity of the algorithm is O (5n).
Space Complexity:
The space complexity of the BFS strategy primarily stems from preserving the sequences in the queue, which correlates directly with the graph's node count.
- Queue Storage: The queue holds the explored sequences. In the worst scenario, the queue's length can reach 5^n for every feasible digit combination, representing a single sequence.
- Memory Usage: Each sequence consists of a pair of digits, with a fixed length occupying constant memory. Consequently, allocating space equivalent to the overall sequence count in the queue becomes essential.
