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

Question

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:

1. The phone number cannot start from 1 or 0.
2. The phone number should not contain special characters.
3. 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'],
          '3': ['5', '7'],
          '4': ['2', '8'],
          '5': ['1', '3', '7', '9'],  #path leading to #, * are ignored
          '6': ['2', '8'],
          '7': ['5', '0', '3'],
          '8': ['4', '6'],
          '9': ['5', '0', '1'],
          '0': ['7', '9']
         }

def knightFindPhoneNumbers(knight, start, path=[]):  #here path basically is your phone number.
    '''
    :param graph:  The movement of knight
    :param start: You can start from anywhere except 0 and 1
    :param path:
    :return: list containing all the valid numbers
    '''
    path = path + [start]
    if len(path) == 7:  #if the total number of length of path is 7 return the path. It means we found a valid phone number
        return [path] #we found one valid phone number
    if not knight.has_key(start):
        return []
    paths = []
    for node in knight[start]:
        if node:
            newpaths = knightFindPhoneNumbers(knight, node, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

def bishopFindPhoneNumbers(bishop, start, path=[]):
    '''
    :param bishop:  The movement of bishop
    :param start: You can start from anywhere except 0, 1. Phone numbers cannot contain these digits
    :param path: capture the phone number
    :return: list of all phone numbers starting from some digit
    '''
    path = path + [start]
    if len(path) == 7:  #if the total number of lenght of digits is 7 return the path
        return [path]
    if not bishop.has_key(start):
        return []
    paths = []
    for node in bishop[start]:
        if node:
            newpaths = bishopFindPhoneNumbers(bishop, node, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths


chessPlayer = raw_input()   #take the input from the user
count = 0
if chessPlayer.strip() == 'knight':
    for i in ['2', '3', '4', '5', '6', '7', '8', '9']:  #the phone number can start from 2, 3, 4, 5, 6, 7, 8, 9
        for k in knightFindPhoneNumbers(knight, i):
            count += 1  #print out the phone numbers
    print count
elif chessPlayer.strip() == 'bishop':
    for i in ['2', '3', '4', '5', '6', '7', '8', '9']:   #the phone number can start from 2, 3, 4, 5, 6, 7, 8, 9
        for k in bishopFindPhoneNumbers(bishop, i):  #find phone numbers start from 2, 3, 4, 5, 6, 7, 8, 9
            count += 1
    print count

The recruiter told me the solution is inefficient, and I am wondering if anyone could suggest improvements to my answer or a better solution.

Answer 1

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

Answer 2

The biggest reason you flunked was probably that you wrote two identical functions: bishopFindPhoneNumbers(bishop, start, path) and knightFindPhoneNumbers(knight, start, path). You didn't realize that since their code was identical, you didn't need to write both of them.

Just writing

def findPhoneNumbers(adjacencies, start, path=[]):
    path += [start]
    if len(path) == 7:
        return [path]
    if not adjacencies.has_key(start):
        return []
    paths = []
    for node in adjacencies[start]:
        if node:
            newpaths = findPhoneNumbers(adjacencies, node, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

# ...

findPhoneNumbers(bishop, start)
findPhoneNumbers(knight, start)

might have been all they were looking for.

Some style notes, though:

• if not adjacencies.has_key(start) would be better written as if start not in adjacencies.

• if node can't ever be false, so don't write it.

• ['2', '3', '4', '5', '6', '7', '8', '9'] should set off your sense of code smell. Even for start in "23456789": would have been preferable.

• Finally,

      newpaths = findPhoneNumbers(adjacencies, node, path)
      for newpath in newpaths:
          paths.append(newpath)
  

should be written as

        paths += findPhoneNumbers(adjacencies, node, path)

Actually, a candidate's not knowing that += concatenates lists in Python would also be cause to fail the interview, where I'm from. So it probably wasn't just the repetition of code that was the problem.

Answer 3

I have some style notes about your script since the others covered the workings so well. The Python style guide PEP0008 is an invaluable resource for this.

I'll start with comments. You should make comments, clear, to the point and well readable. You have issues with your opening block:

#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.

Comments should have a space at the start, after the #. Lines should also try to be under 79 characters. You might think this adds lines, but really it encourages you to be more brief. As for what you're actually saying, it's more of a preamble than any explanation of the code or the problem. You begin saying "My approach", but you haven't said what you're approaching. If this is for the employers you send it in an email or explain it in conversation. Comments are for making the code's function clear, not describing your ideas about the way it's done. I'd rewrite this to be a brief explanation of the problem. Don't explain your approach, it's better to let the code do that with comments along the way to clarify more confusing parts.

Inline comments should be rare. They should only occur as brief comments that best fit on the same line instead of their own line. This isn't a great example:

knight = {'1': ['6', '8'],  #movement of knight

It seems like it's supposed to be relevant to that particular row rather than the whole knight value. Put it on the line above.

# Movement of knight
knight = {'1': ['6', '8'],  

Now, your second inline comment is worse because it's too long. Your big long comment wouldn't fit the requirement even on a line of it's own. Split it onto two lines, and take it out of the dictionary.

# Movement of knight
# This is how the graph will look for Knight with key representing
# the starting point and where they can go from there.
knight = {'1': ['6', '8'],  

...it's also unclear. with key representing the starting point and where they can go from there? You should write comments that can explain your code to someone who doesn't even know the brief, which this doesn't really do. I'd prefer it as:

# Movement of knight
# Keys represent starting points and values contain possible moves.
knight = {'1': ['6', '8'],  

Shorter, clearer and clearly delineates what the values mean.

Still on comments, I don't need to know about redundancies you've left out unless they're confusing me:

#removed the path which will go into special characters since phone number cannot contain that
'5': ['1', '3', '7', '9'],  #path leading to #, * are ignored

You're mostly saying the same thing twice, but also the bishop wouldn't move from 5 to * or # anyway, it'd only move there from 8. I'd just remove both these comments though.

Now, for your docstring you seem to have taken on the javadocs style, which is not the Python way, not to mention you actually misused it anyway by mislabelling parameters, and leaving out information about them to put in a comment instead. Docstrings have their own PEP, but here's one suggestion:

'''Calculate a list of the valid phone numbers for Knight's movement.

Knight contains the knight's movement and start is it's starting key.
Path is used to build up the phone number, it shouldn't be supplied.'''

This is clearer, gives an indication of how to use the function and actually explains the context more.

About the name, knightFindPhoneNumbers is both verbose and the wrong naming convention for Python. Python uses snake_case, like knight_find_phone_numbers. The verbosity is a sign that the function is too specific, as pointed out you could make one function do both. find_phone_numbers is pretty good then, I prefer calculate_phone_numbers personally, as you're determining values, not just finding them.

Again, back to comments:

if len(path) == 7:  #if the total number of length of path is 7 return the path. It means we found a valid phone number
    return [path] #we found one valid phone number

The second one here is totally redundant as you just said it one line before, but that first line contains a lot of redundancy. len(path) == 7 says if the total number of length of path is 7 much more concisely than you, so you can leave it out. It is a good idea to have a much shorter inline comment here though:

if len(path) == 7:
    return [path]  # Valid phone number

It is good to use an inline here, just to highlight abstractly what this means in a couple brief words.

This is confusing and sorely lacking a comment:

if not knight.has_key(start):
    return []

Is this an error? Something that shouldn't be happening? It seems like it is, and if so then you should really mark it as an error with raise ValueError("Not a valid starting point."). Returning an empty list is confusing, especially in a recursive function where that might mean an incomplete number is raised. If returning the empty list is specific intentional behaviour, explain it with a comment. But if this is your error handling, you should actually raise an error.

I'm confused why you're testing if node on knight[start]. You realise that any non empty string will evaluate as True? Meaning this should always be True and I can't see why it would be False or what it would mean. It's either unnecessary code or it's actually a test I've misunderstood.

chessPlayer isn't a clear name either. It makes it sound like it's a game, when really you just want to get chess_piece. Also to check user input, it's good to use .lower() as well as strip so that you can make sure all the characters are lowercase, in case the user entered Knight or even KNIGHT.