How to use generators?

[Ian Vincent]

<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)

if success == 1:
print im.getpixel((x, y))

return success

#Main
wibble = solve_maze(x,y)

[Sybren Stuvel]

Re: How to use generators?

Ian Vincent enlightened us with:[color=blue]
> 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.[/color]

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

[Tom Anderson]

Re: How to use generators?

On Wed, 9 Nov 2005, Sybren Stuvel wrote:
[color=blue]
> Ian Vincent enlightened us with:
>[color=green]
>> 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.[/color]
>
> 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.[/color]

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:

http://cs.colgate.edu/faculty/nevison.pub/web102/web102S00/Notes12.htm

For details.

An extended version of this exercise would be to implement an A* search:

http://en.wikipedia.org/wiki/A-star_search_algorithm

Which might be quicker than a blind breadth-first.

tom

--
Exceptions say, there was a problem. Someone must deal with it. If you
won't deal with it, I'll find someone who will.

[Ian Vincent]

Re: How to use generators?

Tom Anderson <twic@urchin.ea rth.li> wrote in
news:Pine.LNX.4 .62.05110918534 20.25586@urchin .earth.li:[color=blue]
>
> 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:[/color]

Thanks for the answers but found a easier (admittedly cheating) way around
the problem....run the code on my 64bit Linux system at home.