Difference: MazeSearchRecursion (1 vs. 10)

Revision 102019-04-15 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="IntroToCSF2018"

LAB 8
Maze Search
Depth First Search
Recursion

Changed:
<
<
Due: April 16
>
>
Due: April 18
 
Moodle
Screenshot_20181104_184118.png Screenshot_20181104_184141.png

Goal

Revision 92019-04-15 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="IntroToCSF2018"

LAB 8
Maze Search
Depth First Search
Recursion

Line: 126 to 126
 def isEnd(maze,r,c): "return true if r,c is the end (E)"
Deleted:
<
<
def getDirs(maze,r,c): "return list of directions that are spaces (["U","R","D","L"])"
 def randomWalk(maze): r=1 c=1
Line: 158 to 153
 
DFS(maze,row,col)
   If maze[row][column] is an "E" return True

Changed:
<
<
Mark location with a "." while there is an adjacent cell that has not been visited Pick a random adjacent cell at (newR, newC) that is either a " " or "E" Call DFS(maze,newr,newc) if DFS returns a True, return True
>
>
If maze[row][column] is not a space or "S" return False maze[row][column] = "." for each direction dir in (U,R,D,L) if DFS(maze,newr,newc) return True
  return false

Revision 82019-04-09 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="IntroToCSF2018"

LAB 8
Maze Search
Depth First Search
Recursion

Line: 148 to 148
 %ENDCODE%

What's the problem with this solution?

Added:
>
>
End of Day 2: https://repl.it/@JimSkon/MakeMazeDay2
 

Part 4 - A depth first search using recursion

Let's try something else. Image you have a loaf of bread. Before moving that way you set down a piece of bread so you remember where you have been. You pick an open direction (a way without a wall or a piece of bread) and go that way. You then do the same thing again, you put down a piece of bread, pick an open direction, and go that way. The bred keeps you from doubling back. eventually you reach a dead end. At this point you follow the bread along the way you came, until you see an open direction, and then explore that way. This later process is know of as "backtracking". Along the way, you keep you eye out for a "E", and if you find it, you have succeeded. If you don't, eventually you will have searched everywhere, and you declare the maze "unsolvable".

Revision 72019-04-09 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="IntroToCSF2018"

LAB 8
Maze Search
Depth First Search
Recursion

Line: 84 to 85
 %ENDCODE%

Finish the function, and try it with increasing values for the number of steps. What happens when you get to the edge of the the matrix, and go over it?

Added:
>
>

Day 2 start:

https://repl.it/@JimSkon/MazeDay2

 

Part 3 - Random walk the Maze

Let's try to random walk an actual maze. We can start with a fork of: https://repl.it/@JimSkon/MakeMaze

Revision 62019-03-24 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="IntroToCSF2018"
Changed:
<
<

LAB 9
Maze Search
Depth First Search
Recursion

Due: April 11
>
>

LAB 8
Maze Search
Depth First Search
Recursion

Due: April 16
 
Moodle
Screenshot_20181104_184118.png Screenshot_20181104_184141.png

Goal

Revision 52019-03-18 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="IntroToCSF2018"

LAB 9
Maze Search
Depth First Search
Recursion

Changed:
<
<
Due: Nov 15
Moodle
>
>
Due: April 11
Moodle
 
Screenshot_20181104_184118.png Screenshot_20181104_184141.png

Goal

Revision 42018-11-06 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="IntroToCSF2018"
Changed:
<
<

Maze Search
Depth First Search
Recursion

Due: Nov 27
>
>

LAB 9
Maze Search
Depth First Search
Recursion

Due: Nov 15
 
Moodle
Screenshot_20181104_184118.png Screenshot_20181104_184141.png

Goal

Revision 32018-11-05 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="IntroToCSF2018"

Maze Search
Depth First Search
Recursion

Line: 180 to 179
 If you replace the "." with R+"."+X, it will be leave a trail of red periods as you return to the beginning.

Screenshot_20181104_183057.png

Added:
>
>

Screenshot_20181104_194908.png

 

Moodle

Turn in a link to fully commented code.

Line: 191 to 191
 
