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

This problem may be also modelled as a Constraint satisfaction problem (aka CSP for short).

I suggest to use the Minion solver (fast and scalable) that you can find here.

Modelling maybe tedious and time consumming (steep learning curve).

Instead of using Minion language input, my advice is to formulate the model with solver independent modelling language such as ESSENCE and find a converter accordingly.

Answer 2

Run time constant time solution:

#include <iostream>

constexpr int notValid(int x, int y) {
return !(( 1 == x && 3 == y ) || //zero on bottom.
         ( 0 <= x && 3 > x && //1-9
           0 <= y && 3 > y ));
}

class Knight {
    template<unsigned N > constexpr int move(int x, int y) {
        return notValid(x,y)? 0 : jump<N-1>(x,y);
    }

    template<unsigned N> constexpr int jump( int x, int y ) {
        return  move<N>(x+1, y-2) +
            move<N>(x-1, y-2) +
            move<N>(x+1, y+2) +
            move<N>(x-1, y+2) +
            move<N>(x+2, y+1) +
            move<N>(x-2, y+1) +
            move<N>(x+2, y-1) +
            move<N>(x-2, y-1);
    }

public:
    template<unsigned N> constexpr int count() {
        return move<N-1>(0,1) + move<N-1>(0,2) +
            move<N-1>(1,0) + move<N-1>(1,1) + move<N-1>(1,2) +
            move<N-1>(2,0) + move<N-1>(2,1) + move<N-1>(2,2);
    }
};

template<> constexpr int Knight::move<0>(int x, int y) { return notValid(x,y)? 0 : 1; }
template<> constexpr int Knight::count<0>() { return 0; } //terminal cases.
template<> constexpr int Knight::count<1>() { return 8; }


int main(int argc, char* argv[]) {
    static_assert( ( 16 == Knight().count<2>() ), "Fail on test with 2 lenght" );  // prof of performance
    static_assert( ( 35 == Knight().count<3>() ), "Fail on test with 3 lenght" );

    std::cout<< "Number of valid Knight phones numbers:" << Knight().count<10>() << std::endl;
    return 0;
}

Answer 3

I'm not sure if I missed something, but reading the description of the problem I came to this solution. It has O(n) time complexity and O(1) space complexity.

I figured that number 1 is at a corner, right? In each corner you can either move to one of the sides (4 from 9 and 3, or 6 from 7 an 1) or one of the 'vertical' sides (8 from 3 and 1, or 2 from 9 and 7). So, corners add two moves: a side move and a 'vertical' move. This is true for all four corners (1,3,9,7).

From each side, you can either move to two corners (7 and 1 from 6, 9 and 3 from 4) or you can reach the bottom key (0). That's three moves. Two corners and one bottom.

On the bottom key (0), you can move to both sides (4 and 6). So, in each step, you check out all possible endings for the path of the previous length (that is, how many ended on a corner, a side, a 'vertical' or the 'bottom' zero key) and then generate new ending counts according to the generation rules stated before.

• Each corner ending adds a side and a vertical.
• Each side ending adds 2 corners and a bottom.
• Each vertical ending adds 2 corners.
• Each bottom ending adds 2 sides.

If you start from the '1' key, you start with one possible corner solution, in each step you count the number of corner, side, vertical and bottom endings of the previous step and then apply the rules to generate the next count.

In plain javascript code.

function paths(n) {
    //Index to 0
    var corners = 1;
    var verticals = 0;
    var bottom = 0;
    var sides = 0;

    if (n <= 0) {
        //No moves possible for paths without length 
        return 0;
    }

    for (var i = 1; i < n; i++) {
        var previousCorners = corners;
        var previousVerticals = verticals;
        var previousBottom = bottom;
        var previousSides = sides;

        sides = 1 * previousCorners + 2 * previousBottom;
        verticals = 1 * previousCorners;
        bottom = 1 * previousSides;
        corners = 2 * previousSides + 2 * previousVerticals;
        //console.log("Moves: %d, Length: %d, Sides: %d, Verticals: %d, Bottom: %d, Corners: %d, Total: %d", i, i + 1, sides, verticals, bottom, corners, sides+verticals+bottom+corners);  
    }

    return sides + verticals + bottom + corners;

}

for (var i = 0; i <= 10; i++) {
    console.log(paths(i));  
}

Answer 4

I implemented both brute force and dynamic programming models

import queue


def chess_numbers_bf(start, length):
    if length <= 0:
        return 0
    phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]]
    total = 0
    q = queue.Queue()
    q.put((start, 1))

    while not q.empty():
        front = q.get()
        val = front[0]
        len_ = front[1]
        if len_ < length:
            for elm in phone[val]:
                q.put((elm, len_ + 1))
        else:
            total += 1
    return total


def chess_numbers_dp(start, length):
    if length <= 0:
        return 0

    phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]]
    memory = {}

    def __chess_numbers_dp(s, l):
        if (s, l) in memory:
            return memory[(s, l)]
        elif l == length - 1:
            memory[(s, l)] = 1
            return 1
        else:
            total_n_ways = 0
            for number in phone[s]:
                total_n_ways += __chess_numbers_dp(number, l+1)
            memory[(s, l)] = total_n_ways
            return total_n_ways
    return __chess_numbers_dp(start, 0)


# bf
for i in range(0, 10):
    print(i, chess_numbers_bf(3, i))
print('\n')

for i in range(0, 10):
    print(i, chess_numbers_bf(9, i))
print('\n')

# dp
for i in range(0, 10):
    print(i, chess_numbers_dp(3, i))
print('\n')

# dp
for i in range(0, 10):
    print(i, chess_numbers_dp(9, i))
print('\n')

Answer 5

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 6

Recursive memoization approach:

vector<vector<int>> lupt = { {4, 6}, {6, 8}, {9, 7}, {4, 8}, {3, 9, 0},
                             {},     {1,7,0}, {6, 2}, {1, 3}, {2, 4} };

int numPhoneNumbersUtil(int startdigit, int& phonenumberlength, int currCount, map< pair<int,int>,int>& memT)
{
    int noOfCombs = 0;
    vector<int> enddigits;

    auto it = memT.find(make_pair(startdigit,currCount));
    if(it != memT.end())
    {
        noOfCombs = it->second;
        return noOfCombs;
    }

    if(currCount == phonenumberlength)
    {
        return 1;
    }

    enddigits = lupt[startdigit];
    for(auto it : enddigits)
    {
        noOfCombs += numPhoneNumbersUtil(it, phonenumberlength, currCount + 1, memT);
    }

    memT.insert(make_pair(make_pair(startdigit,currCount), noOfCombs));
    return memT[make_pair(startdigit,currCount)];

}

int numPhoneNumbers(int startdigit, int phonenumberlength)
{
    map<pair<int,int>,int> memT;
    int currentCount = 1; //the first digit has already been added
    return  numPhoneNumbersUtil(startdigit, phonenumberlength, currentCount, memT);
}