How to use generators?

Discussion in 'Python' started by Ian Vincent, Nov 9, 2005.

  1. Ian Vincent

    Ian Vincent Guest

    <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)
     
    Ian Vincent, Nov 9, 2005
    #1
    1. Advertising

  2. 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.

    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
     
    Sybren Stuvel, Nov 9, 2005
    #2
    1. Advertising

  3. Ian Vincent

    Tom Anderson Guest

    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:

    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.
     
    Tom Anderson, Nov 9, 2005
    #3
  4. Ian Vincent

    Ian Vincent Guest

    Tom Anderson <> wrote in
    news:p:
    >
    > 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:


    Thanks for the answers but found a easier (admittedly cheating) way around
    the problem....run the code on my 64bit Linux system at home.
     
    Ian Vincent, Nov 10, 2005
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Rhino
    Replies:
    4
    Views:
    5,750
    Roedy Green
    Jan 13, 2006
  2. Pavel

    Code Generators

    Pavel, May 14, 2006, in forum: Java
    Replies:
    7
    Views:
    723
    dimitar
    May 19, 2006
  3. Mark

    Memoizing Generators

    Mark, Jul 8, 2003, in forum: Python
    Replies:
    2
    Views:
    348
  4. Duncan Booth

    generators improvement

    Duncan Booth, Aug 19, 2003, in forum: Python
    Replies:
    4
    Views:
    293
    Oleg Leschov
    Aug 20, 2003
  5. John O'Hagan

    Use of generators and efficiency

    John O'Hagan, Sep 17, 2008, in forum: Python
    Replies:
    0
    Views:
    234
    John O'Hagan
    Sep 17, 2008
Loading...

Share This Page