Generate 10-digit number using a phone keypad

Question

Given a phone keypad as shown below:

1 2 3 4 5 6 7 8 9   0 

How many different 10-digit numbers can be formed starting from 1? The constraint is that the movement from 1 digit to the next is similar to the movement of the Knight in a chess game.

For eg. if we are at 1 then the next digit can be either 6 or 8 if we are at 6 then the next digit can be 1, 7 or 0.

Repetition of digits are allowed - 1616161616 is a valid number.

Is there a polynomial time algorithm which solves this problem? The problem requires us to just give the count of 10-digit numbers and not necessarily list the numbers.

EDIT: I tried modeling this as a graph with each digit having 2 or 3 digits as its neighbors. Then I used DFS to navigate upto the depth of 10 nodes and then increment the count of numbers each time I reached the depth of 10. This obviously is not polynomial time. Assuming each digit had just 2 neighbors, this would have required at least 2^10 iterations.

The variable here is the number of digits. I have taken the eg. of 10 digit numbers. It could as well be n-digits.

Answer 1

Sure it can be done in polynomial time. It's an excellent exercise in dynamic programming or memoization.

Lets assume N (the number of digits) equals 10 for the example.

Think of it recursively like this: How many numbers can I construct using 10 digits starting from 1?

Answer is

[number of 9-digit numbers starting from 8] + [number of 9-digit numbers starting from 6]. 

So how many "9-digit numbers starting from 8" are there? Well,

[number of 8-digit numbers starting from 1] + [number of 8-digit numbers starting from 3] 

and so on. Base case is reached when you get the question "How many 1-digit numbers are there starting from X" (and the answer is obviously 1).

When it comes to complexity, the key observation is that you reuse previously computed solutions. That is for instance, the answer to "how many 5-digit numbers starting from 3" there are, can be used both when answering "how many 6-digit numbers are there starting from 8" AND "how many 6-digit numbers are there starting from 4". This reuse make the complexity collapse from exponential to polynomial.

Let's take a closer look at the complexity of a dynamic programming solution:

Such implementation would fill in a matrix in the following way:

num[1][i] = 1, for all 0<=i<=9   -- there are one 1-digit number starting from X.  for digits = 2...N     for from = 0...9         num[digits][from] = num[digits-1][successor 1 of from] +                             num[digits-1][successor 2 of from] +                             ...                             num[digits-1][successor K of from]  return num[N][1]                 -- number of N-digit numbers starting from 1. 

The algorithm simply fills the matrix one cell at a time, and the matrix is of dimension 10*N, and thus runs in linear time.

---

Wrote it down from the top of my head, please correct me if there are any typos.

Answer 2

I decided to tackle this problem and make it as extensible as I can. This solution allows you to:

Define your own board (phone pad, chess board, etc.)

Define your own chess piece (Knight, Rook, Bishop, etc.); you will have to write the concrete class and generate it from the factory.

Retrieve several pieces of information through some useful utility methods.

The classes are as follows:

PadNumber: Class defining a button on the phone pad. Could be renamed to 'Square' to represent a board square.

ChessPiece: Abstract class that defines fields for all chess pieces.

Movement: Interface that defines movement methods and allows for factory generation of pieces.

PieceFactory: Factory class to generate Chess pieces.

Knight: Concrete class that inherits from ChessPiece and implements Movement

PhoneChess: Entrance class.

Driver: Driver code.

OK, here's the code :)

package PhoneChess;  import java.awt.Point;  public class PadNumber {  private String number = ""; private Point coordinates = null;  public PadNumber(String number, Point coordinates) {     if(number != null && number.isEmpty()==false)         this.number = number;     else         throw new IllegalArgumentException("Input cannot be null or empty.");      if(coordinates == null || coordinates.x < 0 || coordinates.y < 0)         throw new IllegalArgumentException();     else         this.coordinates = coordinates;  }  public String getNumber() {     return this.number; } public Integer getNumberAsNumber() {     return Integer.parseInt(this.number); }  public Point getCoordinates() {     return this.coordinates; } public int getX() {     return this.coordinates.x; } public int getY() {     return this.coordinates.y; }  } 

ChessPiece

