Difference: MazeSearchRecursion (1 vs. 10)

Revision 102019-04-15 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="IntroToCSF2018"

LAB 8Maze SearchDepth First SearchRecursion

Changed:
<
<
>
>

Moodle   Goal

Revision 92019-04-15 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="IntroToCSF2018"

LAB 8Maze SearchDepth First SearchRecursion

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 8Maze SearchDepth First SearchRecursion

Line: 148 to 148
%ENDCODE%

What's the problem with this solution?

>
>
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 8Maze SearchDepth First SearchRecursion

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?

>
>

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 8Maze SearchDepth First SearchRecursion

Moodle   Goal

Revision 52019-03-18 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="IntroToCSF2018"

LAB 9Maze SearchDepth First SearchRecursion

Changed:
<
<
>
>
Moodle   Goal

Revision 42018-11-06 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="IntroToCSF2018"
Changed:
<
<

>
>

LAB 9Maze SearchDepth First SearchRecursion

Moodle   Goal

Revision 32018-11-05 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="IntroToCSF2018"

Maze SearchDepth First SearchRecursion

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

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

Maze SearchDepth First SearchRecursion

Moodle   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: 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. Moodle

Turn in a link to fully commented code.

 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"
>
>
 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" 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" 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" 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
>
>
 META TOPICPARENT name="IntroToCSF2018"

Maze Search 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"

Copyright © 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