Re: Recursion head scratcher
Joel Madigan wrote: Hi everyone! Sorry this isn't strictly a Python question but my algorithms professor contends that given the standard recursive-backtracking maze solving algorithm: width=6 height=4 maze=[[1,0,1,1,0,1], [0,0,1,0,0,0], [1,0,1,0,1,0], [0,0,0,0,1,1]] visited = [[False for x in range(width)] for y in range(height)] sx=1 sy=2 ex=4 ey=0 def findPath(x,y): if (x 0 or x = width or y 0 or y = height): return False elif maze[y][x] == 1: return False elif visited[y][x]: return False elif (x == ex and y == ey): print (%d,%d)%(x,y), return True else: visited[y][x] = True if findPath(x-1,y) or \ findPath(x+1,y) or \ findPath(x,y-1) or \ findPath(x,y+1): print (%d,%d)%(x,y), return True else: return False print findPath(sx,sy) that it is possible to make it print the path to the finish in the order the steps were taken. That is, the algorithm as written produces: (4,0) (4,1) (3,1) (3,2) (3,3) (2,3) (1,3) (1,2) True Rather than (1,2) (1,3) (2,3) (3,3) (3,2) (3,1) (4,1) (4,0) True Furthermore, he claims it's a one line change without using a stack or any other extra data structure. But I can't figure it out to save my life. This isn't homework, there isn't credit on the line. I think he said it just to mess with us. Can anyone point me in the right direction? It's driving me crazy. The output it gives makes perfect sense, since it just prints out each step as the stack unwinds. Normally you would print the output BEFORE recursing, but in this case you only want to print the step if it is actually part of the path. And you don't know that until after the recursion. Can anyone shed some light on this? Thanks, Joel How about swapping sx,sy with ex,ey ? That's one line (one statement). And the rest of the algorithm appears to be symmetric. Basically, you're reversing time, and starting with the end point, descending till you find the start point. DaveA -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursion head scratcher
On Wed, 2009-12-02 at 02:07 -0500, Joel Madigan wrote: that it is possible to make it print the path to the finish in the order the steps were taken. That is, the algorithm as written produces: (4,0) (4,1) (3,1) (3,2) (3,3) (2,3) (1,3) (1,2) True Rather than (1,2) (1,3) (2,3) (3,3) (3,2) (3,1) (4,1) (4,0) True Furthermore, he claims it's a one line change without using a stack or any other extra data structure The way I see immediately is a three line change (if you include modifying/removing the existing print statements). It will be one line shorter to print the other order. As a hint - think of what the python interpreter's stack looks like when it's running your code at the moment - that's the stack you're currently using (and need to use) to store the results you print. Tim -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursion head scratcher
On 12/2/09, Dave Angel da...@ieee.org wrote: Joel Madigan wrote: Hi everyone! Sorry this isn't strictly a Python question but my algorithms professor contends that given the standard recursive-backtracking maze solving algorithm: width=6 height=4 maze=[[1,0,1,1,0,1], [0,0,1,0,0,0], [1,0,1,0,1,0], [0,0,0,0,1,1]] visited = [[False for x in range(width)] for y in range(height)] sx=1 sy=2 ex=4 ey=0 def findPath(x,y): if (x 0 or x = width or y 0 or y = height): return False elif maze[y][x] == 1: return False elif visited[y][x]: return False elif (x == ex and y == ey): print (%d,%d)%(x,y), return True else: visited[y][x] = True if findPath(x-1,y) or \ findPath(x+1,y) or \ findPath(x,y-1) or \ findPath(x,y+1): print (%d,%d)%(x,y), return True else: return False print findPath(sx,sy) that it is possible to make it print the path to the finish in the order the steps were taken. That is, the algorithm as written produces: (4,0) (4,1) (3,1) (3,2) (3,3) (2,3) (1,3) (1,2) True Rather than (1,2) (1,3) (2,3) (3,3) (3,2) (3,1) (4,1) (4,0) True Furthermore, he claims it's a one line change without using a stack or any other extra data structure. But I can't figure it out to save my life. This isn't homework, there isn't credit on the line. I think he said it just to mess with us. Can anyone point me in the right direction? It's driving me crazy. The output it gives makes perfect sense, since it just prints out each step as the stack unwinds. Normally you would print the output BEFORE recursing, but in this case you only want to print the step if it is actually part of the path. And you don't know that until after the recursion. Can anyone shed some light on this? Thanks, Joel How about swapping sx,sy with ex,ey ? That's one line (one statement). And the rest of the algorithm appears to be symmetric. Basically, you're reversing time, and starting with the end point, descending till you find the start point. DaveA Wow... that's devilishy clever. I can see that I still have a long way to travel on my path. Thanks for your insight. -- http://mail.python.org/mailman/listinfo/python-list
