Find total number of phone numbers formed by the movement of Knight and Bishop on keypad

I recently took a test on HackerRank, and submitted my answer for the following question. I passed all the test cases but company told me that the answer is not efficient, and they are not moving forward with my candidacy.

I don't have a screenshot of the question, so I will explain as much as possible.

Question:

We have to create phone number of length 7 by the movement of knight and bishop on a keypad. The properties of the phone number:

• The phone number cannot start from 1 or 0.

• The phone number should not contain special characters.

• The length of the phone number should be 7.

The movement of Knight and Bishop is same as on Chess. See the figure below:

Your program will take input as 'knight' or 'bishop', and print out the total number of phone numbers the if knight and bishop will move on the keypad.

My approach:

```
__author__ = 'rakesh'

#My approach is to convert the whole keypad into graph with nodes representing number and edges represent there is a path
#exists between two nodes. This graph is an undirected graph which means it is bidirectional
#Now I am going to define a dictionary with key repserenting the node(Number on Keypad) and values representing direct connection to node.
#What you see below is the movement of knight represented by key value pair
#It is extremely important to avoid loop in the graph otherwise it will go into infinte recursion.

knight = {'1': ['6', '8'], #movement of knight
'2': ['7', '9'], #this is how the graph will look like for Knight with key representing the starting point and where they can go from there
'3': ['4', '8'],
'4': ['3', '9', '0'],
'6': ['1', '7', '0'],
'7': ['2', '6'],
'8': ['1', '3'],
'9': ['4', '2'],
'0': ['4', '6']
}
#removed the path which will go into special characters since phone number cannot contain that

bishop = {'1': ['5', '9'], #movement of bishop in the keypad
'2': ['4', '6'],

Counting and enumerating are two different problems. Sometimes there is no better way to count than actually enumerating all the possible values, but that is often not the case, and this is one of those cases.

To build an efficient algorithm, we are going to use dynamic programming. We will build a 7 rows (maximum length of phone number) by 10 columns (all possible digits) array. Using zero-based indexing, the item in row r and column c is the number of phone numbers of r + 1 digits that have c as the last digit.

It should be obvious that the first row of that array will be

# 2, 3, 4, 5, 6, 7, 8, 9
first_row = [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]

and that subsequent rows can be filled out by initializing them to all zeros, and then use the adjacency graph to add the values at a given column of the previous row, to all the columns that are successors of that one in the graph.

Once the array is fully filled out, the sum of the last row is the total number of numbers that can be created. Because we only care about the sum of this last row, and each row only depends on the previous one, we only need to keep two rows of the array in memory at a time. Putting it all together into code:

def count_paths(graph, length):
    this_row = [0] * 2 + [1] * 8
    for row in range(1, length):
        prev_row = this_row
        this_row = [0] * 10
        for prev, nexts in graph.items():
            for next_ in nexts:
                this_row[next_] += prev_row[prev]
    return sum(this_row)

Converting your string dictionary into its int equivalent:

knight = {0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8], 4: [3, 9, 0],
          6: [1, 7, 0], 7: [2, 6], 8: [1, 3], 9: [4, 2]}

you can now run the following:

>>> count_paths(knight, 7)
952

which of course returns the same result as your code, but uses a more efficient algorithm. How much more efficient? Well, if \$n\$ is the length of the phone number, and \$m\$ is the maximum number of possible next digits for any digit, your algorithm will have exponential behavior, \$O(m^n)\$, while the DP approach brings that down to \$O(m n)\$.

That is, by the way, a huge improvement. Try e.g. to run your code to calculate the number of 100 digit-long phone numbers, and I bet you will run out of memory before it finishes, while the DP approach spits the result in a blink of the eye:

>>> count_paths(knight, 100)
2657396588204099682921354979006480384L

StackExchange Code Review Q#107470, answer score: 18