CSC111 Programs for Week 12 2015
--D. Thiebaut (talk) 07:11, 20 April 2015 (EDT)
Contents
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()
Display Chessboard Recursively
# drawChessboardRecursive.py
# D. Thiebaut
# A recursive way of drawing a chessboard
#
import random
from graphics import *
WIDTH = 600
HEIGHT = 600
NOCELLS = 8
SIDE = WIDTH // NOCELLS
#visitedCells = []
def drawCell( row, col, color, win ):
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 ):
if color=="white":
#return "black"
return random.choice( ["magenta", "blue", "green", "red", "yellow" ] )
return "white"
def recursiveDraw( row, col, color, win ):
if row >= NOCELLS or col >= NOCELLS:
return
#if (row, col) in visitedCells:
# return
drawCell( row, col, color, win )
#visitedCells.append( (row,col) )
recursiveDraw( row, col+1, opposite( color ), win )
recursiveDraw( row+1, col, opposite( color ), win )
def main():
win = GraphWin( "Chessboard", WIDTH, HEIGHT )
# wait for user to click before starting drawing...
win.getMouse()
# draw the board, recursively
recursiveDraw( 0, 0, "white", win )
win.getMouse()
win.close()
main()
Towers of Hanoi
- Will be covered in class... Extremely short program!