META FILEATTACHMENT attachment="Screenshot_20181104_183057.png" attr="" comment="" date="1541374288" name="Screenshot_20181104_183057.png" path="Screenshot_20181104_183057.png" size="14223" user="JimSkon" version="1"
META FILEATTACHMENT attachment="Screenshot_20181104_184118.png" attr="" comment="" date="1541374963" name="Screenshot_20181104_184118.png" path="Screenshot_20181104_184118.png" size="11391" user="JimSkon" version="1"
META FILEATTACHMENT attachment="Screenshot_20181104_184141.png" attr="" comment="" date="1541374963" name="Screenshot_20181104_184141.png" path="Screenshot_20181104_184141.png" size="17446" user="JimSkon" version="1"
Added:
>
>
META FILEATTACHMENT attachment="Screenshot_20181104_194908.png" attr="" comment="" date="1541378964" name="Screenshot_20181104_194908.png" path="Screenshot_20181104_194908.png" size="79219" user="JimSkon" version="1"

Revision 22018-11-04 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="IntroToCSF2018"
Changed:
<
<

Maze Search

Screenshot_20181103_213358.png
>
>

Maze Search
Depth First Search
Recursion

Due: Nov 27
Moodle
Screenshot_20181104_184118.png Screenshot_20181104_184141.png
 

Goal

Using recursion to solve a maze.

Line: 143 to 145
 What's the problem with this solution?

Part 4 - A depth first search using recursion

Changed:
<
<
Let's try something else. Image going along, picking a direction, until you get stuck (or find the "E"). Then you go back to a previous branchpoint, and try from there.
>
>
Let's try something else. Image you have a loaf of bread. Before moving that way you set down a piece of bread so you remember where you have been. You pick an open direction (a way without a wall or a piece of bread) and go that way. You then do the same thing again, you put down a piece of bread, pick an open direction, and go that way. The bred keeps you from doubling back. eventually you reach a dead end. At this point you follow the bread along the way you came, until you see an open direction, and then explore that way. This later process is know of as "backtracking". Along the way, you keep you eye out for a "E", and if you find it, you have succeeded. If you don't, eventually you will have searched everywhere, and you declare the maze "unsolvable".

Consider the following algorithm for arecursive Depth First Search (DFS)

DFS(maze,row,col)
   If maze[row][column] is an "E" return True
   Mark location with a "."
   while there is an adjacent cell that has not been visited
        Pick a random adjacent cell at (newR, newC) that is either a " " or "E"
        Call DFS(maze,newr,newc)
        if DFS returns a True, return True
    return false

Try this algorithm out a few times.

Write the DFS algorithm in your maze program, and get it working. You will end up with something like this:

Screenshot_20181104_181738.png

Part 5 - Marking the path

Look at the solved Maze above. Notice how it includes false as well as successful paths. How can we see the actual path the led to the end? What if as you "return" back, at each level, place a different color marker?

Do the following, when you find the "E", before you return, change the "." below you to red. How can we do this? Following two character codes will help:

<-- SyntaxHighlightingPlugin -->
R = '\033[31m' # red
X = '\033[0m' # reset
<-- end SyntaxHighlightingPlugin -->

