Mobile Numeric Keypad Problem Solution in Java

Mobile Numeric Keypad Problem

Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. You are not allowed to press bottom row corner buttons (i.e. * and # ).
Given a number N, find out the number of possible numbers of given length.

Examples:

For N=1, number of possible numbers would be 10 (0, 1, 2, 3, …., 9)
For N=2, number of possible numbers would be 36
Possible numbers: 00,08 11,12,14 22,21,23,25 and so on.
If we start with 0, valid numbers will be 00, 08 (count: 2)
If we start with 1, valid numbers will be 11, 12, 14 (count: 3)
If we start with 2, valid numbers will be 22, 21, 23,25 (count: 4)
If we start with 3, valid numbers will be 33, 32, 36 (count: 3)
If we start with 4, valid numbers will be 44,41,45,47 (count: 4)
If we start with 5, valid numbers will be 55,54,52,56,58 (count: 5)

Question is: We need to print the count of possible numbers.


Solution 1(Based on DFS):

N = 1 is trivial case, number of possible numbers would be 10 (0, 1, 2, 3, …., 9)
For N > 1, we need to start from some button, then move to any of the four direction (up, left, right or down) which takes to a valid button (should not go to *, #). Keep doing this until N length number is obtained (depth first traversal).

Solution 2(Recursive):

Mobile Keypad is a rectangular grid of 4X3 (4 rows and 3 columns)
Lets say Count(i, j, N) represents the count of N length numbers starting from position (i, j)

If N = 1
  Count(i, j, N) = 10
Else
  Count(i, j, N) = Sum of all Count(r, c, N-1) where (r, c) is new
                   position after valid move of length 1 from current
                   position (i, j)

Sample Code:

/************@Author : Abhinaw Tripathi*******************/

class IndexResult
{
int up,down,left,right;

public IndexResult()
{
up = down = left = right = -1;
}
}

public class KepadProblem
{

// check if given index is safe
static boolean isSafe(int i, int j)
{
return (i>=0 && i<3 && j>=0 && j<3);
}

// get set of indices in all 4 directions
static IndexResult getIndices(int n)
{
IndexResult result = new IndexResult();

// handle case for digit 0 separately
if(n == 0)
{
result.up = 8;

return result;
}

// get row and column of digit in 3*3 matrix
int row = n/3;
if(n%3 == 0)
row--;
int col = n - (row*3) - 1;

// set up index
if(isSafe(row-1,col))
result.up = (row-1)*3 + col + 1;

// set down index handling case for digit 8 separately
if(n == 8)
result.down = 0;
else
{
if(isSafe(row+1,col))
result.down = (row+1)*3 + col + 1;
}

if(isSafe(row,col-1))
result.left = row*3 + col;

if(isSafe(row,col+1))
result.right = row*3 + col + 2;

return  result;
}

static int getCount(int N)
{
int[][] mat = new int[10][N];

for(int j=0;j<N;j++)
{
for(int i=0;i<=9;i++)
{
if(j == 0)
mat[i][j] = 1;
else
{
// get set of indices in all 4 directions in "result"
IndexResult result = getIndices(i);

mat[i][j] = mat[i][j-1];
if(result.up != -1)
mat[i][j] += mat[result.up][j-1];
if(result.down != -1)
mat[i][j] += mat[result.down][j-1];
if(result.left != -1)
mat[i][j] += mat[result.left][j-1];
if(result.right != -1)
mat[i][j] += mat[result.right][j-1];
}
}
}

// sum of answers for length N for all starting digits
int sum = 0;
for(int i=0;i<=9;i++)
sum += mat[i][N-1];

return sum;
}

public static void main(String[] args)
{
int N = 5;
System.out.println("N = " + N);
System.out.println("\nAns = " + getCount(N));
}
}

OutPut: 

N = 5
Ans = 2062