I am having issues with dfs, probably from a RecursionError when facing a wall.
Instead of continuously running an attempt which can only lead to a wall, it is supposed to return to its previous position and try another path.
Also, it leans heavily on the order in which attempts are made (N,S,E,W or other combinations)
Thanks in advance
def portal(M,l,c): # locates current portal and changes position (if entering portal 1, go to portal 2)
for elem in D.keys():
x = 1
if elem == M[l][c]:
if [l,c] == D[elem][0] and x: [l,c] = D[elem][1]; x -=1
if [l,c] == D[elem][1] and x: [l,c] = D[elem][0]; x-=1
return [l,c]
def dfs(Q,p):
l, c = Q[-1] # previous position
if [l,c] == COORD: return True
for dir in [(l-1, c,1), (l, c - 1,2), (l , c 1,3), (l 1 ,c,4)]: # dir = (l,c,p) = next row, next column and a number that represents the direction taken (1 = north)
j=1
if p:
if dir[2] == p: # if passing through a portal, p should not update, or else it would attempt to move in a direction it's not intended to
nextl,nextc = dir[:2]
print(nextl,nextc,l,c)
else: j = 0 # p is not 0 and no move happens (j = 0)
else: # if no portal has been used: try all possible directions
nextl, nextc, p = dir
if j:
if len(M[0]) > c >= 0 and 0 <= l < len(M): # if inbounds
if M[nextl][nextc] in D: # if the next move lands in a portal, change coordinates using the function portal()
Q.append((nextl,nextc))
nextl,nextc = portal(M,nextl,nextc)
if M[nextl][nextc] and ((nextl, nextc) not in Q) and (M[nextl][nextc] not in D):
# if there is no wall on the next position and it has not been visited yet, call dfs again for the next position
Q.append((nextl, nextc))
if dfs(Q,0):
return True
else:
Q.pop()
elif M[nextl][nextc] and (M[nextl][nextc] in D) and ((nextl, nextc) not in Q):
# if a portal has been used, the next move should keep previous p (direction). Therefore, the function call is different, to prevent it from attempting to move in all 4 directions.
Q.append((nextl,nextc))
if dfs(Q,p):
return True
else:
Q.pop()
elif M[l][c] not in D: p = 0
# resets p if no move is possible ( allows it to gain a new direction from the for loop above)
else: p = 0
M = [];L = int(input())
for _ in range(L): M.append(input().split()) # Matrix input
for i in M:
for h in i:
if h == "#": M[M.index(i)][i.index(h)] = 0
elif h == ".": M[M.index(i)][i.index(h)] = 1 # Replaces path with 1 (easier to write)
l0, c0 = (int(i) for i in input().split())
queue = [(l0, c0)] # initial position
COORD = 0
D={};lineP=-1
for LINE in M: # locates portals and assigns to the corresponding letter both coordinates
colP = -1; lineP =1
for COL in LINE:
colP =1
if COL not in ["*",0,1]:
if COL in D: D[COL].append([lineP,colP])
else: D[COL] = [[lineP,colP]]
if COL == "*": COORD=[lineP,colP] # locates the destination (marked with "*")
if dfs(queue,0):
print("Success"
else:
print("Failure")
CodePudding user response：
I created a script that finds one path that can reach goal. If the path does not exists, it prints that the task is impossible.
Note: the algorithm does not seek for all possible paths. Once it finds one, it returns that path. Consequently, it does not return the shortest path to goal. It returns a path, if it exists. Otherwise, it returns an empty list.
The return of dfs_pathfinder is a boolean, telling if the path was found or not. To retrive the path, store a list to path, and let the function fill the list passed as parameter by reference.
I tried to explain every single line of the script using comments. If you didn't understood something, or got an unexpected bug from it, feel free to post it on the comments of this answer.
# Swap rows by columns of a grid.
#
# Useful for printing on terminal only. Or, if you
# need to transpose the input grid.
def transpose(grid):
tgrid = []
ncols = range(len(grid[0]))
nrows = range(len(grid))
for j in ncols:
tgrid.append([])
for i in nrows:
tgrid[-1].append(grid[i][j])
return tgrid
# Handles the file input, loading:
# 1. The Character's starting position
# 2. The Grid itself
# 3. The Goal you want to reach
# 4. The List of Portals
def handle_input(filename):
portals = {}
goal = (-1, -1)
# Try to open the file and read all its lines
try:
file = open(filename, 'rt')
except:
print('Error: Couldn\'t open ' filename)
else:
lines = file.readlines()
file.close()
# Get the number of rows
nrows = int(lines[0][:-1])
# Mount the grid based on the file data
# Append all portals
# Find the goal's position
grid = []
for nr in range(nrows):
row = lines[nr 1][:-1].split(' ')
for co in range(len(row)):
if (row[co] != '.' and row[co] != '#' and row[co] != '*'):
if (row[co] in portals):
if (len(portals[row[co]]) == 2):
print("Warning: There are 3 portals of same kind: ", row[co])
portals[row[co]].append((nr, co))
else:
portals[row[co]] = [(nr, co)]
elif (row[co] == '*'):
goal = (nr, co)
grid.append(row)
# Retrieve the starting position
pos = lines[nrows 1][:-1].split(' ')
pos = (int(pos[0]), int(pos[1]))
# Check if the goal exists
if (goal[0] == -1 or goal[1] == -1):
print('Warning: No goal * is set')
return grid, pos, goal, portals
# Eases the way of retrieving the current tile character from the grid, given
# a position pos: (x, y)
#
# If a position outside of the grid is requested, return an empty character.
def get(grid, pos):
if (pos[0] >= 0 and pos[1] >= 0 and pos[0] < len(grid) and pos[1] < len(grid[pos[0]])):
return grid[pos[0]][pos[1]]
else:
return ''
# Each portal is a pair of positions: [(a, b), (c, d)]
#
# This means that portal1 is at (a, b)
# and portal2 is at (c, d)
#
# Calling enterPortal(portal, (a, b)) -> (c, d)
# Calling enterPortal(portal, (c, d)) -> (a, b)
def enterPortal(portal, pos):
if (portal[0][0] == pos[0] and portal[0][1] == pos[1]):
return portal[1]
else:
return portal[0]
# This function does not measures the best path. Nor, it searches all
# possible paths available to goal.
#
# It returns the first path to goal that is found. Otherwise, an empty
# path is returned, signalizing that the goal is unreachable.
def dfs_pathfinder(grid, pos, goal, portals, path, reached):
char = get(grid, pos)
reached.append(pos)
# Still walking
if (char == '.'):
# Store all movement choices
movement = [(-1, 0), (1, 0), (0, 1), (0, -1)]
# Try all movement choices
for mv in movement:
# Get a hint of next position
nextPos = (pos[0] mv[0], pos[1] mv[1])
# If the next position is not reached yet, continue
if (nextPos not in reached):
# Append current position to path
path.append(pos)
# And check if you are in the correct path
if (dfs_pathfinder(grid, nextPos, goal, portals, path, reached)):
# If you reached goal, signalize to other levels of recursion
# that you found it.
return True
else:
# If you're not, pop current position from path and try again
path.pop()
# Didn't found goal. Giving up.
return False
# Steped on portal
elif (char in portals):
# Portals are unreachable. They teleport the character.
#
# However, we do append their position into path list.
reached.pop()
# Get the other end of the current portal
other = enterPortal(portals[char], pos)
# Get previous position, which will be used to calculate
# which direction the character should face when stepping
# outside of the portal exit
prev = path[-1]
# Check which position you came from
diff = (prev[0] - pos[0], prev[1] - pos[1])
# Get position you will face when exiting the portal
# @ -> P ... O -> .
# . <- O ... P <- @
move = (-diff[0], -diff[1])
# Calculate a hint of next position on other side of the portal
nextPos = (other[0] move[0], other[1] move[1])
# If the hint position is not reached yet:
if (nextPos not in reached):
path.append(pos) # Stepped on portal
path.append(other) # Stepped on other side of portal
# Check if you're on the correct path to goal
if (dfs_pathfinder(grid, nextPos, goal, portals, path, reached)):
# You are. Signalize to other levels of recursion that you
# found the goal.
return True
else:
path.pop() # pop other side of portal
path.pop() # pop current portal
# You're wrong. Try again.
# Didn't found goal. Giving Up.
return False
# Reached goal
elif (char == '*'):
path.append(pos) # Append goal to path.
# Signalize to other levels of recursion that you found goal.
return True
# Cannot reach goal anymore. You are on a non-walkable tile.
else:
# Giving Up.
return False
if __name__ == '__main__':
# Step 1: Extract data
grid, pos, goal, portals = handle_input('file.txt')
# Step 2: Call Pathfinder
path = []
if (dfs_pathfinder(grid, pos, goal, portals, path, [])):
print("A Path was found: ", path)
else:
print("No Path was found. Task is impossible.")
# Step 3: Show the path inside the grid using counters
k = 0
for pos in path:
grid[pos[0]][pos[1]] = str(k)
k = 1
# Step 4: Print the grid and the path the character must
# go through to reach the goal
print()
grid = transpose(grid)
gout = ''
for j in range(len(grid[0])):
for i in range(len(grid)):
gout = ((' ' get(grid, (i, j)) ' ') if (len(get(grid, (i, j))) == 1) else (' ' get(grid, (i, j)) ' '))
gout = '\n'
print('The Grid: ')
print(gout)
print()
The script gets input from a file. In this case, file.txt, which contents are:
7
# # * # # # # # #
. . . . T . . . .
# # # # # # # # .
. . . T . . . . .
Q . . . . # # # #
. . . . . Q . . .
. . . # # # . . .
5 1
After testing the script, I got this output:
A Path was found: [(5, 1), (4, 1), (3, 1), (3, 2), (4, 2), (5, 2), (5, 3), (4, 3), (4, 4), (3, 4), (3, 3), (1, 4), (1, 3), (1, 2), (0, 2)]
The Grid:
# # 14 # # # # # #
. . 13 12 11 . . . .
# # # # # # # # .
. 2 3 10 9 . . . .
Q 1 4 7 8 # # # #
. 0 5 6 . Q . . .
. . . # # # . . .
The starting position is at 0 position, and 14 is the goal. The tiles 10 and 11 are both ends of the portal T, which tells that the algorithm used the portal T to reach the goal.