Problem Set 4 - Due Tue, Feb 27 at 23:59

Reading

  1. Slides and notebooks from Lec 04 Functions, Lec 05 Divide/Conquer/Glue with Pictures, Lec 06: Booleans, Logical Expressions, and Predicates and Lec 07: Conditionals You do not need (in fact, should not use material from) Lec 08 Sequences and Simple Loops
  2. Problems and solutions from Lab 03 Functions and Lab 04 Conditionals
  3. Think Python, Chapter 5: Conditionals (Secs 5.1 -- 5.7)

About this Problem Set

This problem set is intended to give you practice with conditionals and the Divide, Conquer, and Glue (DCG) problem-solving strategy.

  1. In Task 1 (individual task), you will write functions using conditionals to create a rock-paper-scissors game.
  2. In Task 2 (partner-optional task), you will make some Blob simulations using functions that involve conditionals.
  3. In Task 3 (partner-optional task), you will create quilt patterns using functions.

Unlike the previous two problem sets, this one has three tasks, and two of them are partner-optional. In Tasks 2 and 3, having a partner is optional, but strongly recommended. You can choose to work with a partner on both of the tasks, or just one of the tasks if you prefer. However, if you choose both of the tasks, you should work with the same partner on both tasks. If you want to have a partner, use this shared Google Doc. Remember, you can talk with other individuals and teams about high-level problem-solving strategies, but you cannot share any code with them.

Other notes:

All code for this assignment is available in the ps04 folder in the cs111/download directory within your cs server account. This assignment also uses the Codder program to help you do a final check of the three tasks before you submit.


Task 1: Rock, Paper, Scissors

This is an individual problem which you must complete on your own, though you may ask for help from the CS111 staff.

In this problem, you will define functions to play the game rock-paper-scissors. This is a game in which both you and your opponent each choose one of the three hand gestures rock, paper, or scissors, and the winner is chosen according to the following diagram:

Your task is to define the following five functions in the provided file named rockPaperScissors.py:

def isValidGesture(gesture):
    """Returns True if gesture is one of the strings 'rock', 'paper', or
       'scissors', and False otherwise."""
    # Flesh out the body of this function

def randomGesture():
    """Randomly returns one of 'rock', 'paper', or 'scissors',
       with equal probability."""
    # Flesh out the body of this function

def beats(gesture1, gesture2):
    """Returns True if the first gesture beats the second gesture, i.e.,
       if the first and second gesture are rock/scissors or scissors/paper,
       or paper/rock, respectively. Returns False otherwise.
       The output is unspecified if one or both gestures is invalid."""
    # Flesh out the body of this function

def play(yourGesture,opponentGesture):
    """Plays rock/paper/scissors game with your gesture vs. opponent's
       gesture. If both gestures are valid, displays one of 'Game is
       a tie!', 'You win!', or 'Opponent wins!'. Otherwise, indicates
       the first gesture that is invalid."""
    # Flesh out the rest of the body of this function

def playComputer(yourGesture):
    """Plays rock/paper/scissors with your gesture against a computer 
       opponent that randomly chooses a gesture. First displays the choice 
       of the computer, and then displays the result of the game."""
    # Flesh out the rest of the body of this function

Interactive Testing in Canopy

One way to test your functions is to first run you program in the Canopy editor window (to load the function definitions) and then enter sample calls of your functions in the interactive console to test that they work correctly. Here are some examples:

Sample Output

In []: isValidGesture('paper')
Out[]: True

In []: isValidGesture('spock')
Out[]: False

In []: randomGesture()
Out[]: 'scissors' # You might get a different result because of randomness

In []: randomGesture()
Out[]: 'rock' # You might get a different result because of randomness

In []: randomGesture()
Out[]: 'scissors' # You might get a different result because of randomness

In []: beats('paper', 'rock')
Out[]: True

In []: beats('scissors', 'rock')
Out[]: False

