# Problem Set 10 - Due Tue, Dec 4 at 23:59 EST

## About this Problem Set

The goal of this problem set is to give you practice with fruitful recursion in several contexts: TurtleWorld, PictureWorld, and file system processing.

There are four tasks in this problem set:

1. In Task 1 (Individual Task), you will define a fruitful recursive function that draws a pattern using Turtle World and returns information about the pattern.

2. In Task 2 (Partner-recommended Task), you will generate quilts with a recursive pattern.

3. In Task 3 (Partner-recommended Task), you will write some testing code to figure out which of several versions of a recursive function works correctly.

4. In Task 4 (Individual Task), you will write testing code for a file traversing algorithm that you will finish working on next week.

Note that Tasks 2 and 3 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

• When you're done with the task, fill out your honor code form and follow the submission instructions to submit your pset.

• In Spring 2017, students spent these times:

• Task 1: an average of 1.6 hours (median 1.5 hours, 90th percentile 3 hours)
• Task 2: an average of 2 hours (median 2 hours, 90th percentile 3 hours)
• Task 3: task 3 is new this semester
• Task 4: task 4 is new this semester
• All code for this assignment is available in the `ps10` folder in the `cs111/download` directory within your `cs` server account.

• This assignment uses the Codder program to help you check Tasks 1 and 2.

## Task 1: Turtle Shrubs

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, 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 Lecture 19 (slides 19-40 through 19-75). 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.

## Task 2: Quilts with Recursion

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. If you work with a partner on multiple tasks in this problem set, you must work with the same partner for all tasks.

You will write a program that generates quilts like this:

The `ps10` folder contains `picture.py`, our module built upon cs1graphics where every object is a 200x200 "picture." The module includes several functions to generate and combine pictures, such as `upperRightNest` that we saw in Lec 20, Fruitful Recursion, `fourPics` and `rotations` that you saw in Lec 05, and others.

The `recursiveQuilts.py` file includes the following predefied pictures that you can use as building blocks for your patterns:

`pyTri`
`gwTri`
`redLeaves`
`greenLeaves`
`emptyPic`

Write all your code for this task in the `recursiveQuilts.py` file.

### Subtask 2a. `quadRecurse`

Define a function, `quadRecurse(pic1, pic2, levels)`, that generates the following pictures:

`quadRecurse(pyTri, gwTri, 1)`
`quadRecurse(pyTri, gwTri, 2)`
`quadRecurse(pyTri, gwTri, 3)`
`quadRecurse(pyTri, gwTri, 4)`
`quadRecurse(pyTri, gwTri, 5)`
`quadRecurse(pyTri, gwTri, 6)`

`quadRecurse(pyTri, gwTri, 0)` should be an empty picture:

#### Notes:

• Use the Divide/Conquer/Glue strategy to break the `quadRecurse` pattern into parts.

• Define as many helper functions as necessary. Some of these helper functions should themselves be recursive. In particular, you will need one or more recursive helper functions for the upper left and lower right quadrants of `quadRecurse`.

