Shortest path in Binary Maze

Question

I want a feedback on my code for the below known problem from Daily coding challenge:

You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on.

Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board.

For example, given the following board:

[[f, f, f, f],
[t, t, f, t],
[f, f, f, f],
[f, f, f, f]]

My solution in Python: I have added comments in my code itself to make it more explanatory

import copy
def shortestpath(m, start, end):
# store the coordinates of start and end
 p = end[0]
 q = end[1]
 a = start[0]
 b = start[1]
# if end destination is a wall, return a message
 if m[p][q] == 1:
 return ('Destination is a wall')
 if a==p and b==q:
 return('Start and End same')
# store the size of matrix
 M = len(m[0])
 N = len(m)
# create a matrix of all -9 of the same size of the maze. this will be populated later according to distance from 
# start and -1 if its a wall. So it will have -1 if the coordinate has wall and an integer for number of steps fro
# start
 dist = [[-9 for _ in range(M)] for _ in range(N)]
# the starting point is initialised with distance 0 and also we take a deepcopy of the distance dist matrix,
# the usage of the copy will be exlained later
 dist[a][b] = 0
 distcopy = copy.deepcopy(dist)
 while True:
# for the complete matrix, we iterate the matrix until we reach the destination
# the very first time, a and b will have value of the starting point so the iterations will start from 
# starting point. I transverse from left to right and then down as normal 2D array
# as starting point is initialised to 0, its neighbour will be 0+1 and then further its neighbour will be 0+1+1
# also we not only popluate the current a,b position, but also all the neighbours, like up, down, right, left
 for i in range(a, N):
 for j in range(b, M):
 # left neighbour 
 if i - 1 >= 0:
 [dist[i][j] , dist[i-1][j]] = neighbours(dist[i][j] , dist[i-1][j] , m[i-1][j])
 # right neighbour 
 if i + 1 < N:
 [dist[i][j] , dist[i+1][j]] = neighbours(dist[i][j] , dist[i+1][j] , m[i+1][j])
 # above neighbour 
 if j - 1 >= 0:
 [dist[i][j] , dist[i][j-1]] = neighbours(dist[i][j] , dist[i][j-1] , m[i][j-1])
 # below neighbour 
 if j + 1 < M:
 [dist[i][j] , dist[i][j+1]] = neighbours(dist[i][j] , dist[i][j+1] , m[i][j+1])
# if the value -9 is replaced by any value, it means the number of steps have been found and hence ot returns 
 if dist[p][q] != -9:
 return dist[p][q]
# here we check the dist matrix with the copy before the current iteration started
# if there is no change in M X N matrix, it means, no path was able to be found
# it can happen when there is a wall all together and traversing is not possible
 if dist == distcopy:
 return ('No path available')
# the copy is updated afer the last row is iterated. here the N-1 check is important as otherwise there will be
# instances when the complete row was same as earlier, but as it was not the last row, it came out,
# so we should ideally be checking the complete matrix of M X N instead of individual rows
 else:
 if i == N - 1:
 distcopy = copy.deepcopy(dist)
 a = 0
 b = 0
def neighbours(d_curr , d_ngbr , m_ngbr):
# here we compute the distance of either the current position or the neighbour.
# passsed values are current position, position of neighbour and the status of neighbour if its a wall or not
# d_curr != -9 means, the position has been calculated, either wall or the distance from start
# similary for d_ngbr which corresponds to neighbour
# m_ngbr represnts the input matrix which tells about the walls within the maze
 if d_curr != -9:
 if d_ngbr == -9:
 if m_ngbr == 0:
 if d_curr != -1:
 d_ngbr = d_curr + 1
 else:
 d_ngbr = -1
 else:
 if d_ngbr != -9 and m_ngbr == 0:
 d_curr = d_ngbr + 1
 return [d_curr , d_ngbr]
# here 1 represnts a wall and 0 is a valid path
m = [[0, 1, 0, 0, 0, 0, 1, 0, 0, 0],
 [0, 1, 0, 1, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 1, 0, 0, 1, 0, 1, 0],
 [1, 1, 1, 1, 0, 1, 1, 1, 1, 0],
 [0, 0, 0, 1, 0, 0, 0, 1, 0, 1],
 [0, 1, 0, 0, 0, 0, 1, 0, 1, 1],
 [0, 1, 1, 1, 1, 1, 1, 1, 1, 0],
 [0, 1, 0, 0, 0, 0, 1, 0, 0, 0],
 [0, 0, 1, 1, 1, 1, 0, 1, 1, 0]]
start = [0, 0]
end = [3, 4]
shortestpath(m, start, end)

• Samwise: FYI you've got a bug -- try shortestpath(m, [2, 2], [8, 1])...

Answer 1

As noted in a comment, I think you've got a bug, but I'll do a pass over the code for style since it works for your test case at least. These are mostly minor style points rather than addressing the overall structure of the code; my goal is going to be to make the code easier to read without doing a full rewrite from scratch or changing the way it works.

1. Clearly specify what your functions take as arguments and what they return. One way to do this is docstrings; I usually prefer doing it with type annotations since those can be checked by mypy and the format is actually built into Python 3.

2. Having added type annotations, I'd suggest changing some of those types: use 2-tuples for the coordinates (since you always want exactly two int values there, you can make mypy enforce this by specifying it as a Tuple[int, int]), and raise exceptions for errors rather than returning a string (this is a much more standard way of handling errors in Python). Same for neighbors where you're always returning two values.