In []: beats('rock', 'rock')
Out[]: False

In []: play('rock', 'paper')
Opponent wins!

In []: play('rock', 'scissors')
You win!

In []: play('rock', 'rock')
Game is a tie!

In []: play('rook', 'scissors')
Your gesture (rook) is invalid

In []: play('rock', 'sissors')
Opponent's gesture (sissors) is invalid

In []: play('spock', 'sissors')
Your gesture (spock) is invalid

In []: playComputer('paper')
Computer chooses rock
You win!
# You might get different printout because of randomness

In []: playComputer('paper')
Computer chooses paper
Game is a tie!
# You might get different printout because of randomness

In []: playComputer('paper')
Computer chooses paper
Game is a tie!
# You might get different printout because of randomness

In []: playComputer('paper')
Computer chooses scissors
Opponent wins!
# You might get different printout because of randomness

In []: playComputer('rock')
Computer chooses paper
Opponent wins!
# You might get different printout because of randomness

Automatic Testing in Canopy

Interactive testing can be tedious. As an alternative, we have provided a special main conditional block at the bottom of rockPaperScissors.py that includes test cases that will be automatically run every time you run your program in Canopy. This section begins as follows

if __name__ == "__main__":
    '''All code that tests the above functions should be nested                       
       within this special "main" conditional.                                        
    '''
    print "isValidGesture('paper') -->", isValidGesture('paper')
    print "isValidGesture('spock') -->", isValidGesture('spock')
    print "\nrandomGesture() -->", randomGesture()
    print "randomGesture() -->", randomGesture()
    ... many more tests below ...

Feel free to add or comment out tests in this block as desired.

Notes


Task 2: Blob Simulator

In this problem, having a partner is optional, but is strongly recommended. If you want to have a partner, use this shared Google Doc.

This task involves a whimsical simulation system with circular objects called blobs that follow rules to move around the four quadrants of a screen. Here's a short video of this simulation in action:

We give you most of the code for this simulation system and ask to fill in a small missing part of the code that implement the rules specifying the behavior of the blobs. These rules involve using conditionals.

You need to understand what the system is supposed to do in order to complete your part of the task. Most of this task description is an explanation of the blob simulation and the code that we've provided for you, so you'll need to do a lot of reading before you can start coding.

Background

This problem uses a cs1graphics layer called quadrants that is contained within an 800x600 canvas. The (0,0) point of the quadrants layer is in center of the canvas, and there are horizontal and vertical lines going through this point that divide the quadrants layer into 4 quadrants. As usual in cs1graphics, x coordinates increase to the right, and y coordinates increase going down.

The quadrants layer hosts a whimsical simulation system in which circular blobs move around the layer. Each blob is just a colored, borderless cs1graphics circle that is contained within the quadrants layer. The reference point of a blob is it center, so we refer the x or y location of a blob, we are referring the coordinates of its center point relative to the quadrants layer.

On each step of the simulation, the blob is first moved according to the moving rules, and then might be scaled according to the scaling rules:

Moving Rules

Scaling Rules

Example

We illustrate the rules in the context of a simple system with a single purple blob with initial radius 50 and initial location (-75,25). Below we show a sequence of state snaphots of this system in which each picture of a blob on the quadrants layer is accompanied by text showing the state number and the properties of the blob, The state number also appears in magenta in the upper left corner of quadrants.

state: 0; radius=50.0; location=(-75.0,-125.0)
state 1: radius=50.0; location=(-25.0,-125.0)
state: 2: radius=100.0; location=(25.0,-125.0)
state: 3; radius=200.0; location=(125.0,-25.0)
state: 4; radius=200.0; location=(325.0,175.0)
state: 5; radius=200.0; location=(125.0,175.0)
state 6: radius=100.0; location=(-75.0,175.0)
state 7: radius=50.0; location=(-175.0,175.0)
state 8: radius=25.0; location=(-225.0,175.0)
state 9: radius=12.5; location=(-250.0,175.0)
state 10: radius=6.25; location=(-262.5,50.0)
state 11: radius=6.25; location=(-268.75,-12.5)
state 12: radius=6.25; location=(-262.5,-12.5)
state 13: radius=6.25; location=(-256.25,-12.5)
 