• Following the DRY (Don't Repeat Yourself) principle, your code should capture the fact that the upper left and lower right quadrants of `quadRecurse` are closely related.

• Use `fourPics` to combine pictures.

• First make sure `quadRecurse` works for `levels` arguments 0, 1, and 2. Then the rest will follow more easily.

• Uncomment the test invocations at the bottom of `recursiveQuilts.py` to test your functions. Type `closeAllPics()` in the interactive pane to close the picture canvases without crashing Canopy.

• Codder will test your pictures from both parts 2a and 2b.

### Subtask 2b. `quilt`

Now define a function, `quilt(pic1, pic2, levels)`, that generates the following pictures. `quilt` is not a recursive function, and is very short. (The function body can be written in one (rather long) line, but you may want to express it in several lines). You will need to invoke `quadRecurse`, as well as at least two of the functions from `picture.py`.

Carefully study the relationship between the patterns produced by `quadRecurse` and `quilt` for the same number of levels.

`quilt(pyTri, gwTri, 1)`
`quilt(pyTri, gwTri, 2)`
`quilt(pyTri, gwTri, 3)`
`quilt(pyTri, gwTri, 4)`

(Note: invoking `quilt` with `levels``4` may cause your program to freeze.)

`quilt(pyTri, gwTri, 0)` should be an empty picture as well.

`quilt(redLeaves, greenLeaves, 4)` generates the picture shown at the beginning of the task.

Uncomment the test invocations at the bottom of `recursiveQuilts.py` to test your functions. Type `closeAllPics()` in the interactive pane to close the picture canvases without crashing Canopy.

## Task 3: Testing Code

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. If you work with a partner on multiple tasks in this problem set, you must work with the same partner for all tasks.

Throughout the semester, we've helped you write your code by providing extensive testing code via Codder (and various test cases within the code files themselves). After CS111, however, you will be expected to write your own test cases for the code that you produce. In fact, it's often more efficient to start with the test cases, and finish writing the code later. This task provides you with some working (and some non-working) functions, and asks you to write test cases to figure out which of the provided functions work correctly. Define your test cases in the `testFindSorted.py` file in the `ps10` folder (not in the `findSorted.py` file, which you should not modify).

For this task, we have implemented quite a few different functions that are supposed to do the same thing as Python's `in` operator: figure out whether a list of strings contains a particular string or not. The catch is that the code is allowed to assume that the list is sorted, which lets it potentially work more efficiently. The `findSorted.py` file contains the attempted solutions for this problem, but not all of them work correctly. The most basic version is called `findReference` and it just takes a list of strings (`stuff`) and a string to search for (`string`) and returns True or False by using the `in` operator:

``````def findReference(stuff, string):
return string in stuff``````

Although `findReference` does not depend on the `stuff` list being sorted, the other implementations are allowed to do so, which means that all of your test cases should only specify sorted lists for input.

You do not have to change them or implement any new functions for this task. Instead, your job is to write a set of test cases (function inputs paired with expected outputs) that will allow you to figure out exactly which of the implementations are working properly. Each test case should be a tuple containing a tuple of function arguments and the expected output for that input. Because the various `findSorted` implementations take a list and a string as arguments, the arguments tuple part of each test case will be a tuple containing a list and a string. For example, a simple test case showing that for an empty list and the string `"anything"`, the function should return `False` would look like this:

``(([], "anything"), False)``

For each of the five different implementation strategies (loop, simple recursion, splitting recursion, dividing loop, and dividing recursion) there is exactly one correct implementation, so including the `findReference` reference implementation, there are exactly 6 correct implementations to find. In order to identify the correct implementations, add test cases to the `testFindSorted.py` file and run it to see which implementations pass. Keep adding test cases until there are only 6 passing functions (and make sure that you don't add any incorrect cases; `findReference` should always pass). Once you have identified the correct implementations, you're done!

#### Notes:

• You do not need to read and understand all of the implementations in order to write test cases! A few of them don't even pass the first example test case that is already given in `testFindSorted.py`. Start by defining some simple inputs and outputs that you know should be correct, based on the specification of the problem (each implementation should work the same as the `in` operator).
• A few obvious test cases should narrow the number of implementations to fewer than 10. At that point, it may be worthwhile to read through some of the implementations to see if you can figure out a test case that will cause them to fail.
• Although it is reasonable (but not required) to use a long input list for some test cases, most of your cases can use very short lists.
• If `findReference` fails on a test case, then that test case must be incorrect. Also make sure that none of your test cases supply lists that aren't sorted alphabetically (`findReference` will pass these cases, but some of the other correct implementations may not).
• You should not use `findReference` or any other function calls when defining your test cases. Just specify the values (lists, strings to search for, and expected `True`/`False` results) that you need.
• You can use the provided `reportTestResults` function to see exactly which tests a specific implementation passes or fails.
• If you're having trouble getting rid of one tricky implementation that's hard to understand, try just adding more test cases based on what you know every implementation should be able to handle.
• Make sure you include negative as well as positive test cases. If all of your test cases are supposed to return `True`, then a function that just returns `True` no matter what the input is will pass.
• The only thing you have to do for this task is define test cases in `testFindSorted.py`. You will be graded based on whether your test cases correctly eliminate all but the 6 correct implementations.

## Task 4: Preparing for File Traversal

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

Before starting this task, you should review terminology and examples from Lec 22: Recursive File Traversal.

For this task, you will write test cases for a file traversal problem that we will work on next week. For problem set 11, the first task is to write some fruitful recursive functions that can traverse directories and report the files it finds and their sizes, as well as the sizes of directories. Instead of using Codder to help us figure out if our code is working, you will create test cases this week that you can use to help write a solution next week. For many problems it's much easier to write test cases than to solve the problem, and once you have some test cases, solving the problem becomes easier because you can test your solution as you work on it. Working on test cases first like this is called "test-driven development."

### Background

The `ps10` directory contains a subdirectory `testfiles` that you will use for examples. This `testfiles` directory is similar to the `testdir` directory used in the slides and notebook of Lec 22: Recursive File Traversal.

Below is an indented list showing the entire file tree rooted at `testfiles`. The total size of all non-hidden files in this tree is 3000 bytes. The so-called hidden files are files whose names begins with a dot. These hidden files (highlighted below) are often not shown when displaying the contents of a directory, and such hidden files should be ignored by the functions you define. This is especially important, because some operating systems add hidden files to all directories (on Mac OS, every directory gets a hidden `.DS_Store` file).

• `testfiles`
• `.secret`
• `ballast.txt`
• `html`
• `img`
• `100.png`
• `200.png`
• `balance.txt`
• `small.html`
• `tiny.html`
• `hollow`
• `.hidden`
• `py`
• `small.py`
• `tiny.py`
• `txt`
• `.odd.txt`
• `hello.txt`
• `world.txt`

The `os` module supplies a function `os.path.getsize` that returns the size of a file in bytes. (You can think of "one byte" as the size of a single character, but things are actually a bit more complex than that.) For example:

``````In [1]: import os.path

In [2]: os.path.getsize('testfiles/hollow/.hidden')
Out[2]: 1000

In [3]: os.path.getsize('testfiles/html/img/100.png')
Out[3]: 995

In [4]: os.path.getsize('testfiles/txt/hello.txt')
Out[4]: 180``````

The above outputs indicated that the files `.hidden`, `100.png`, and `hello.txt` have sizes of 1000, 995, and 180 bytes, respectively.

When `os.path.getsize` is called on a directory, it returns the size of bookkeeping information associated with the directory that is unrelated to the sizes of files contained in the directory.

``````In [5]: os.path.getsize('testfiles/html')
Out[5]: 204``````

In this task, you must ignore the size of bookkeeping information associated with a directory.

Also, you must ignore hidden files entirely (use the provided `isHidden` function to check if a file counts as a hidden file).

All code for this task should be written in the provided `fileTreeSizes.py` file in the `ps10` folder.

### The Problem

On problem set 11, you will be asked to define a function called `fileTreeListWithSizes` that takes as its single argument the pathname (a string) of a file or directory relative to the current working directory. It should return a list of pairs where each pair is a tuple of

1. a pathname (relative to the current working directory); and
2. the file tree size of the file or directory with that pathname.

The pairs should be ordered such that the pair for a directory comes directly after the pairs for all directories and/or files that directory contains, and within a directory, files and directories should appear alphabetically.

No hidden files should appear in the list: if a hidden file or directory is targeted, the result should be an empty list, and if a directory containing a hidden file or directory is targeted, the entry for that file or the entries for that directory should not appear in the list at all.

For example, if we had the following file structure:

• Directory `a`
• Subdirectory `b`
• File `.hidden` -- 1000 bytes (hidden file)
• File `q.txt` -- 400 bytes
• File `z.txt` -- 30 bytes
• Subdirectory `c`
• File `hello.txt` -- 6 bytes
• File `world.txt` -- 6 bytes
• File `def.py` -- 8 bytes

The output should look like this:

``````In [0]: fileTreeListWithSizes('a/b/q.txt')
Out[0]: [('a/b/q.txt', 400)]

In [1]: fileTreeListWithSizes('a/b/.hidden')
Out[1]: []

In [2]: fileTreeListWithSizes('a/c')
Out[2]:
[('a/c/hello.txt', 6),
('a/c/world.txt', 6),
('a/c', 12)]

In [3]: fileTreeListWithSizes('a')
Out[3]:
[('a/b/q.txt', 400),
('a/b/z.txt', 30),
('a/b', 430),
('a/c/hello.txt', 6),
('a/c/world.txt', 6),
('a/c', 12),
('a/def.py', 8),
('a', 450)]``````

You do not have to implement the `fileTreeListWithSizes` function this week!

### Writing Tests

Instead of implementing `fileTreeListWithSizes`, you have to write tests for it. Each test case should specify the input and corresponding correct output as a pair. Given the file tree example above, one possible test case would be:

``````(
'a/c',
[
('a/c/hello.txt', 6),
('a/c/world.txt', 6),
('a/c', 12)
]
)``````

In the `ps10` directory, there is a `testfiles` directory that you will use to test `fileTreeListWithSizes`. Your test cases should all specify the path to a file or directory inside `testfiles` (or specify `testfiles` itself) as the input.

Use the `os.path.getsize` function (and if you find it useful, the `os.listdir` function to list files in a directory including hidden files) to discover the sizes of the various files inside of `testfiles`. Alternatively, you could use your operating system's file browser instead, but make sure you can find the exact size of each file in bytes. In either case, write down (in a text file or on paper) the paths to each file (relative to the `ps10` directory) and the size in bytes of each file (you need the exact size in bytes, not an estimate in KB or MB).

Hint: The total size for all non-hidden files in the `testfiles` directory and its subdirectories is exactly 3000 bytes. The `testfiles/html/img` folder alone accounts for 2000 bytes.

### Requirements

Once you know which files are where and how big they are, write at least the following seven test cases:

• 2 test cases that target single non-hidden files.
• 2 test cases that target directories containing only files.
• 1 test case that targets a hidden file.
• 1 test case that targets a directory containing only hidden files.
• 1 test case that targets the `testfiles` directory itself.

As specified above, each test case should be a pair including:

1. the path to the target file or directory and,
2. the list of (path, size) tuples that should be the result for that target.

You should write your test cases in the `fileTreeSizes.py` file; the length of the `testCases` list should be at least seven when you are done.

#### Notes

• Because `fileTreeListWithSizes` is not implemented yet (it just returns an empty list), most of your test cases will fail. Until next week, you will not have any feedback on whether they are correct or not, which is part of the nature of writing test cases.
• If you are worried that your test cases aren't formatted properly, run the file to check that there are no syntax errors, and look at the output from the failed cases to check that the 'expected' part of the output matches what you put in your test case.
• Make sure you understand what `fileTreeListWithSizes` is supposed to do so that you can write the correct outputs for corresponding inputs.
• This subtask is just a warm-up for Task 1 of PS11.

## 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 `shrub.py` and `fileTreeSizes.py` files in your `ps10` folder.
• Each team member should save their `recursiveQuilts.py` and `testFindSorted.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 `shrub.py`, `recursiveQuilts.py`, `testFindSorted.py`, `fileTreeSizes.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, Dec 4, 2018.
• Failure to submit your code before the deadline will result in zero credit for the code portion of ps10.