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")
Advertisement
Answer
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
.