Difference between revisions of "CSC111 Programs for Week 12 2015"
(→Largest, Smallest, Factorial) |
|||
Line 135: | Line 135: | ||
<br /> | <br /> | ||
<br /> | <br /> | ||
+ | =Recursively Visiting a Maze= | ||
<br /> | <br /> | ||
+ | ::<source lang="python"> | ||
+ | # graphicsVisitMaze.py | ||
+ | # D. Thiebaut | ||
+ | # Generates a maze and displays it in a graphics window. | ||
+ | # The maze is defined as a collection of lines of text. | ||
+ | # MazeText is the variable containing the raw definition. | ||
+ | # MazeText is split into lines and the list of lines is kept | ||
+ | # in the variable maze. | ||
+ | # Each line in mazeText contains # or . characters. A #-character | ||
+ | # indicates a wall, while a . indicates an empty space. | ||
+ | # MazeText is cleaned up and all the dots are replaced by spaces. | ||
+ | # Then the maze is displayed in the graphic window. | ||
+ | # The program maintains the status of the visit in the variable | ||
+ | # maze. A '.' will represent a breadcrumb, i.e. a place that has | ||
+ | # been visited and that is potentially on the path to the exit. A | ||
+ | # 'v' character indicates a visited place that leads to an impass. | ||
+ | # The program starts by visiting location STARTi (line number) | ||
+ | # and STARTj (column number). | ||
+ | # | ||
+ | import time | ||
+ | import os | ||
+ | from graphics import * | ||
+ | |||
+ | |||
+ | # Dimensions of the graphics window | ||
+ | WIDTH = 600 | ||
+ | HEIGHT = 600 | ||
+ | |||
+ | mazeText = """ | ||
+ | ######################### | ||
+ | ........................# | ||
+ | ##############.########## | ||
+ | #.#.#........#.#........# | ||
+ | #.#.#.########.########.# | ||
+ | #.#.#.................#.# | ||
+ | #.#.###.#####.#####.#...# | ||
+ | #...........#.#.#.#.##### | ||
+ | #.#########.#.#.#.#...#.# | ||
+ | #.#.#.#.#.#.#.#.#######.# | ||
+ | #.#.........#.#.......#.. | ||
+ | #.###############.#####.# | ||
+ | #...............#.......# | ||
+ | #.###########.#########.# | ||
+ | #........#..............# | ||
+ | ######################### | ||
+ | """ | ||
+ | |||
+ | mazeText1 = """ | ||
+ | ######################### | ||
+ | ........................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #........................ | ||
+ | #.......................# | ||
+ | ######################### | ||
+ | """ | ||
+ | |||
+ | mazeText2 = """ | ||
+ | ######################### | ||
+ | ........................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #######################.# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #.####################### | ||
+ | #.......................# | ||
+ | #.......................# | ||
+ | #........................ | ||
+ | #.......................# | ||
+ | ######################### | ||
+ | """ | ||
+ | |||
+ | # | ||
+ | STARTi = 1 # line number | ||
+ | STARTj = 0 # column number | ||
+ | |||
+ | NOLINES = len( mazeText.strip().split("\n") ) | ||
+ | NOCHARS = len( mazeText.strip().split("\n")[1] ) | ||
+ | BLOCKWIDTH = WIDTH // NOCHARS | ||
+ | BLOCKHEIGHT = HEIGHT / NOLINES | ||
+ | |||
+ | |||
+ | def getMazeFromFile( fileName ): | ||
+ | """reads the definition of the maze from a file""" | ||
+ | |||
+ | try: | ||
+ | lines = open( fileName, 'r' ).read() | ||
+ | except: | ||
+ | print( "I/O Error: could not open", fileName ) | ||
+ | return None | ||
+ | |||
+ | return getMaze( lines ) | ||
+ | |||
+ | def getMaze( mazeText ): | ||
+ | """take the string representing the maze and | ||
+ | break it down into an array of lines""" | ||
+ | maze=[] | ||
+ | for i, line in enumerate( mazeText.split( '\n' ) ): | ||
+ | line = line.strip() | ||
+ | #print( "%d [%s]" % (i, line ) ) | ||
+ | if len( line ) < 2: | ||
+ | continue | ||
+ | line = line.replace( '.', ' ' ) | ||
+ | maze.append( line ) | ||
+ | return maze | ||
+ | |||
+ | def setBreakCrumb( i, j, win ): | ||
+ | global BLOCKWIDTH | ||
+ | global BLOCKHEIGHT | ||
+ | radius = BLOCKWIDTH // 4 | ||
+ | brd = Circle( Point( (j+0.5)*BLOCKWIDTH, (i+0.5)*BLOCKHEIGHT ), radius ) | ||
+ | brd.setFill( "red" ) | ||
+ | brd.draw( win ) | ||
+ | |||
+ | # rest a tiny bit to slow down the program | ||
+ | time.sleep( 0.1 ) | ||
+ | |||
+ | def setImpass( i, j, win ): | ||
+ | global BLOCKWIDTH | ||
+ | global BLOCKHEIGHT | ||
+ | radius = BLOCKWIDTH // 4 | ||
+ | blk = Rectangle( Point( j*BLOCKWIDTH, i*BLOCKHEIGHT ), | ||
+ | Point( (j+1)*BLOCKWIDTH, (i+1)*BLOCKHEIGHT ) ) | ||
+ | blk.setFill( "lightgrey" ) | ||
+ | blk.setOutline( "lightgrey" ) | ||
+ | blk.draw( win ) | ||
+ | |||
+ | # rest a tiny bit to slow down the program | ||
+ | time.sleep( 0.1 ) | ||
+ | |||
+ | |||
+ | def displayMaze( maze, win ): | ||
+ | """ display the maze and wait for some amount of time""" | ||
+ | global BLOCKWIDTH | ||
+ | global BLOCKHEIGHT | ||
+ | global NOLINES | ||
+ | global NOCHARS | ||
+ | |||
+ | blocks = [] | ||
+ | for i in range (NOLINES ): | ||
+ | for j in range( NOCHARS ): | ||
+ | if maze[i][j]=="#": | ||
+ | r = Rectangle( Point( j*BLOCKWIDTH, i*BLOCKHEIGHT ), | ||
+ | Point( (j+1)*BLOCKWIDTH, (i+1)*BLOCKHEIGHT ) ) | ||
+ | r.setFill( "blue" ) | ||
+ | r.setOutline( "blue" ) | ||
+ | r.draw( win ) | ||
+ | blocks.append( r ) | ||
+ | |||
+ | return blocks | ||
+ | |||
+ | def setChar( maze, i, j, char ): | ||
+ | """puts the character char at position i, | ||
+ | j in the maze""" | ||
+ | line = maze[i] | ||
+ | letters = [] | ||
+ | for letter in line: | ||
+ | letters.append( letter ) | ||
+ | letters[j] = char | ||
+ | maze[i] = ''.join( letters ) | ||
+ | |||
+ | def visitMaze( maze, i, j, win ): | ||
+ | """recursive visit of the maze. Returns True when it | ||
+ | has found the exit, False otherwise""" | ||
+ | |||
+ | setBreakCrumb( i, j, win ) | ||
+ | setChar( maze, i, j, '.' ) | ||
+ | |||
+ | #printMaze( maze ) | ||
+ | if ( i != STARTi or j != STARTj ) \ | ||
+ | and ( (i==0 or i==len( maze )-1 ) or (j==0 or j==len( maze[0] )-1 ) ): | ||
+ | return True | ||
+ | |||
+ | #--- try the four directions around where we are --- | ||
+ | #--- to the right? --- | ||
+ | if j+1< len( maze[0] ) and maze[i][j+1]==' ': | ||
+ | if visitMaze( maze, i, j+1, win ) == True: | ||
+ | return True # found an exit by going right! | ||
+ | |||
+ | #--- down? --- | ||
+ | if i+1< len( maze ) and maze[i+1][j]==' ': | ||
+ | if visitMaze( maze, i+1, j, win ) == True: | ||
+ | return True # found an exit by going down! | ||
+ | |||
+ | #--- up? --- | ||
+ | if i-1>=0 and maze[i-1][j]==' ': | ||
+ | if visitMaze( maze, i-1, j, win ) == True: | ||
+ | return True # found an exit by going up! | ||
+ | |||
+ | #--- to the left? --- | ||
+ | if j-1>=0 and maze[i][j-1]==' ': | ||
+ | if visitMaze( maze, i, j-1, win ) == True: | ||
+ | return True # found an exit by going left! | ||
+ | |||
+ | #--- if we're here, none of the 4 directions was successful --- | ||
+ | #--- in bringing us to an exit, we have to mark our cell with-- | ||
+ | #--- a v, and return false to our caller, indicating that we--- | ||
+ | #--- couldn't find a path --- | ||
+ | |||
+ | setImpass( i, j, win ) | ||
+ | setChar( maze, i, j, 'v' ) | ||
+ | #printMaze( maze ) | ||
+ | return False | ||
+ | |||
+ | |||
+ | def main(): | ||
+ | """gets the maze, visit and display it""" | ||
+ | #maze = getMazeFromFile( 'largemaze.txt' ) | ||
+ | win = GraphWin("Maze", WIDTH, HEIGHT ) | ||
+ | win.getMouse() | ||
+ | |||
+ | maze = getMaze( mazeText ) | ||
+ | |||
+ | #printMaze( maze ) | ||
+ | blocks = displayMaze( maze, win ) | ||
+ | |||
+ | success = visitMaze( maze, STARTi, STARTj, win ) | ||
+ | |||
+ | #--- print the maze without the v-characters --- | ||
+ | #printMazeNoVs( maze ) | ||
+ | |||
+ | if success: | ||
+ | print( "A path was found!" ) | ||
+ | else: | ||
+ | print( "No path to an exit found..." ) | ||
+ | |||
+ | win.getMouse() | ||
+ | win.close() | ||
+ | |||
+ | main() | ||
+ | |||
+ | </source> | ||
<br /> | <br /> | ||
<br /> | <br /> |
Revision as of 16:43, 20 April 2015
--D. Thiebaut (talk) 07:11, 20 April 2015 (EDT)
Display Maze Recursively
- Here's a skeleton program to start with...
# drawChessboardRecursive.py # D. Thiebaut # A recursive way of drawing a chessboard from graphics import * WIDTH = 600 HEIGHT = 600 NOCELLS = 8 SIDE = WIDTH // NOCELLS drawnCells = [] # keep track of cells already drawn def drawCell( row, col, color, win ): """draws a square cell of the given color on the given row and column""" x1 = col * SIDE y1 = row * SIDE x2 = x1 + SIDE y2 = y1 + SIDE cell = Rectangle( Point( x1, y1 ), Point( x2, y2 ) ) cell.setFill( color ) cell.draw( win ) def opposite( color ): """return the opposite color of a given color, assuming that the opposite of white is black, and conversely""" if color=="white": return "black" else: return "white" def recursiveDraw( row, col, color, win ): """recursively draw a chessboard""" return def main(): win = GraphWin( "Chessboard", WIDTH, HEIGHT ) recursiveDraw( 0, 0, "white", win ) win.getMouse() win.close() main()
Largest, Smallest, Factorial
# Find largest item recursively. Find the smallest one, recursively.
# Compute the factorial of a number.
def findLargestR( L ):
"""given a list of numbers, returns the largest one."""
print( "findLargest(", L, ")" )
if len( L ) == 1:
print( "Stopping condition. largest =", L[0] )
return L[0]
first = L[0]
remainingL = L[1: ]
print( "first =", first, " remainingL=", remainingL )
largestOfRemainingL = findLargestR( remainingL )
print( "largest of remainingL is", largestOfRemainingL )
if first > largestOfRemainingL:
return first
else:
return largestOfRemainingL
def findSmallestR( L ):
"""given a list of numbers, returns the smallest one."""
print( "findSmallestR(", L, ")" )
if len( L ) == 1:
print( "Stopping condition. Smallest =", L[0] )
return L[0]
first = L[0]
remainingL = L[1: ]
print( "first =", first, " remainingL=", remainingL )
smallestOfRemainingL = findSmallestR( remainingL )
print( "smallest of remainingL is", smallestOfRemainingL )
if first < smallestOfRemainingL:
return first
else:
return smallestOfRemainingL
def fact( n ):
""" compute the factorial of a number."""
# stopping condition
if n == 1:
return 1
# recursive step
return n * fact( n-1 )
def main():
"""
L = [ 10, 3, 101, 23 ]
smallest = findSmallestR( L )
print( "largest = ", smallest )
"""
while True:
n = int( input( "> " ) )
print( "factorial of", n, "=", fact(n) )
main()
Recursively Visiting a Maze
# graphicsVisitMaze.py # D. Thiebaut # Generates a maze and displays it in a graphics window. # The maze is defined as a collection of lines of text. # MazeText is the variable containing the raw definition. # MazeText is split into lines and the list of lines is kept # in the variable maze. # Each line in mazeText contains # or . characters. A #-character # indicates a wall, while a . indicates an empty space. # MazeText is cleaned up and all the dots are replaced by spaces. # Then the maze is displayed in the graphic window. # The program maintains the status of the visit in the variable # maze. A '.' will represent a breadcrumb, i.e. a place that has # been visited and that is potentially on the path to the exit. A # 'v' character indicates a visited place that leads to an impass. # The program starts by visiting location STARTi (line number) # and STARTj (column number). # import time import os from graphics import * # Dimensions of the graphics window WIDTH = 600 HEIGHT = 600 mazeText = """ ######################### ........................# ##############.########## #.#.#........#.#........# #.#.#.########.########.# #.#.#.................#.# #.#.###.#####.#####.#...# #...........#.#.#.#.##### #.#########.#.#.#.#...#.# #.#.#.#.#.#.#.#.#######.# #.#.........#.#.......#.. #.###############.#####.# #...............#.......# #.###########.#########.# #........#..............# ######################### """ mazeText1 = """ ######################### ........................# #.......................# #.......................# #.......................# #.......................# #.......................# #.......................# #.......................# #.......................# #.......................# #.......................# #.......................# #.......................# #........................ #.......................# ######################### """ mazeText2 = """ ######################### ........................# #.......................# #.......................# #.......................# #.......................# #.......................# #.......................# #######################.# #.......................# #.......................# #.......................# #.......................# #.####################### #.......................# #.......................# #........................ #.......................# ######################### """ # STARTi = 1 # line number STARTj = 0 # column number NOLINES = len( mazeText.strip().split("\n") ) NOCHARS = len( mazeText.strip().split("\n")[1] ) BLOCKWIDTH = WIDTH // NOCHARS BLOCKHEIGHT = HEIGHT / NOLINES def getMazeFromFile( fileName ): """reads the definition of the maze from a file""" try: lines = open( fileName, 'r' ).read() except: print( "I/O Error: could not open", fileName ) return None return getMaze( lines ) def getMaze( mazeText ): """take the string representing the maze and break it down into an array of lines""" maze=[] for i, line in enumerate( mazeText.split( '\n' ) ): line = line.strip() #print( "%d [%s]" % (i, line ) ) if len( line ) < 2: continue line = line.replace( '.', ' ' ) maze.append( line ) return maze def setBreakCrumb( i, j, win ): global BLOCKWIDTH global BLOCKHEIGHT radius = BLOCKWIDTH // 4 brd = Circle( Point( (j+0.5)*BLOCKWIDTH, (i+0.5)*BLOCKHEIGHT ), radius ) brd.setFill( "red" ) brd.draw( win ) # rest a tiny bit to slow down the program time.sleep( 0.1 ) def setImpass( i, j, win ): global BLOCKWIDTH global BLOCKHEIGHT radius = BLOCKWIDTH // 4 blk = Rectangle( Point( j*BLOCKWIDTH, i*BLOCKHEIGHT ), Point( (j+1)*BLOCKWIDTH, (i+1)*BLOCKHEIGHT ) ) blk.setFill( "lightgrey" ) blk.setOutline( "lightgrey" ) blk.draw( win ) # rest a tiny bit to slow down the program time.sleep( 0.1 ) def displayMaze( maze, win ): """ display the maze and wait for some amount of time""" global BLOCKWIDTH global BLOCKHEIGHT global NOLINES global NOCHARS blocks = [] for i in range (NOLINES ): for j in range( NOCHARS ): if maze[i][j]=="#": r = Rectangle( Point( j*BLOCKWIDTH, i*BLOCKHEIGHT ), Point( (j+1)*BLOCKWIDTH, (i+1)*BLOCKHEIGHT ) ) r.setFill( "blue" ) r.setOutline( "blue" ) r.draw( win ) blocks.append( r ) return blocks def setChar( maze, i, j, char ): """puts the character char at position i, j in the maze""" line = maze[i] letters = [] for letter in line: letters.append( letter ) letters[j] = char maze[i] = ''.join( letters ) def visitMaze( maze, i, j, win ): """recursive visit of the maze. Returns True when it has found the exit, False otherwise""" setBreakCrumb( i, j, win ) setChar( maze, i, j, '.' ) #printMaze( maze ) if ( i != STARTi or j != STARTj ) \ and ( (i==0 or i==len( maze )-1 ) or (j==0 or j==len( maze[0] )-1 ) ): return True #--- try the four directions around where we are --- #--- to the right? --- if j+1< len( maze[0] ) and maze[i][j+1]==' ': if visitMaze( maze, i, j+1, win ) == True: return True # found an exit by going right! #--- down? --- if i+1< len( maze ) and maze[i+1][j]==' ': if visitMaze( maze, i+1, j, win ) == True: return True # found an exit by going down! #--- up? --- if i-1>=0 and maze[i-1][j]==' ': if visitMaze( maze, i-1, j, win ) == True: return True # found an exit by going up! #--- to the left? --- if j-1>=0 and maze[i][j-1]==' ': if visitMaze( maze, i, j-1, win ) == True: return True # found an exit by going left! #--- if we're here, none of the 4 directions was successful --- #--- in bringing us to an exit, we have to mark our cell with-- #--- a v, and return false to our caller, indicating that we--- #--- couldn't find a path --- setImpass( i, j, win ) setChar( maze, i, j, 'v' ) #printMaze( maze ) return False def main(): """gets the maze, visit and display it""" #maze = getMazeFromFile( 'largemaze.txt' ) win = GraphWin("Maze", WIDTH, HEIGHT ) win.getMouse() maze = getMaze( mazeText ) #printMaze( maze ) blocks = displayMaze( maze, win ) success = visitMaze( maze, STARTi, STARTj, win ) #--- print the maze without the v-characters --- #printMazeNoVs( maze ) if success: print( "A path was found!" ) else: print( "No path to an exit found..." ) win.getMouse() win.close() main()