I got this problem during a mock interview, and I would like to get code review for the backtracking solution. I include 7 test cases, and my solution passes 7 out of 7 test cases. See the online code compiler here
Robot Paths
Prompt: Given a matrix of zeroes, determine how many unique paths exist from the top left corner to the bottom right corner
Input: An Array of Array of Integers (matrix)
Output: Integer
Examples:
matrix = [[0,0,0,0], [0,0,0,0], [0,0,0,0]] robotPaths(matrix) = 38
matrix = [[0,0,0], [0,0,0]] robotPaths(matrix) = 4
# Note: From any point, you can travel in the four cardinal directions. I decided to do backtracking approach to solve this problem.
# (north, south, east, west). A path is valid as long as it travels
# from the top left corner to the bottom right corner, does not go
# off of the matrix, and does not travel back on itself
def robot_paths(matrix):
num_of_rows = len(matrix)
num_of_cols = len(matrix[0])
def traverse(row, col):
nonlocal num_of_rows
nonlocal num_of_cols
# is row and col in bounds?
if row < 0 or row >= num_of_rows or col < 0 or col >= num_of_cols:
return 0
# has row, col already been visited?
if matrix[row][col] == 1:
return 0
# is row, col the destination?
if row == num_of_rows - 1 and col == num_of_cols - 1:
return 1
# mark coordinate as visited
matrix[row][col] = 1
# initialize sum of total unique paths to end from that coordinate
s = traverse(row, col + 1) + traverse(row + 1, col) + traverse(row - 1, col) + traverse(row, col - 1)
# backtrack; mark coordinate as unvisited so it can be
matrix[row][col] = 0
return s
return traverse(0, 0)
#############################################
######## DO NOT TOUCH TEST BELOW!!! #######
#############################################
def expect(count, name, test):
if (count == None or not isinstance(count, list) or len(count) != 2):
count = [0, 0]
else:
count[1] += 1
result = 'false'
errMsg = None
try:
if test():
result = ' true'
count[0] += 1
except Exception as err:
errMsg = str(err)
print(' ' + (str(count[1]) + ') ') + result + ' : ' + name)
if errMsg != None:
print(' ' + errMsg + '\n')
def lists_equal(lst1, lst2):
if len(lst1) != len(lst2):
return False
for i in range(0, len(lst1)):
if lst1[i] != lst2[i]:
return False
return True
print('Robot Paths Tests')
test_count = [0, 0]
def test():
matrix = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
example = robot_paths(matrix)
return example == 38
expect(test_count, 'should work on first example input', test)
def test():
matrix = [[0, 0, 0],
[0, 0, 0]]
example = robot_paths(matrix)
return example == 4
expect(test_count, 'should work on second example input', test)
def test():
matrix = [[0]]
example = robot_paths(matrix)
return example == 1
expect(test_count, 'should work on single-element input', test)
def test():
matrix = [[0, 0, 0, 0, 0, 0]]
example = robot_paths(matrix)
return example == 1
expect(test_count, 'should work on single-row input', test)
def test():
matrix = [[0],
[0],
[0],
[0],
[0]]
example = robot_paths(matrix)
return example == 1
expect(test_count, 'should work on a 5 x 8 matrix input', test)
def test():
matrix = [[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]
print(" Please be patient, test 6 may take longer to run")
example = robot_paths(matrix)
return example == 7110272
print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n')