Knight on a Phone

Given a phone keypad as shown below:

0 1 2
3 4 5
6 7 8
  9

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.

Generalize this problem to find the number of unique numbers of length n that can be form starting from any number.

This question was taken from: https://stackoverflow.com/questions/2893470/generate-10-digit-number-using-a-phone-keypad/

The Idea: For every number we begin at we have fixed amount of options to select. So this problem can be modeled using a tree given a graph that represents the choices we have. This is shown below.The number of root to leaf paths also represent the number of unique numbers. For the brute force method, we can model it using BFS.

For the dynamic programming solution we need to first recognize the overlapping subproblems in the tree and then structure the problem in the context of our graphic model. I have modeled this for (start=5, length=4) below.The same two parameters (start, length) can represent the an equivalent subproblem. We can model to say that sol(5, 4) would return the number of 4 digit unique solutions starting at digit 5. Using DFS the algorithm will terminate when either we have reached the end of tree, in which case we return 1 because this is one unique number, or we've found an already solved solution in memory (in which case we return that solution), or we solved a complete subproblem (which is the sum of the previous solutions).

Complexity: BF: O(2*n + 3*m) time where n + m = length number, DP: O(Length) time

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')