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

I recently gave 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.

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 by 10 columns 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

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

• How do you get such great ideas? Dynamic Programming is such a pain in my life – python Oct 14 '15 at 22:02
• It comes with practice... Somewhere in Steven Skienna's The Algorithm Design Manual he says something about how once you get the hang of it, there's no point in memorizing DP problems, because it really is easier to figure them out from scratch. I remember thinking to myself that this guy was from a different planet, but after practicing A LOT this summer for some coding interviews, I actually think he is probably right. – Jaime Oct 14 '15 at 22:07
• In your example, the basic smell that something is wrong is that your algorithm is exponential. That is rarely a good thing, and often means that the "can we do better" question will have an affirmative answer. And DP is one of the usual suspects when it comes to dealing with super-polynomial problems. geeksforgeeks.org is a great source for example problems. If you work your way through 50% of theit DP archives you will be kicking ass next time DP comes your way! ;-) – Jaime Oct 14 '15 at 22:13
• Thanks Jamie for sharing this. I am still struggling in my coding interviews, and your comments will be really helpful. – python Oct 14 '15 at 22:20

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]
return []
paths = []
if node:
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.

• I got so excited after clearing all the test cases that I didn't realize my code contains so many extra lines :/ :/ – python Oct 14 '15 at 6:25
• Can you think of some other approach to solve this problem? – python Oct 14 '15 at 6:25
• Your algorithm is correct; it's just your code is extremely verbose and unidiomatic. So yeah, the "other approach" would be "do what you did, but then read over the code and make sure it looks like a good solution." Pretend you're code-reviewing your own solution, and then fix all the problems you find, and only then show it to the interviewer and say "I'm done." Don't submit work that isn't finished! :) – Quuxplusone Oct 14 '15 at 6:43

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.

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

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.