I am trying to implement DFS using recursion in Python I am not so good in python but trying to learn it by exploration and experience. The Following is the code I have designed based on my visualization
rowNums = [0, -1, 0, 1]
colNums = [-1, 0, 1, 0]
class Point():
x:int
y:int
def __init__(self, x, y) -> None:
self.x = x
self.y = y
class Node():
coordinates:Point
distance:int
def __init__(self, coords:Point, distance:int):
self.coordinates = coords
self.distance = distance
def isSafe(point:Point, nrow, ncol):
if point.x>=0 and point.x<nrow and point.y>=0 and point.y<ncol:
return True
return False
def DFS(maze:list[list[int]],
src:Point,
dest:Point,
nrow:int,
ncol:int):
visited = []
if maze[src.x][src.y] != 1 or maze[dest.x][dest.y] != 1:
return -1
for i in range(len(maze)):
visited.append([False]*len(maze[i]))
visited[src.x][src.y] = True
def recurTillDeath(node:Node):
point = node.coordinates
if point.x == dest.x and point.y == dest.y:
print("Found it")
return node.distance
else:
print(str(point.x) + " " + str(point.y))
for i in range(0,4):
print("i Values for Point ("+ str(point.x) + " " + str(point.y) +") is "+str(i))
newP = Point(point.x+rowNums[i],point.y+colNums[i])
print(str(newP.x) + " " + str(newP.y))
if isSafe(newP,nrow,ncol) and maze[newP.x][newP.y] != 0 and visited[newP.x][newP.y] != True:
visited[newP.x][newP.y]=True
val = recurTillDeath(Node(newP,node.distance+1))
if val is not None:
return val
return recurTillDeath(Node(src,0))
if __name__ == "__main__":
inputMaze = [[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]]
src = [0, 0]
dest = [3, 3]
srcObject = Point(src[0], src[1])
destObject = Point(dest[0], dest[1])
val = DFS(inputMaze, srcObject, destObject, len(inputMaze), len(inputMaze[0]))
if val == -1:
print("Path does not exist")
else:
print("Length of DFS path is: ", val)
This Code works, But I want to know, Have I used recursion correctly in my recurTillDeath function? Is there a better, more standardized approach to recur?
Edit: as I found solution to my original issue, Modified the question to ask for code improvement help
It looks fine, except for one thing:
DFS can return -1, None, or a non-negative distance. -1 is only returned when source or target are not cells with a 1-value. None is returned in all other cases where no path could be found. This means the main program will misinterpret the result when val is None.
For example, change the input maze such that there is no path by replacing a critical 1 to 0, and then run the program:
inputMaze = [[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 0, 1, 1]]
# ^-------------changed to zero
Then your code outputs:
Length of DFS path is: None
...while it really should say:
Path does not exist
It is better to avoid None returns, and also return -1 in those cases.
Not an error, but a code smell which could lead to errors in other circumstances: don't define attributes at the level of the class when you intend to use them as instance attributes. They have a different use and behaviour. In your code there is no negative effect, because in the constructors, you always define instance attributes with the same name, so there is no confusion. But the class members serve no purpose then.
All other remarks I could have are not errors, but just code review.
I post here a revised version of your code with comments on the changes I made:
from __future__ import annotations
class Point:
# Remove class members
def __init__(self, x, y) -> None:
self.x = x
self.y = y
# With this, never worry about how to print a Point
def __repr__(self):
return repr((self.x, self.y))
# Make this a method to facilitate navigation from Point to neighbor
def add(self, point: Point):
return Point(self.x + point.x, self.y + point.y)
# Use tuples for immutable data, all CAPS for constant names, and combine
# together what is related, which in this case can be Point instances:
DIRECTIONS = (Point(0, -1), Point(-1, 0), Point(0, 1), Point(1, 0))
# Node class is not needed, as distance can be managed
# via argument and return value
# But use a class for managing the maze
class Maze:
# Don't ask caller to pass values that can be derived (ncol nrow)
def __init__(self, maze: list[list[int]]):
self.maze = maze
self.nrows = len(maze)
self.ncols = len(maze[0])
# Make this a method:
def isSafe(self, point: Point):
# Use chained comparisons and just return the result (it is boolean)
# Also include the cell test
return (0 <= point.x < self.nrows and 0 <= point.y < self.ncols
and self.maze[point.x][point.y] != 0)
# Use lowercase method name
# By adding visited as parameter, we can use this function for recursion
def dfs(self, src: Point, dest: Point, visited: list[list[bool]]=None):
if self.maze[src.x][src.y] != 1 or self.maze[dest.x][dest.y] != 1:
return -1
if visited is None: # First call (not recursive)
# Populate visited without append:
visited = [[False]*self.ncols for _ in range(self.nrows)]
visited[src.x][src.y] = True
print(src)
if src.x == dest.x and src.y == dest.y:
print("Found it")
return 0 # Distance is 0 -- will increase when backtracking
else:
for step in DIRECTIONS:
newP = src.add(step)
print(f"Neighbor: {newP}")
# Comparing with True can be simplified
# Incorporate the cell's value check in `isSafe`
if self.isSafe(newP) and not visited[newP.x][newP.y]:
val = self.dfs(newP, dest, visited) # Use dfs itself
if val >= 0: # Don't work with None
return val + 1 # Add the one here! No need for Node.
return -1 # Always return number
if __name__ == "__main__":
inputMaze = [[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]]
src = [0, 0]
dest = [3, 3]
# Create maze instance once, allowing multiple dfs calls if wanted
maze = Maze(inputMaze)
# Can unpack using asterisk
distance = maze.dfs(Point(*src), Point(*dest))
if distance == -1:
print("Path does not exist")
else:
print("Length of DFS path is: ", distance)