<Spoiler Alert - Anyone at < Level 24 in Python Challenge may not want to read this post!>
I have never used generators before but I might have now found a use for them. I have written a recursive function to solve a 640x640 maze but it crashes, due to exceeding the stack. The only way around this I can think of is to use Generator but I have no idea how to.
The function is as below:
def solve_maze(x,y): if y <= 0: success = 1 elif x <= 0 or x > 640 or y >= 640: success = 0 elif maze_array[x][y] == 1: success = 0 elif im.getpixel((x,y)) == (255, 255, 255, 255): success = 0 else: maze_array[x][y] = 1 if solve_maze(x,y-1) == 1: success = 1 elif solve_maze(x+1,y) == 1: success = 1 elif solve_maze(x-1,y) == 1: success = 1 else: success = solve_maze(x,y+1)
> I have never used generators before but I might have now found a use > for them. I have written a recursive function to solve a 640x640 > maze but it crashes, due to exceeding the stack. The only way > around this I can think of is to use Generator but I have no idea > how to.
A better way is to use a queue. I had the same problem with a similar piece of code. The only thing why you're using a stack is to move to the "next" point, without going back to a visited point.
The non-recursive solution is to mark all visited points as such, only consider non-visited points, and then append the coordinates to a list of points yet to visit. Then keep looping over your code until either you found the solution to the maze or there are no points left to visit.
Sybren -- The problem with the world is stupidity. Not saying there should be a capital punishment for stupidity, but why don't we just take the safety labels off of everything and let the problem solve itself? Frank Zappa
On Wed, 9 Nov 2005, Sybren Stuvel wrote: > Ian Vincent enlightened us with:
>> I have never used generators before but I might have now found a use >> for them. I have written a recursive function to solve a 640x640 maze >> but it crashes, due to exceeding the stack. The only way around this I >> can think of is to use Generator but I have no idea how to.
> A better way is to use a queue. I had the same problem with a similar > piece of code. The only thing why you're using a stack is to move to > the "next" point, without going back to a visited point.
Exactly - using a queue means you'll do a breadth-first rather than a depth-first search, which will involve much less depth of recursion. See:
|