The Simulation

The blobSimulator.py file in the ps04 folder contains almost all of the code for simulating the behavior of blobs on the quadrant layer. Although you don't need to understand this code in detail, here we give an overview of key aspects of the code.

A blob is simply a borderless, colored circle that "lives" in a layer:

# Do not edit or change makeBlob
def makeBlob(color, radius, x, y, containingLayer):
    '''Create a new blob with the specified properties,                                                     
       and add it to the container layer. Return the blob.                                                  
    '''
    blob = Circle(radius, Point(x, y))
    blob.setFillColor(color) 
    # remove borders, which don't look good when scaled
    blob.setBorderColor('transparent') 
    containingLayer.add(blob)
    return blob

The run function runs the simulation on a given list of blobs for a specified number of steps:

# Do not edit or change run
def run(blobs, steps):
    '''Run the simulation on the given blobs for the specified number of steps'''

    # Print initial state of system                                                                         
    printSystemState(blobs)

    # Run simulation for given number of steps                                                              
    for i in range(steps):
        nextState(blobs)

The run function (and a few other functions) uses a simple loop to perform an action for every blob in a list of blobs. You are not required to understand loops for this assignment, but using loops in the simulation code simplifies it considerably.

The core part of the run function is calling the nextState function on a list of blobs. This increments the state number in the upper left corner of the quadrants layer, and updates the state of each blob according to the movement and scaling rules explained above:

# Do not edit or change nextState
def nextState(blobs):
    '''Run one step of the simulation for the given blobs'''
    incrementStateNumber() # Increment state number in the upper left corner                                
    for blob in blobs:
        update(blob)
    printSystemState(blobs)

The update function is not provided; your task is to flesh it out. See the details below.

The printSystemState function (provided) displays the current state of the simulation:

# Do not edit or change printSystemState
def printSystemState(blobs):
    '''Display the current state of the simulation for the given blobs'''
    print('-'*55)
    print('state: ' + stateLabel.getMessage())
    for blob in blobs:
        printBlob(blob)

For example, here is the initial state of a system with five test blobs:

-------------------------------------------------------
state: 0
purple blob: radius=50.0; location=(-75.0,-125.0)
cyan blob: radius=30.0; location=(10.0,-250.0)
red blob: radius=40.0; location=(300.0,150.0)
yellow blob: radius=160.0; location=(-25.0,275.0)
green blob: radius=125.0; location=(-275.0,-200.0)

The printBlob function (provided) displays the current state of a single blob. It uses several helper functions (all provided):

# Do not edit or change printBlob, blobState, blobX or blobY
def printBlob(blob):
    '''Print a line describing the current state of a blob'''
    print blobState(blob)

def blobState(blob):
    '''Returns a string describing the current state of a blob'''
    return str(blob.getFillColor()) + ' blob:'\
            + ' radius=' + str(blob.getRadius())\
            + '; location=' + '(' + str(blobX(blob))\
                            + ',' + str(blobY(blob)) + ')'

def blobX(blob):
    '''Returns x coordinate of center of blob'''
    return blob.getReferencePoint().getX()

def blobY(blob):
    '''Returns y coordinate of center of blob'''
    return blob.getReferencePoint().getY()

There is other code in blobSimulator.py for creating the quadrants layer and its enclosing canvas and adding to its upper left corner a text label that contains the current step number of the simulation. See blobSimulator.py for all the details.


Your Task

The only thing you must do in this problem is to flesh out the skeleton of the update function in blobSimulator.py so that it implements all the movement rules (Rules M1 through M4) and scaling rules (Rules S1 and S2) explained above.

def update(blob):
    """Update the state of a blob according to the movement and scaling rules                               
       in the ps04 task description.                                                                        
    """
    pass # Replace this stub with your code. 

To implement the rules, you only need to use conditional statements involving the following blob operations:

Notes:

 


Task 3: Quilts

In this problem, having a partner is optional, but is strongly recommended. If you want to have a partner, use this shared Google Doc.

The CS111 Etsy shop wants to expand the items offered on their site. Quilts would be an item that could generate a lot of revenue. Below is an example of one of the CS111 Etsy quilt designs, which we will call winter quilt.

Another example is the following, which we will call the autumn quilt:

You and several other CS111 students have been hired as interns at the CS111 Etsy shop to help design quilts. Your project is to use pictures to generate the quilt designs shown above. You'll notice that the quilts are the same except for the color scheme.

These quilts are just two sample of the quilt design. In your code, you will write functions that will take color parameters, and therefore can generate lots of different quilts, in the same pattern as above, but with color variation.

The picture.py module, which contains picture functions you have learned about in Lecture 05 and Lab 03, is provided in the ps04 folder. You may use the functions defined in that module to help create your quilts. All the functions that you will define for this problem will be in a file that you will create called ps04Quilt.py.

Your goal is to write a quilt function that takes several color parameters and returns a picture corresponding to the quilt shown above when quilt is invoked with appropriate colors. This picture is ultimately generated by combining primitive pictures created by the following two functions that you have already seen in class. They can be found in the picture.py file:

patch (c):
"""Returns a rectangular patch of color c with a
   black border that fills a given picture frame.
"""

triangles(c1,c2):
"""Returns a picture that consists of two triangles filling the
   given picture frame: a black-bordered triangle of color c1
   in the lower left corner of the frame; and a black-bordered
   triangle of color c2 in the upper right corner of the frame.
"""

For example, below are the pictures generated by some sample invocations of these functions:

patch('red') triangles('red', 'blue')

Divide, Conquer, and Glue

The key to solving the problem of defining the quilt function is to note that the picture it returns can be decomposed into smaller pictures that are used more than once in the larger picture. For example, by wishful thinking we can image that the upper right quadrant is a picture returned by a function we'll call block:

block('navy', 'lightskyblue', 'darkseagreen', 'papayawhip', 'plum', 'orchid')

The block is clearly decomposable into subquadrants of two kinds, which we've dubbed rose and diamond. Here are two roses:

