CSC111 Programs for Week 12 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()

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

# hanoi.py
# D. Thiebaut
# Program written in class.  Solves the hanoi problem,
# and moves N disks from Peg A to Peg B, using Peg C as
# an extra peg.

def moveDisks( n, source, dest, extra ):

    # stopping condition
    if n==1:
        print( "move disk from", source, "to",  dest )
        return
    
    # recursive
    moveDisks( n-1, source, extra, dest )
    moveDisks( 1, source, dest, extra )
    moveDisks( n-1, extra, dest, source )


def main():
    while True:
        n = int( input( "> " ) )
        moveDisks( n, "A", "B", "C" )

main()