3
\$\begingroup\$

I solved a Daily Coding Challenge, but i suspect my code could be optimised. The challenge is the following:

You are given an N by M matrix of 0s and 1s. Starting from the top left corner, how many ways are there to reach the bottom right corner?
You can only move right and down. 0 represents an empty space while 1 represents a wall you cannot walk through. For example, given the following matrix:

[[0, 0, 1],
 [0, 0, 1],
 [1, 0, 0]]

Return two, as there are only two ways to get to the bottom right:
Right, down, down, right
Down, right, down, right
The top left corner and bottom right corner will always be 0.

You can see my solution below. Any tips on how to improve on it are very welcome.

def solution(matrix, x=0, y=0):
    count = 0
    right, left = False, False

    if y == len(matrix) - 1 and x == len(matrix[0]) - 1:  # found a way
        return 1

    if x < len(matrix[0]) - 1:
        if matrix[y][x+1] == 0:
            count += solution(matrix, x+1, y)  # look right
            right = True

    if y < len(matrix) - 1:
        if matrix[y+1][x] == 0:
            count += solution(matrix, x, y+1)  # look down
            left = True

    if not right and not left:  # dead end
        return 0

    return count


if __name__ == "__main__":
    print(solution([[0, 0, 0], [0, 0, 0], [0, 1, 0]]))
\$\endgroup\$
0
\$\begingroup\$

You don't need right and left: they add nothing that isn't already covered by count.

Compute lengths once rather than repeatedly.

Check for empty matrix rows and/or columns, or invalid x and y, if your code needs to handle such edge cases.

def solution(matrix, x=0, y=0):
    count = 0
    y_limit = len(matrix) - 1
    x_limit = len(matrix[0]) - 1

    # Success.
    if y == y_limit and x == x_limit:
        return 1

    # Look right.
    if x < x_limit and matrix[y][x + 1] == 0:
        count += solution(matrix, x + 1, y)

    # Look down.
    if y < y_limit and matrix[y + 1][x] == 0:
        count += solution(matrix, x, y + 1)

    return count
\$\endgroup\$
1
  • \$\begingroup\$ I don't think edge cases have to be considered in my case. this helped, thank you! \$\endgroup\$
    – John Doe
    Jul 9 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.