# Problem Set 10 - Due Friday, May 3 at 23:59 EST

The goal of this problem set is to give you practice with nonfruitful and fruitful recursion in the context of printing patterns with textual characters, drawing turtle pictures, and creating `cs1graphics` pictures.

There are four tasks in this problem set:

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 recursive L-shaped pattern using Turtle World.

3. In Task 3 (Partner-recommended Task), you will define a fruitful recursive function that draws a shrub pattern using Turtle World and returns information about the pattern.

4. In Task 4 (Partner-recommended Task), you will generate a recursive `cs1graphics` pattern and return information about the pattern.

Note that Tasks 3 and 4 are both partner-recommended tasks. You may choose to work with a partner on one or both tasks, but you may not work with two different partners on the different tasks. Use this shared Google Doc to find a partner for this pset.

Notes:

• The CS111 Problem Set Guide gives an overview of psets, including a detailed description of individual and partner tasks.

• Follow the style guidelines in the CS111 Code Style Guide

• In Spring 2018, students spent the following times (in hours) on the tasks in this pset:

Task Average Median 25% took more than 10% took more than
Task 1 1.4 1.0 1.5 2.0
Task 2 1.9 1.4 2.0 3.0
Task 3 1.6 1.5 2.0 3.0

Task 4 is a new problem, so we don't have any estimated times for it.

• All code for this assignment is available in the `ps10` folder in the `cs111/download` directory within your `cs` server account.

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:

• Unlike many of the recursion examples seen in class, `hourglass` has more than one base case.

• Although Codder will run all of the above tests for you, it is important to test and debug in Canopy

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:

• If you see an error message mentioning `wxNSApplication`, it means that your PyLab backend in Canopy is set to `Interactive (wx)`. In order to run Turtle examples, you need to set your PyLab backend to `Inline (SVG)` by following the instructions here.
• Your `drawLs()` function must be recursive (no loops allowed).
• You may (but are not required to) define a helper function to solve this problem. (You should not need more than one.)
• The `drawLs()` function must be invariant with respect to the turtle's heading and position.
• Use floating point numbers when dividing so as not to lose precision. Failure to to this can generate images that appear wrong in Codder.
• The provided `initializeTurtle` function inside `drawLs.py`, sets up the canvas and puts the turtle in a good starting position for drawing all the Ls. The provided `run` function takes a levels argument and invokes `initializeTurtle` before calling `drawLs` with this number of levels:
``````    def run(levels):
initializeTurtle()
drawLs(200,levels)``````
• The `drawLs.py` file ends with the test invocation `run(3)` that tests the pattern with a `levels` argument of 3. To test your program at a different number of levels, either (1) change the `3` in `run(3)` to the desired number in `drawLs.py` and re-reun the program or (2) invoke `run` directly in the Canopy interaction pane with a different number.
• There is currently a bug in Canopy that makes it necessary to restart Canopy in order to close the turtle window. However, it is not necessary to close the turtle window to test your program for a different `levels` number. Just invoke `run` again.
• When testing your function, consider slowing the turtle down using `speed(1)` instead of `speed(0)` (the fastest speed) within `initializeTurtle` to get a better sense as to precisely what the turtle is doing.

This task is a partner-recommended problem in which it is strongly recommended that you work with a partner as part of a two-person team. If you work with a partner on multiple tasks in this problem set, you must work with the same partner for all tasks. Use this shared Google Doc to find a partner for this pset.

In this task, you'll write a fruitful recursive function named `shrub` that draws a tree pattern with a turtle and returns a tuple of values (see below for details). Your `shrub` function should be invariant with respect to the turtle's position and direction. Define your function in the `shrub.py` file in the `ps10` folder.

A turtle shrub is a variation of the turtle tree in Lec 22 More Recursion

It is created by the `shrub` function, which takes four parameters in order:

1. `trunkLength`: the length of the branch at the base of the shrub.
2. `angle`: the angle relative to the trunk for the right and left branches
3. `shrinkFactor`: the trunk of the right branch is `shrinkFactor` times `trunkLength`, and the trunk of the left branch is `shrinkFactor*shrinkFactor` times `trunkLength`
4. `minLength`: the minimum branch length in the shrub.

The `shrub` function returns a pair (a tuple with two elements) of:

1. The total number of branches in the shrub, including the trunk
2. The total length of branches in the shrub, including the trunk

Below are sample invocations of the `shrub` function, with the magenta text indicating the value returned by the invocation, i.e., the number of branches in the shrub:

`shrub(100, 15, 0.8, 60)` -> (4, 308.0)
`shrub(100, 15, 0.8, 50)` -> (7, 461.6)
`shrub(100, 15, 0.8, 10)` -> (232, 3973.9861913600025)
`shrub(100, 30, 0.82, 10)` -> (376, 6386.440567704483)
`shrub(200, 90, 0.75, 10)` -> (232, 5056.675148010254)

#### Notes:

• If you see an error message mentioning `wxNSApplication`, it means that your PyLab backend in Canopy is set to `Interactive (wx)`. In order to run Turtle examples, you need to set your PyLab backend to ```Inline (SVG)``` by following the instructions here.

• Solve this problem in parts:

1. First draw the correct picture without worrying about the returned values.

2. Then modify the code to return only the correct number of branches.

3. Then modify it to return only the correct total branch length.

4. Only after solving all of the above subparts should you modify `shrub` to return the correct tuple.
• For examples of turtle functions that return results (including tuples), see the fruitful recursion notebook solutions (Solutions to Exercises 5, 6, and 7).

• Python has a tuple assigment feature for assigning the elements of a tuple to a tuple of variables that is particuarly helpful in this problem. For example, the invocation `shrub(100, 15, 0.8, 60)` returns the tuple `(4, 308.0)`. The tuple assignment

`numBranches, branchLen = shrub(100, 15, 0.8, 60)`

simultaneously assigns `4` to the variable `numBranches` and `308.0` to the variable `branchLen`. For more information, see Sec. 12.2 on Tuple Assignment in the Think Python book and also see the `spiralTuple` solution to Exercise 7 in the fruitful recursion notebook solutions

• Your `shrub` function should calculate both tuple elements in a single pass of drawing the tree. It should not draw the tree more than once.

• Your `shrub` function should not use any global variables to calculate the tuple elements.

• Use the provided `testShrub` and `testShrubPrint` functions to test `shrub`. `testShrub` initializes the screen and turtle for drawing the shrub from the middle bottom of the screen. As shown in the following image, it also (1) displays the invocation and result in the title bar (blue box) and (2) displays the result next to the turtle (red box).

`testShrub` also returns the result of calling `shrub`. `testShrubPrint` is like `testShrub`, but additionally prints the invocation and result to the console window.

• Codder will test both your shrub picture and the returned values.

This task is a partner-recommended problem in which it is strongly recommended that you work with a partner as part of a two-person team. If you work with a partner on multiple tasks in this problem set, you must work with the same partner for all tasks. Use this shared Google Doc to find a partner for this pset.

In this task, you will use `cs1graphics` to draw multi-colored recursive squares patterns that look like this:

You should start this problem by reviewing the cs1graphics recursion examples from the end of the Notebook in Lec 20 Introduction to Recursion.

You will write all code for this task in the `recursiveSquares.py` file within the `ps10` folder.

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

### Subtask 4a: `recursiveSquares`

In this subtask, you will define a nonfruitful function `recursiveSquares` that draws the recursive squares pattern but does not return any result. The `recursiveSquares` function has the following function header:

``````def recursiveSquares(canvas, patternSide, upperLeftX, upperLeftY,
minSide, color1, color2, color3):``````

Here is the meaning of the parameters, which are further illustrated in the eight examples in the table following the bullet points.

• `canvas` is a provided `cs1graphics` canvas on which the pattern should be displayed. This is similar to the the `canvas` parameter in the `drawTarget` and `drawNestedCircles` exercises in the Notebook for Lec 20 Introduction to Recursion.

• `patternSide` is the side length of the square area that contains the entire pattern of recursive squares. The big square in the upper left quadrant has side length `patternSide/2`. In general, smaller versions of the recursive squares pattern fill the other three quadrants.

• `upperLeftX` and `upperLeftY` are the X and Y coordinates of the upper left corner of the square area containing the entire pattern of recursive squares.

• `minSide` is the smallest value of `patternSide` for which a nonempty pattern will be drawn. If `patternSide` is strictly less than `minSide`, `recursiveSquares` will draw nothing.

• `color1` is the color of the square in the upper left corner of the pattern.

• Colors `color2` and `color3` are two other colors that are used in the recursive subpatterns. To understand how they are used, carefully study the examples in the following table.
`recursiveSquares(canv,512,0,0,600,`
`'red','blue','cyan')`
`recursiveSquares(canv,512,0,0,512,`
`'red','blue','cyan')`
`recursiveSquares(canv,512,0,0,256,`
`'red','blue','cyan')`
`recursiveSquares(canv,512,0,0,128,`
`'red','blue','cyan')`
`recursiveSquares(canv,512,0,0,64,`
`'red','blue','cyan')`
`recursiveSquares(canv,512,0,0,32,`
`'red','blue','cyan')`
`recursiveSquares(canv,512,0,0,16,`
`'red','blue','cyan')`
`recursiveSquares(canv,512,0,0,8,`
`'red','blue','cyan')`

#### Notes:

• In order to draw a square, use this `drawSquare` helper function, which has been defined for you:

``````def drawSquare(canvas, sideLength, upperLeftX, upperLeftY, color):
"""
On the given canvas, add a square of the given side length and color whose
upper left corner is at (upperLeftX, upperLeftY) in the canvas.
"""
halfSide = sideLength/2
centerX = upperLeftX + halfSide
centerY = upperLeftY + halfSide
sq = Square(sideLength, Point(centerX, centerY))
sq.setFillColor(color)
• Use the Divide/Conquer/Glue strategy and wishful thinking to define `recursiveSquares`. In particular, use the concrete examples in the above table to design the the three recursive calls to `recursiveSquares` within the general case of the definition of `recursiveSquares`. First focus on making sure that `recursiveSquares` works for the first examples in the table. Then the rest will follow more easily.

• It is very helpful to define a local variable `halfSide` that is half of `patternSide`, because this value is used several times in the body of `recursiveSquares`.

• Uncomment the test invocations of `testRecursiveSquares` in the `if __name__=="__main__":` block to test your function. This will draw each test pattern in a separate canvas whose title indicates the arguments to the invocation.

• To close all open canvases, use `closeAllCanvases()`. This is commented out at the end of the `if __name__=="__main__":` block.

• You can also use Codder to check your pictures.

### Subtask 4b: `recursiveSquaresCount`

In this subtask you will define a fruitful function named `recursiveSquaresCount` that takes the same arguments and draws the same pattern as `recursiveSquares` from Subtask 4a but also returns the total number of squares drawn in the pattern. For example, in the following table, the number after the `=>` in each invocation of `recursiveSquaresCount` shows the integer that should be returned.

`recursiveSquaresCount(canv,512,0,0,600,`
`'red','blue','cyan') => 0`
`recursiveSquaresCount(canv,512,0,0,512,`
`'red','blue','cyan') => 1`
`recursiveSquaresCount(canv,512,0,0,256,`
`'red','blue','cyan') => 4`
`recursiveSquaresCount(canv,512,0,0,128,`
`'red','blue','cyan') => 13`
`recursiveSquaresCount(canv,512,0,0,64,`
`'red','blue','cyan') => 40`
`recursiveSquaresCount(canv,512,0,0,32,`
`'red','blue','cyan') => 121`
`recursiveSquaresCount(canv,512,0,0,16,`
`'red','blue','cyan') => 364`
`recursiveSquaresCount(canv,512,0,0,8,`
`'red','blue','cyan') => 1093`

#### Notes:

• Begin this problem by copying a working definition of `recursiveSquares` from Subtask 4a and changing all occurrences of `recursiveSquares` to `recursiveSquaresCount`. Then use variable assignment to name the result of the three recursive calls to `recursiveSquaresCount`, and combine these appropriately to return the correct result for `recursiveSquaresCount`.

• You are not allowed to call `recursiveSquares` in your definition of `recursiveSquaresCount`.

• You are not allowed to use any helper functions (other than `drawSquare`) in your definition of `recursiveSquaresCount`.

• You are not allowed to use any global variables to count the number of squares drawn by `recursiveSquaresCount`.

• Your definition `recursiveSquaresCount` should draw each square only once.

• Uncomment the invocations of `testRecursiveSquaresCount` in the `if __name__=="__main__":` block to test your function. In addition to drawing each pattern in a separate canvas, `testRecursiveSquaresCount` will:

• Show the result of the call in the canvas title.
• Print the invocation and its result in the console
• You can also use Codder to check the picture drawn and result value for `recursiveSquaresCount`.

### Subtask 4c: `recursiveSquaresCountColors`

In this subtask you will define a fruitful function named `recursiveSquaresCountColors` that takes the same arguments and draws the same pattern as `recursiveSquares` from Subtask 4a but also returns a triple (i.e., a 3-element tuple) with these three components:

1. The number of squares in the pattern drawn with `color1`;

2. The number of squares in the pattern drawn with `color2`;

3. The number of squares in the pattern drawn with `color3`.

For example, in the following table, the number after the `=>` in each invocation of `recursiveSquaresCount` shows the triple of integers that should be returned.

`recursiveSquaresCountColors(canv,512,0,0,600,`
`'red','blue','cyan') => (0, 0, 0)`
`recursiveSquaresCountColors(canv,512,0,0,512,`
`'red','blue','cyan') => (1, 0, 0)`
`recursiveSquaresCountColors(canv,512,0,0,256,`
`'red','blue','cyan') => (1, 1, 2)`
`recursiveSquaresCountColors(canv,512,0,0,128,`
`'red','blue','cyan') => (6, 4, 3)`
`recursiveSquaresCountColors(canv,512,0,0,64,`
`'red','blue','cyan') => (11, 13, 16)`
`recursiveSquaresCountColors(canv,512,0,0,32,`
`'red','blue','cyan') => (46, 40, 35)`
`recursiveSquaresCountColors(canv,512,0,0,16,`
`'red','blue','cyan') => (111, 121, 132)`
`recursiveSquaresCountColors(canv,512,0,0,8,`
`'red','blue','cyan') => (386, 364, 343)`

#### Notes:

• Begin this problem by copying a working definition of `recursiveSquares` from Subtask 4a and changing all occurrences of `recursiveSquares` to `recursiveSquaresCountColors`. Then, for each of the three recursive calls to `recursiveSquaresCountColors`, use tuple assignment to name the three color components of the call. Finally combine all the color count information in a triple that is returned by `recursiveSquaresCountColors`.

• This problem is an excellent example of Divide/Conquer/Glue problem solving and wishful thinking. In particular, start by assuming that each recursive call to `recursiveSquaresCountColors` on a smaller problem returns the correct results. How do you glue together those results to create the returned triple for the big problem?

• You are not allowed to call `recursiveSquares` or `recursiveSquaresCount` in your definition of `recursiveSquaresCountColors`.

• You are not allowed to use any helper functions (other than `drawSquare`) in your definition of `recursiveSquaresCountColors`.

• You are not allowed to use any global variables to count the number of squares of a particular color drawn by `recursiveSquaresCount`.

• Your definition `recursiveSquaresCountColors` should draw each square only once.

• Uncomment the invocations of `testRecursiveSquaresCountColors` in the `if __name__=="__main__":` block to test your function. In addition to drawing each pattern in a separate canvas, `testRecursiveSquaresCountColors` will:

• Show the result of the call in the canvas title.
• Print the invocation and its result in the console
• You can also use Codder to check the picture drawn and result value for `recursiveSquaresCountColors`.

## Task 5: 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

• Save your final `hourglass.py` and `drawLs.py` files in your `ps10` folder.
• Each team member should save their `shrub.py` and `recursiveSquares.py` files in their `ps10` folder.
• Save your filled-out `honorcode.py` file in `ps10` folder as well.
• Note: It is critical that the name of the folder you submit is `ps10`, and your submitted files are `hourglass.py` and `drawLs.py`, `shrub.py`, `recursiveSquares.py`, and `honorcode.py`. In other words, do not rename the folder that you downloaded, do not create new files or folders, and do not delete or re-name any of the existing files in this folder. Improperly named files or functions will incur penalties.
• Drop your entire `ps10` folder in your `drop` folder on the `cs` server using Cyberduck by 11:59pm on Tuesday, May 3, 2019.
• Failure to submit your code before the deadline will result in zero credit for the code portion of ps10.