Problem Set 9 - Due Tue, Nov 20 at 23:59 EDT

Reading

  1. Slides and notebooks from Lec 18 Introduction to Recursion, Lec 19 Turtle Recursion, and Lab 11 Recursion.
  2. Think Python, Sec. 5.8: Recursion

About this Problem Set

This problem set is intended to give you practice with recursion, in the context of printing patterns with textual characters, drawing turtle pictures, and creating cs1graphics pictures.

  1. In Task 1 (Individual Task), you will define a recursive function named hourglass that prints an hourglass shape of characters to the screen.
  2. In Task 2 (Individual Task), you will write a recursive function that draws a pattern using Turtle World.
  3. In Task 3 (Partner-recommended task), you will draw a recursive cs1graphics pattern.

Use this shared Google Doc to find a pair programming partner and record your partner.

Notes:


Task 1: Hourglasses

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

In this task, open the provided file named hourglass.py and define in it a recursive function named hourglass that prints an hourglass shape of characters to the screen. You must use recursion (no loops are allowed).

The function is invoked as hourglass(indent, width, char1, char2).

  1. indent is the number of spaces printed on the left of each line
  2. width is the maximum number of characters printed per line at the topmost and bottommost lines of the hourglass.
  3. char1 and char2 are the two characters in the hourglass. The hourglass should consist of alternating lines of each character, beginning with char1.

The top line of the hourglass shape consists of width copies of char1 and begins with no spaces. Each subsequent line has two fewer characters and begins with one more space than the previous line, until a line with just one or two characters is reached. Then the lines start growing again in the opposite order.

If width is less than or equal to zero, nothing should be printed.

The following invocations of the hourglass function produce the output shown below.

In [2]: hourglass(0, 11, '&', '%')
&&&&&&&&&&&
 %%%%%%%%%
  &&&&&&&
   %%%%%
    &&&
     %
    &&&
   %%%%%
  &&&&&&&
 %%%%%%%%%
&&&&&&&&&&&

In [3]: hourglass(0, 12, 'x', 'o')
xxxxxxxxxxxx
 oooooooooo
  xxxxxxxx
   oooooo
    xxxx
     oo
    xxxx
   oooooo
  xxxxxxxx
 oooooooooo
xxxxxxxxxxxx

In [4]: hourglass(5, 7, '*', '-')
     *******
      -----
       ***
        -
       ***
      -----
     *******

In [5]: hourglass(0, 1, 'A', 'B')
A

In [6]: hourglass(0, 2, 'C', 'D')
CC

In [7]: hourglass(4, 1, 'E', 'F')
    E

In [8]: hourglass(7, 2, 'G', 'H')
       GG

In [9]: hourglass(9, 0, 'I', 'J') # Nothing printed for this case

In [10]: hourglass(3, -17, 'K', 'L') # Nothing printed for this case

Notes:


Task 2: Drawing Ls

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

Inside the ps09 folder, open the file called drawLs.py. Within drawLs.py, you will define a new function, drawLs, so that it causes a turtle to draw a pattern of capital L letters. Your function should take two arguments:

  1. size indicates the length of the vertical edge of the L shape
  2. levels indicates the number of levels of recursion.

Each successive L is half the size of its predecessor. Below are example invocations of the drawLs function with different levels.


drawLs(200,0)

drawLs(200,1)

drawLs(200,2)

drawLs(200,3)

drawLs(200,4)

drawLs(200,5)

Details on how to draw a single L shape are shown below:

Notes:

    def run(levels):
      initializeTurtle()
      drawLs(200,levels)

 


Task 3: Shrinking Squares

This task is a Partner-recommended problem in which it is recommended that you work with a partner as part of a two-person team. Use this shared Google Doc to find a pair programming partner and record your partner

In this task, you will draw multi-colored shrinking squares patterns that look like this:

The Exercise 4 bulleye example in the Lec 18 notebook shows that recursion is a simpler way than loops to draw the nested circles pattern from PS05 Task 1A. Similarly, this task illustrates that recursion leads to an easier solution than if you used loops to create the shrinking squares pattern.

In this task, you will write code in the shrinkingSquares.py file within the ps09 folder.

All subtasks of this task are checked by Codder but you should first run and test them in Canopy.

Subtask 3a: rotated

Regardless of which approach is taken to draw the shrinking squares pattern, cycling through the colors is a challenging aspect. Here we ask you to define a helper function named rotated that returns a new list in which the element at the front is moved to the back, shifting all other elements forward by one index:

def rotated(vals):
    """
    Suppose vals is a list of values with n elements.
    Return a **new** list of n elements that contains the same values as vals
    except that the 0th value appears at the end and the index of every other
    value is shifted down by 1,

    The given list vals is **not** changed by this operation.
    """

For example:

In []: nums = range(5)

In []: nums
Out[]: [0, 1, 2, 3, 4]

In []: rotated(nums)
Out[]: [1, 2, 3, 4, 0] # a new list is returned 

In []: nums
Out[]: [0, 1, 2, 3, 4] # nums is unchanged 

In []: rotated(rotated(nums))
Out[]: [2, 3, 4, 0, 1] # another new list is returned 

In []: nums
[0, 1, 2, 3, 4] # nums is still unchanged

Notes:

def testRotated(vals):
    def rotatedNTimes(n):
        result = vals
        for i in range(n):
            result = rotated(result)
        return result
    return ['rotated {} times: {};\n      original list is now {})'.format(i, rotatedNTimes(i), vals)
            for i in range(len(vals)+2)]

For example:

In []: printNice(testRotated([0,1,2,3)
[
  ('list rotated 0 times: [0, 1, 2, 3]', 'original list is now [0, 1, 2, 3]'),
  ('list rotated 1 times: [1, 2, 3, 0]', 'original list is now [0, 1, 2, 3]'),
  ('list rotated 2 times: [2, 3, 0, 1]', 'original list is now [0, 1, 2, 3]'),
  ('list rotated 3 times: [3, 0, 1, 2]', 'original list is now [0, 1, 2, 3]'),
  ('list rotated 4 times: [0, 1, 2, 3]', 'original list is now [0, 1, 2, 3]'),
  ('list rotated 5 times: [1, 2, 3, 0]', 'original list is now [0, 1, 2, 3]')
]

Subtask 3b: drawShrinkingSquaresRow

In this subtask, you will define a function drawShrinkingSquaresRow that draws the a row of shrinking squares on a given canvas. Supposing that canv is a canvas, here are some examples:


drawShrinkingSquaresRow(canv, 400, 0, 0, 0.5, 5, ['cyan', 'magenta', 'yellow'])


drawShrinkingSquaresRow(canv, 300, 0, 0, 0.6, 5, ['yellow', 'green', 'magenta', 'cyan', 'purple'])


drawShrinkingSquaresRow(canv, 200, 0, 0, 0.75, 5, ['red', 'green', 'blue', 'magenta', 'cyan', 'yellow', 'orange', 'purple'])

Here's the contract for drawShrinkingSquaresRow:

def drawShrinkingSquaresRow(canvas, size, upperLeftX, upperLeftY,
                            shrinkFactor, minSize, colorList):
    """
    On the given canvas, add a row of colored squares aligned on their upper
    edges.

    Each square but the first has a left edge that coincides with the right edge
    of the square to its left.

    The leftmost square has an upper left corner at at (upperLeftX, upperLeftY)
    in the canvas.

    The leftmost square has side length `size`, and each other square has a side         
    length that is shrinkFactor multiplied by the side length of the square    
    immediately to its left. (Assume 0 < `shrinkFactor` < 1.)

    The smallest allowable square has side length `minSize`; no square whose side
    is less than `minSize` will be drawn.

    From left to right, the squares are colored using the colors in order from
    the list of colors `colorList`. When colors run out, they start again at the
    beginning of `colorList`.
    """

Notes:

def drawSquare(canvas, size, upperLeftX, upperLeftY, color):
    """  
    On the given canvas, add a square of the given size and color whose 
    upper left corner is at (upperLeftX, upperLeftY) in the canvas.   
    """
    halfSize = size/2.0
    centerX = upperLeftX + halfSize
    centerY = upperLeftY + halfSize
    sq = Square(size, Point(centerX, centerY))
    sq.setFillColor(color)
    canvas.add(sq)

Subtask 3c: drawShrinkingSquares

In this subtask, you will define a function drawShrinkingSquaresRow that draws the a row of shrinking squares on a given canvas. Supposing that canv is a canvas, here are some examples:


drawShrinkingSquares(canv, 400, 0, 0, 0.5, 5, ['cyan', 'magenta', 'yellow'])


drawShrinkingSquares(canv, 300, 0, 0, 0.6, 5, ['yellow', 'green', 'magenta', 'cyan', 'purple'])


drawShrinkingSquares(canv, 200, 0, 0, 0.75, 5, ['red', 'green', 'blue', 'magenta', 'cyan', 'yellow', 'orange', 'purple'])

Here's the contract for drawShrinkingSquares:

def drawShrinkingSquares(canvas, size, upperLeftX, upperLeftY, shrinkFactor,
     minSize, colorList):
    """  
    On the given canvas, add rows of colored squares, where each row is created
    by calls to `drawShrinkingSquaresRow` that use the parameters `shrinkFactor`         
    and `minSize` unchanged from `drawShrinkingSquaresRow`.

    The top left corner of the uppermost row is at coordinates       
    (upperLeftX, upperLeftY) in the canvas.      

    The rows are aligned on their leftmost edges, and the top edge of each row 
    (but the first) coincides with the bottom edge of the largest square in the
    row above it.  

    The topmost row is the created by `shrinkingSquaresRow(size, shrinkFactor, 
    minSize, colorList)`. Going downward, each row has a leftmost square whose 
    side length is `shrinkFactor` multiplied by the side length of the leftmost
    square immediately above it. Smaller rows are added until the size of the  
    biggest square in a row would be strictly less than `minSize`.   

    The color list used in a row is a version of the list from the row immediately       
    above in which the first color has been move to the end but all other colors         
    are the same.   
    """

Notes:


Honor Code Form and Final Checks

As in the previous psets, your honor code submission for this pset will involve defining entering values for the variables in the honorcode.py file.

If you wrote any function invocations or print statements in your Python files to test your code, please remove them, comment them out before you submit, or wrap them in a if __name__=='__main__' block at the end of a .py file. Points will be deducted for isolated function invocations or superfluous print statements.

It's a good idea to run Codder one last time before submission.


How to turn in this Problem Set