package PhoneChess;  import java.util.HashMap; import java.util.List;  public abstract class ChessPiece implements Movement {  protected String name = ""; protected HashMap<PadNumber, List<PadNumber>> moves = null; protected Integer fullNumbers = 0; protected int[] movesFrom = null; protected PadNumber[][] thePad = null; } 

Movement Interface:

package PhoneChess;  import java.util.List;  public interface Movement  { public Integer findNumbers(PadNumber start, Integer digits); public abstract boolean canMove(PadNumber from, PadNumber to); public List<PadNumber> allowedMoves(PadNumber from); public Integer countAllowedMoves(PadNumber from); } 

PieceFactory

package PhoneChess;  public class PieceFactory  {     public ChessPiece getPiece(String piece, PadNumber[][] thePad)     {     if(thePad == null || thePad.length == 0 || thePad[0].length == 0)         throw new IllegalArgumentException("Invalid pad");     if(piece == null)         throw new IllegalArgumentException("Invalid chess piece");      if(piece.equalsIgnoreCase("Knight"))         return new Knight("Knight", thePad);     else         return null; } } 

Knight class

package PhoneChess;  import java.util.ArrayList; import java.util.HashMap; import java.util.List;  public final class Knight extends ChessPiece implements Movement {  /**Knight movements  * One horizontal, followed by two vertical  * Or   * One vertical, followed by two horizontal  * @param name  */  public Knight(String name, PadNumber[][] thePad) {     if(name == null || name.isEmpty() == true)         throw new IllegalArgumentException("Name cannot be null or empty");      this.name = name;     this.thePad = thePad;     this.moves = new HashMap<>(); }   private Integer fullNumbers = null;  @Override public Integer findNumbers(PadNumber start, Integer digits)  {     if(start == null || "*".equals(start.getNumber()) || "#".equals(start.getNumber()) ) { throw new IllegalArgumentException("Invalid start point"); }     if(start.getNumberAsNumber() == 5) { return 0; } //Consider adding an 'allowSpecialChars' condition     if(digits == 1) { return 1; };      //Init     this.movesFrom = new int[thePad.length * thePad[0].length];     for(int i = 0; i < this.movesFrom.length; i++)         this.movesFrom[i] = -1;      fullNumbers = 0;     findNumbers(start, digits, 1);           return fullNumbers; }  private void findNumbers(PadNumber start, Integer digits, Integer currentDigits) {     //Base condition     if(currentDigits == digits)     {         //Reset         currentDigits = 1;          fullNumbers++;          return;      }     if(!this.moves.containsKey(start))         allowedMoves(start);      List<PadNumber> options = this.moves.get(start);     if(options != null)     {         currentDigits++; //More digits to be got         for(PadNumber option : options)             findNumbers(option, digits, currentDigits);     } }  @Override public boolean canMove(PadNumber from, PadNumber to)  {     //Is the moves list available?     if(!this.moves.containsKey(from.getNumber()))     {         //No? Process.         allowedMoves(from);     }     if(this.moves.get(from) != null)     {         for(PadNumber option : this.moves.get(from))         {             if(option.getNumber().equals(to.getNumber()))                 return true;         }     }     return false;  }  /***  * Overriden method that defines each Piece's movement restrictions.  */ @Override public List<PadNumber> allowedMoves(PadNumber from)  {     //First encounter     if(this.moves == null)         this.moves = new HashMap<>();       if(this.moves.containsKey(from))         return this.moves.get(from);     else     {         List<PadNumber> found = new ArrayList<>();         int row = from.getY();//rows         int col = from.getX();//columns          //Cases:         //1. One horizontal move each way followed by two vertical moves each way         if(col-1 >= 0 && row-2 >= 0)//valid         {             if(thePad[row-2][col-1].getNumber().equals("*") == false &&                      thePad[row-2][col-1].getNumber().equals("#") == false)             {                 found.add(thePad[row-2][col-1]);                 this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;             }          }         if(col-1 >= 0 && row+2 < thePad.length)//valid         {             if(thePad[row+2][col-1].getNumber().equals("*") == false &&                      thePad[row+2][col-1].getNumber().equals("#") == false)             {                 found.add(thePad[row+2][col-1]);                 this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;             }         }         if(col+1 < thePad[0].length && row+2 < thePad.length)//valid         {             if(thePad[row+2][col+1].getNumber().equals("*") == false &&                      thePad[row+2][col+1].getNumber().equals("#") == false)             {                 found.add(thePad[row+2][col+1]);                 this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;             }         }         if(col+1 < thePad[0].length && row-2 >= 0)//valid         {             if(thePad[row-2][col+1].getNumber().equals("*") == false &&                      thePad[row-2][col+1].getNumber().equals("#") == false)             found.add(thePad[row-2][col+1]);         }         //Case 2. One vertical move each way follow by two horizontal moves each way          if(col-2 >= 0 && row-1 >= 0)         {             if(thePad[row-1][col-2].getNumber().equals("*") == false &&                      thePad[row-1][col-2].getNumber().equals("#") == false)             found.add(thePad[row-1][col-2]);         }         if(col-2 >= 0 && row+1 < thePad.length)         {             if(thePad[row+1][col-2].getNumber().equals("*") == false &&                      thePad[row+1][col-2].getNumber().equals("#") == false)             found.add(thePad[row+1][col-2]);         }          if(col+2 < thePad[0].length && row-1 >= 0)         {             if(thePad[row-1][col+2].getNumber().equals("*") == false &&                      thePad[row-1][col+2].getNumber().equals("#") == false)             found.add(thePad[row-1][col+2]);         }         if(col+2 < thePad[0].length && row+1 < thePad.length)         {             if(thePad[row+1][col+2].getNumber().equals("*") == false &&                      thePad[row+1][col+2].getNumber().equals("#") == false)             found.add(thePad[row+1][col+2]);         }          if(found.size() > 0)         {             this.moves.put(from, found);             this.movesFrom[from.getNumberAsNumber()] = found.size();         }         else         {             this.moves.put(from, null); //for example the Knight cannot move from 5 to anywhere             this.movesFrom[from.getNumberAsNumber()] = 0;         }     }      return this.moves.get(from);   }  @Override public Integer countAllowedMoves(PadNumber from)  {     int start = from.getNumberAsNumber();      if(movesFrom[start] != -1)         return movesFrom[start];     else     {         movesFrom[start] = allowedMoves(from).size();     }     return movesFrom[start]; }  @Override public String toString() {     return this.name; }  } 

PhoneChess entrant class

package PhoneChess;   public final class PhoneChess  { private ChessPiece thePiece = null; private PieceFactory factory = null;  public ChessPiece ThePiece() {     return this.thePiece; }  public PhoneChess(PadNumber[][] thePad, String piece) {     if(thePad == null || thePad.length == 0 || thePad[0].length == 0)         throw new IllegalArgumentException("Invalid pad");     if(piece == null)         throw new IllegalArgumentException("Invalid chess piece");      this.factory = new PieceFactory();     this.thePiece = this.factory.getPiece(piece, thePad); }  public Integer findPossibleDigits(PadNumber start, Integer digits) {     if(digits <= 0)         throw new IllegalArgumentException("Digits cannot be less than or equal to zero");      return thePiece.findNumbers(start, digits); }  public boolean isValidMove(PadNumber from, PadNumber to) {     return this.thePiece.canMove(from, to); }  } 

Driver Code:

public static void main(String[] args) {       PadNumber[][] thePad = new PadNumber[4][3];     thePad[0][0] = new PadNumber("1", new Point(0,0));     thePad[0][1] = new PadNumber("2", new Point(1,0));     thePad[0][2] = new PadNumber("3",new Point(2,0));     thePad[1][0] = new PadNumber("4",new Point(0,1));     thePad[1][1] = new PadNumber("5",new Point(1,1));     thePad[1][2] = new PadNumber("6", new Point(2,1));     thePad[2][0] = new PadNumber("7", new Point(0,2));     thePad[2][1] = new PadNumber("8", new Point(1,2));     thePad[2][2] = new PadNumber("9", new Point(2,2));     thePad[3][0] = new PadNumber("*", new Point(0,3));     thePad[3][1] = new PadNumber("0", new Point(1,3));     thePad[3][2] = new PadNumber("#", new Point(2,3));      PhoneChess phoneChess = new PhoneChess(thePad, "Knight");     System.out.println(phoneChess.findPossibleDigits(thePad[0][1],4)); }  }