The string R will change subsequent letters to red, and the string X will change back to what it was (there are other color codes here: http://www.siafoo.net/snippet/88 )

If you replace the "." with R+"."+X, it will be leave a trail of red periods as you return to the beginning.

Screenshot_20181104_183057.png

Moodle

Turn in a link to fully commented code.

Solution

 
META FILEATTACHMENT attachment="Screenshot_20181103_213358.png" attr="" comment="" date="1541295330" name="Screenshot_20181103_213358.png" path="Screenshot_20181103_213358.png" size="13495" user="JimSkon" version="1"
Added:
>
>
META FILEATTACHMENT attachment="Screenshot_20181104_181738.png" attr="" comment="" date="1541373476" name="Screenshot_20181104_181738.png" path="Screenshot_20181104_181738.png" size="11946" user="JimSkon" version="1"
META FILEATTACHMENT attachment="Screenshot_20181104_183057.png" attr="" comment="" date="1541374288" name="Screenshot_20181104_183057.png" path="Screenshot_20181104_183057.png" size="14223" user="JimSkon" version="1"
META FILEATTACHMENT attachment="Screenshot_20181104_184118.png" attr="" comment="" date="1541374963" name="Screenshot_20181104_184118.png" path="Screenshot_20181104_184118.png" size="11391" user="JimSkon" version="1"
META FILEATTACHMENT attachment="Screenshot_20181104_184141.png" attr="" comment="" date="1541374963" name="Screenshot_20181104_184141.png" path="Screenshot_20181104_184141.png" size="17446" user="JimSkon" version="1"

Revision 12018-11-04 - JimSkon

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="IntroToCSF2018"

Maze Search

Screenshot_20181103_213358.png

Goal

Using recursion to solve a maze.

Part 1 - Make a maze

Consider the Maze above. Can you find a path from the S to the E? Try it and come up with a written set of instructions on how you do it.

Can we write a program to do this?

Consider the following repl.it that generates a random maze like the one above: https://repl.it/@JimSkon/MakeMaze

Note that the maze generating has the maze code in a separate file, makemaze.py.

Play around with the program. the command maze=createMaze(16,8,2) creates a maze. What do the parameters?

Part 2 - Random Walk

How can we try to make a program to solve a given maze? Let's start out with a random walk.

The following code creates a matrix of "." (periods). And prints it. Try it out. Make sure you understand it.

<-- SyntaxHighlightingPlugin -->
def makeMatrix(h,w):
  "Make a h,w matrix of spaces"
  m=[]
  row=["."]*w
  for i in range(h):
    m.append(row[:])
  return(m)

def printMatrix(maze):
  "Print out a maze"
  for i in range(len(maze)):
    for j in range(len(maze[i])):
      print(maze[i][j],end="")
    print()
<-- end SyntaxHighlightingPlugin -->

We want to be able to start from a point on the matrix, and put a "*" there. from ther we move either to the right, up, left, or down, and put the next "*". In thi way we "walk" across the matric, making a path. We need to be able to pick a random direction, and go that way. How can we do that?

Now consider code to take a position (row, column) in the grid, and a direction "U","R","D","L", and return a row and column. See how it works in repl.it:

<-- SyntaxHighlightingPlugin -->
def goDir(dir,r,c):
  "given U, R. D, L, return the coordinates for that cell"
  if dir=="U":
    return r-1,c
  elif dir=="R":
    return r,c+1
  elif dir=="D":
    return r+1,c
  elif dir=="L":
    return r,c-1
  else:
    print("goDir error:",dir)
  return r,c
<-- end SyntaxHighlightingPlugin -->

Now write code to start from a point, and "walk" a random path:

<-- SyntaxHighlightingPlugin -->
def randomWalk(m,r,c,steps):
  "Random walk through a matrix"
  "m is the matrix, r,c are where to start"
  "Steps - how many steps to take"
  # Pick a random direction
  # and set r, c to the new location
  # and put a "*"
  m[r][c]="*"
  printMatrix(m)
  for i in range(steps):
    # Pick a random direction
    # and set r, c to the new location
    # and put a "*
    printMatrix(m)

w=20
h=20
mat = makeMatrix(w,h)
randomWalk(mat,10,10,100)
<-- end SyntaxHighlightingPlugin -->

Finish the function, and try it with increasing values for the number of steps. What happens when you get to the edge of the the matrix, and go over it?

Part 3 - Random walk the Maze

Let's try to random walk an actual maze. We can start with a fork of: https://repl.it/@JimSkon/MakeMaze

What you will need to do is create a maze. Set the start location to the "S" in the maze (1,1). Write a function

<-- SyntaxHighlightingPlugin -->
from makemaze import createMaze
import random

def goDir(dir,r,c):
  "given U, R. D, L, return the coordinates for that cell"
  if dir=="U":
    return r-1,c
  elif dir=="R":
    return r,c+1
  elif dir=="D":
    return r+1,c
  elif dir=="L":
    return r,c-1
  else:
    print("goDir error:",dir)
  return r,c

def printMaze(maze):
  "Print out a maze"
  for i in range(len(maze)):
    for j in range(len(maze[i])):
      print(maze[i][j],end="")
    print()

def isOpen(maze,r,c):
  "return true if r,c is open (space)"
  

def isEnd(maze,r,c):
  "return true if r,c is the end (E)"


def getDirs(maze,r,c):
  "return list of directions that are spaces (["U","R","D","L"])"


def randomWalk(maze):
  r=1
  c=1
  dirs=getDirs(maze,r,c)
  while len(dirs)>0:  # while there is a open adjacent space
     # pick a direction
     # go in that direction (place a "." there)
     # print the update maze
     # stop is you have nowhere to go, or reach the "E"
  
maze=createMaze(10,10,1)
printMaze(maze)
randomWalk(maze)
printMaze(maze)
<-- end SyntaxHighlightingPlugin -->

What's the problem with this solution?

Part 4 - A depth first search using recursion

Let's try something else. Image going along, picking a direction, until you get stuck (or find the "E"). Then you go back to a previous branchpoint, and try from there.

META FILEATTACHMENT attachment="Screenshot_20181103_213358.png" attr="" comment="" date="1541295330" name="Screenshot_20181103_213358.png" path="Screenshot_20181103_213358.png" size="13495" user="JimSkon" version="1"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback