The Mobile Numeric Keypad Problem is a graph traversal combinatorial problem motivated by the constraints (layout and movement) around the keypad of a mobile phone. Therefore, the problem is to see how many unique sequences of a specified length n of digits we can form by pressing keys on the keypad strictly following adjacency rules. The layout of a typical mobile keypad is:
1 2 3
4 5 6
7 8 9
0
In this keypad layout, we define the keys as nodes in a graph and adjacent keys as those keys that share an edge either horizontally, vertically, or diagonally. Let's say the key 5 is adjacent to 2, 4, 6 and 8, and the key 0 is only adjacent to 8. The valid transitions between keys when forming sequences are dictated by these adjacency relationships.
The problem is to find how many sequences of length n can be defined such that starting from any digit on the keypad, all adjacency constraints hold. If n=2, 5 gives valid sequences 52, 54, 56, 58 etc. It can be shown using big O notation. As n grows, the number of possible sequences increase exponentially, so the problem gets more difficult.
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.
Representation of the keypad as a graph where nodes represent each key, and edges connect together adjacent keys is utilized to solve Mobile Numeric Keypad Problem. Finally, we solve this problem using a dynamic programming approach. For any given sequence length n, we can efficiently compute the number of linked sequences. Specifically, the states are defined in terms of the current key and sequence length, and results computed for previous sequence length are used to build longer sequence solutions.
Approach-1: Brute Force Approach (Recursive Backtracking)
The Mobile Numeric Keypad Problem is first solved by brute force by exploring each sequence of length, starting with each digit of the keypad. This approach represents the keypad as a graph, where each digit is a node and valid moves between neighboring keys are defined by edges. The algorithm generates all possible sequences using recursion with backtracking by traversing this graph.
We use the recursive function, which takes in a starting digit, moves to its valid neighbors, and reduces the sequence length with each step. When the length becomes 1, it records a valid sequence. With backtracking, the algorithm guarantees that all possible combinations will be covered because we can backtrack when we have created one path and move back to explore other options only.
Program:
Let us take an example to illustrate the Mobile Numeric Keypad problem in C++ using Brute Force Approach.
#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 taken to be a graph, which includes digit nodes and valid moves (edges) between adjacent keys. This approach uses recursion with backtracking to generate all possible digit sequences for the given 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 above brute force approach can be analyzed based on the recursive exploration of all possible sequences starting from each digit on the keypad:
- Key Observations: Every digit can have up to 5 neighbors, except edge digits like 1, 3, 7, and 9, which can have fewer (no neighbors, 1 neighbor, or 2 neighbors). The sequence length n is the same as the recursion depth. The function explores all valid neighbors of the current digit at each level of recursion.
- Recursive Calls: Each digit in a sequence of length n makes up to 5 recursive calls. The result is that each recursive call adds another recursive call for the next level, which means an exponential number of 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) is a graph traversal strategy that traverses all possible paths layer by layer from the starting node (or bare digit on the keypad) and spreads outwards. BFS is used to generate valid sequences of length n, given any digit as a starting position for the Mobile Numeric Keypad Problem. Each digit (0-9) is represented as a node in a graph, and the allowed moves between digits constitute the edges. The character of BFS is that it should explore sequences in steps (levels). With each step, each level is a sequence of one more digit than the previous step.
Program:
Let us take an example to illustrate the Mobile Numeric Keypad problem in C++ using Breadth-First Search (BFS) Approach.
#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 have an unordered map of keys (unordered_map<int, vector<int>>), key -> valid neighboring keys (0 - 9). For example:
Key 0 can move to 0 and 8. 1, 4, 2 can be accessed by the key 1.
Structure:
SequenceState: The state of a sequence in BFS is represented by a structure SequenceState. It holds two properties:
- digit: The newest digit of the sequence.
- length: The length of this current sequence.
Helper Functions:
- initializeBFS: The function starts with keys from 0 to 9 and sequences of length 1 in the BFS queue. The BFS queue is initialized with a SequenceState for each digit from 0 to 9, with the digit and the sequence length of 1.
- exploreNeighbors: This function goes through the digit's neighbor and generates a sequence of increasing length. For a given sequence length n, further exploration of this sequence is stopped if the current sequence length is n as well. Otherwise, it moves the valid neighboring digits into 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 BFS approach's space complexity is mainly due to the storage of the sequences in the queue, which is directly related to the number of nodes in the graph.
- Queue Storage: The sequences as they are explored are stored in the queue. In the worst case, the length of the queue can be up to 5^n for each possible combination of digits, one sequence.
- Memory Usage: The number of sequences is a pair of digits, and the sequence length and each sequence occupies constant space. Hence, it is necessary to reserve a total space proportional to the total number of sequences in the queue.