3. Use destructuring to assign multiple variables, e.g. a, b = start.

4. Align your comments to the indentation of the blocks they describe. Also, omit comments like # the usage of the copy will be exlained later. Either explain it or don't, but don't comment your comments. :)

5. You state the problem in terms of bool values, but your code uses ints. Since you use lots of ints to keep track of distances and coordinates, it's already hard to keep track of what each number represents; if you can turn at least some of those into bools it makes it easier to discern the use of each variable from its type.

6. Try to reduce nested ifs. For example, this:

 if m_ngbr == 0:
 if d_curr != -1:
 d_ngbr = d_curr + 1
 else:
 d_ngbr = -1

could be written as:

 if m_ngbr:
 d_ngbr = -1
 elif d_curr != -1:
 d_ngbr = d_curr +1

7. Magic values like -9 and -1 are dangerous, and I suspect one of those might be the origin of your bug. :) Consider defining them as constants to at least make them easier to distinguish from "real" numbers, or better yet, use alternate types like None to indicate unset values.

import copy
from typing import List, Tuple
def shortestpath(m: List[List[bool]], start: Tuple[int, int], end: Tuple[int, int]) -> int:
 """Returns the length of the shortest path through m from start to end. Raises if there's no path."""
 # store the coordinates of start and end
 p, q = end
 a, b = start
 # if end destination is a wall, return a message
 if m[p][q]:
 raise Exception('Destination is a wall')
 if start == end:
 raise Exception('Start and End same')
 # store the size of matrix
 M = len(m[0])
 N = len(m)
 # create a matrix of all -9 of the same size of the maze. this will be populated later according to distance from 
 # start and -1 if its a wall. So it will have -1 if the coordinate has wall and an integer for number of steps fro
 # start
 dist = [[-9 for _ in range(M)] for _ in range(N)]
 # the starting point is initialised with distance 0 and also we take a deepcopy of the distance dist matrix,
 dist[a][b] = 0
 distcopy = copy.deepcopy(dist)
 while True:
 # for the complete matrix, we iterate the matrix until we reach the destination
 # the very first time, a and b will have value of the starting point so the iterations will start from 
 # starting point. I transverse from left to right and then down as normal 2D array
 # as starting point is initialised to 0, its neighbour will be 0+1 and then further its neighbour will be 0+1+1
 # also we not only popluate the current a,b position, but also all the neighbours, like up, down, right, left
 for i in range(a, N):
 for j in range(b, M):
 # left neighbour 
 if i - 1 >= 0:
 dist[i][j] , dist[i-1][j] = neighbours(dist[i][j] , dist[i-1][j] , m[i-1][j])
 # right neighbour 
 if i + 1 < N:
 dist[i][j] , dist[i+1][j] = neighbours(dist[i][j] , dist[i+1][j] , m[i+1][j])
 # above neighbour 
 if j - 1 >= 0:
 dist[i][j] , dist[i][j-1] = neighbours(dist[i][j] , dist[i][j-1] , m[i][j-1])
 # below neighbour 
 if j + 1 < M:
 dist[i][j] , dist[i][j+1] = neighbours(dist[i][j] , dist[i][j+1] , m[i][j+1])
 # if the value -9 is replaced by any value, it means the number of steps have been found and hence ot returns 
 if dist[p][q] != -9:
 return dist[p][q]
 # here we check the dist matrix with the copy before the current iteration started
 # if there is no change in M X N matrix, it means, no path was able to be found
 # it can happen when there is a wall all together and traversing is not possible
 if dist == distcopy:
 raise Exception('No path available')
 # the copy is updated afer the last row is iterated. here the N-1 check is important as otherwise there will be
 # instances when the complete row was same as earlier, but as it was not the last row, it came out,
 # so we should ideally be checking the complete matrix of M X N instead of individual rows
 else:
 if i == N - 1:
 distcopy = copy.deepcopy(dist)
 a = 0
 b = 0
def neighbours(d_curr: int, d_ngbr: int, m_ngbr: bool) -> Tuple[int, int]:
 # here we compute the distance of either the current position or the neighbour.
 # passsed values are current position, position of neighbour and the status of neighbour if its a wall or not
 # d_curr != -9 means, the position has been calculated, either wall or the distance from start
 # similary for d_ngbr which corresponds to neighbour
 # m_ngbr represnts the input matrix which tells about the walls within the maze
 if d_curr != -9:
 if d_ngbr == -9:
 if m_ngbr:
 d_ngbr = -1
 elif d_curr != -1:
 d_ngbr = d_curr +1
 else:
 if d_ngbr != -9 and not m_ngbr:
 d_curr = d_ngbr + 1
 return d_curr, d_ngbr
# here W represnts a wall and P is a valid path
W = True
P = False
maze = [
 [P, W, P, P, P, P, W, P, P, P],
 [P, W, P, W, P, P, P, W, P, P],
 [P, P, P, W, P, P, W, P, W, P],
 [W, W, W, W, P, W, W, W, W, P],
 [P, P, P, W, P, P, P, W, P, W],
 [P, W, P, P, P, P, W, P, W, W],
 [P, W, W, W, W, W, W, W, W, P],
 [P, W, P, P, P, P, W, P, P, P],
 [P, P, W, W, W, W, P, W, W, P],
]
start = [0, 0]
end = [3, 4]
assert shortestpath(maze, (0, 0), (3, 4)) == 11