rose('darkseagreen','papayawhip) rose('navy','lightskyblue')

Here are two examples of the pattern we called diamond:

diamond('plum', 'orchid', diamond('navy', 'lightskyblue',
'darkseagreen') 'darkseagreen')

Implement each of these, then combine these subproblem solutions to solve the whole quilt. How to solve these? Each of these patterns can be broken down into quadrants and those subproblems solved and combined with operations like rotation to solve the pattern.

This is an excellent illustration of the divide, conquer, and glue problem solving strategy we will use throughout this course:

  1. Divide the problem into subproblems. Here, the whole quilt problem can be solved if we can solve the problem of generating the pictures in the different quadrants and sub-quadrants.

  2. Conquer the subproblems by solving them. In this case, you'll want to solve subproblems like rose and diamond that will help solve the whole problem.

  3. Glue the solutions to the subproblems together to form the solution to the whole problem. Here, we combine four rotated versions of the picture returned by block to construct the picture returned by quilt.

But how do we solve the problems of defining the rose and diamond functions? By applying the divide, conquer, and glue strategy again! Of course, all of these functions will take appropriate color parameters.

Continue this way, decomposing each problem into smaller subproblems, until you reach problems that can be solved using our primitives (e.g., patch and triangles). For an example of this sort of decomposition, see the quilt example from Lecture 05.

Starting the Assignment

Begin by creating a file named ps04Quilt.py. As usual, your file must start with comments at the top, identifying the author(s), username(s), problem set and task number, filename, and date. Follow this format:

# Your name:                                                                          
# Your username:                                                                      
# Your partner's name (if applicable):                                                
# Your partner's username (if applicable):    
# CS111 PSO4, Task 3
# ps04Quilt.py
# Submitted: 

Remember to include the line:

from picture import *

at the top of your file, so that all of the functions in the picture.py file are available to you.

Then use incremental programming to make progress on your quilt. That is, make approximations to your quilt picture or parts of your quilt picture and use displayPic to display these pictures along the way.

You can work in one of two directions:

  1. In the bottom-up strategy, you start with smaller helper functions, like those defined in the Helper Functions section below, and build up pictures of increasing complexity, including rose and diamond, until you have correctly defined the full quilt picture.

  2. In the top-down strategy, you start by defining the quilt function in terms of the block function or the rose and diamond functions. But those are complicated, so you might put off the diamond subproblem while you work on the rose subproblem. So for testing purposes, you instead provide a so-called stub picture for the diamond function. For example, as a very crude approximation, you might define an initial version of the diamond function that returns the result of calling triangles on two of its parameters. You can then test quilt with this approximation. Then you continue the top-down descent by defining initially-crude-approximations for functions that return the quadrants of the block picture. You continue this top down process until you reach pictures that are correctly implemented by patch and triangles, at which point you now have the correct quilt function rather than just an approximation.

Colors and Parameters

There are exactly six colors used in the Winter quilt and a different six colors in the Autumn quilt. All of the colors for the Winter quilt are listed in the examples above. The Autumn quilt uses the colors in the following examples:

rose('red','gold')
rose('darkred','coral')
diaomon('darkred','coral','red')
diamond('darkorange','bisque','red')

Your top-level quilt function will take six colors as arguments and return the appropriate quilt. You get to choose the order of the six color parameters. (The quilt function will not independently be tested by Codder.)

However, you must define zero-argument functions winterQuilt and autumnQuilt that return the result of calling the quilt function on six appropriate color arguments.

def winterQuilt():
    '''Returns the first quilt with the blue-green-purple theme'''
    return quilt( ... six color arguments go here ... )

def autumnQuilt():
    '''Returns the second with the red-orange-yellow theme'''
    return quilt( ... six color arguments go here ... )

The quilt pictures returned by these functions should match the ones depicted at the beginning of this task. Codder will test the results of these two functions.

Note: Ideally, color parameters should have meaningful names, but with functions like quilt and block that take lots of (six) color parameters, it's challenging to design such names. In our solution, the main quilt function takes six parameters, which we named c1, c2, ... c6. Then in the various subfunctions, which take fewer colors, we didn't want to use the same numbers, because it might be confusing. If we think of c1 as "navy" for example, we don't want to use c1 in another function where it might mean plum. So some functions have arguments named cx, cy and cz. Of course, Python doesn't care what we call our parameters, and we can use the same parameter names in several different functions. But remember that programs are written for humans to read and only incidentally for computers to execute. Even reading our own code, we want to keep names clear in our minds.

Helper Functions

As we have seen, a general principle of computer science is Don't Repeat Yourself (DRY), which means you should avoid writing the same pattern of code more than once. If you find yourself writing the same or similar code more than once in your program, you should write functions that capture the patterns of the repeated code and invoke the functions instead.

The divide, conquer, and glue process of defining quilt naturally exposes the need for numerous auxiliary functions. Above, we have seen the block, rose, and diamond functions, which you must define. As part of working on this task, you must also define and use the following helper functions:

def bandana(c1, c2):
    """Returns a 2x2 picture with solid c1-colored patches in the lower left
       and upper right quadrants, and triangles(c1, c2) in the upper left
       and lower right quadrants."""

def lowerLeft(p):
    """Returns a picture which divides the picture space into four
       quadrants and places the given picture in the lower left quadrant.
       Nothing is in the other quadrants."""

def lowerLeftNest(p1, p2):
    """Returns a picture in which picture p2 is placed in the the lower left
       quadrant of picture p1."""

def lowerLeftNestSelf4(p):
    """Returns a picture that has four copies of picture p: one full size one, 
       and three successively smaller versions descending in the 
       lower left quadrant."""

Here is an example invocation of bandana:

bandana('red', 'blue')

Note that the lowerLeft, lowerLeftNest, and lowerLeftNestSelf4 functions take pictures as arguments, not colors. To illustrate these helper functions, suppose that pictures picP1 and picP2 are defined as:

picP1 picP2

Then here are examples of calling the lowerLeft, lowerLeftNest, and lowerLeftNestSelf4 functions with these pictures:

lowerLeft(picP1) lowerLeftNest(picP1, picP2) lowerLeftNestSelf4(picP2)

Notes:

Testing

As you implement the above required helper functions and your own helper functions, you'll want to test them! You should put the following testing code at the end of ps04Quilt.py:

# ------------------------- Testing -----------------------
if __name__ == "__main__":
    '''All code that displays pictures or prints output should be nested 
       within this special "main" header at the end of ps04Quilt.py
    '''

    closeAllPics() # Use this to close all previously created pictures.

    # Uncomment particular lines below to test your code.
    # Add more test cases for functions that you define!

    #displayPic(bandana('red', 'blue'))
    #displayPic(lowerLeft(triangles('red', 'blue')))
    #displayPic(lowerLeftNest(patch('red'), triangles('red', 'blue')))
    #displayPic(lowerLeftNestSelf4(triangles('navy', 'lightskyblue')))               

    ## Roses
    #displayPic(rose('navy', 'lightskyblue'))                                        
    #displayPic(rose('darkseagreen', 'papayawhip'))                                        
    #displayPic(rose('red','gold'))
    #displayPic(rose('darkred','coral'))

    ## Diamonds
    #displayPic(diamond('plum', 'orchid', 'darkseagreen'))                           
    #displayPic(diamond('navy', 'lightskyblue', 'darkseagreen'))                     
    #displayPic(diamond('darkred','coral','red'))
    #displayPic(diamond('darkorange','bisque','red'))

    ## Blocks
    #displayPic(block('navy', 'lightskyblue', 'darkseagreen',                        
    #                 'papayawhip', 'plum', 'orchid'))

    ## Quilts
    #displayPic(winterQuilt())
    #displayPic(autumnQuilt())

    # Extra invocations to displayPic to fix picture glitch 
    # (a simple picture is sometimes needed to have previous pictures display)
    displayPic(patch('red'))
    displayPic(patch('blue'))

Recall that in order to see your pictures, you'll need to to invoke displayPic with an argument which corresponds to the picture you want to display. As indicated in the above code, you should put all invocations of displayPic at the very end of ps04Quilt.py indented within the special header if __name__ == "__main__":

Notes:

Completing the Assignment

You should define all the helper functions specified above. In addition to that, you should define other functions that capture other patterns that appear in the quilt. It is also helpful to define local variables within your functions to give names to pictures that you generate as part of your solution.

Each of your functions should be short: no more than a few statements long (say 7 or 8). If you find yourself defining a longer function, consider how you can break it up into smaller parts (preferably in a way that permits one or more of the smaller functions to be used multiple times).

Both Quilts

Remember that your quilt function takes six colors as arguments, so you will be able to create both the winter and autumn quilts with the same function, just supplying different sets of colors.

Codder Testing

After you're satisified with testing your quilt functions in Canopy, use Codder to check that you pass all of its tests.


Task 4: Honor Code File

Your honor code submission for this pset will involve defining entering values for the variables in the honorcode.py file.


How to turn in this Problem Set

Soft-copy submission

Hard-copy submission

There is no hard copy submission. Problem set submission is entirely electronic.