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 q = end a = start b = start # 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) 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)