Solve Robot Paths using backtracking

Question

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

Answer 1

There are a few things I would like to point out to you.

Style

Python has an official style guide called PEP8. Under "Indendation" there is the following rule most Python programmers stick to:

Use 4 spaces per indentation level.

Reference: PEP8 - Indentation

This would also make your code consistent with the provided test code.

Though not strictly part of PEP8, most of the tools integrated in Python IDEs would also tell you that s is not a good variable name. Use something that is more descriptive (n_paths maybe?).

While we're at it, you can wrap long lines such as the sum of the four traverse calls on multiple lines to allow better readability in case you have, say two documents next to each other or a small screen. Including the previous note, s = ... could be transformed into, e.g.

n_paths = traverse(row, col + 1) \
    + traverse(row + 1, col) \
    + traverse(row - 1, col) \
    + traverse(row, col - 1)

The nonlocal keyword

I suspect you slightly missunderstood what nonlocal does. All variables from an outer scope are automatically available to read from in nested scopes. This means in your case, traverse can see num_of_rows and num_of_cols from robot_paths automatically.

Statements like nonlocal or global only come into play whenever you want to assign to a variable not in your local scope. The Python interpreter would then recognize, that you don't want to create a new local variable with the given name, but instead use an already existing one from an outer scope. This SO answer has a nice example to show you that effect.

Answer 2

The x < y < z operator

Instead of this:

if row < 0 or row >= num_of_rows or col < 0 or col >= num_of_cols:

You can write like this:

if not(0 <= row < num_of_rows and 0 <= col < num_of_cols):

Which is not only a bit more compact, but also quite natural to read.

Modifying the input

Unless the problem description explicitly allows it, it's better not to modify the input.