Problem Set 9 - Due Tue, Nov. 26, 2019 at 23:59pm
- New material: Slides and notebooks from Lec 18 File Operations, Lec 20 Recursion, Lab 11: File Operations, and Lab12: Recurison.
- Think Python, Ch. 14: Files and Think Python, Ch. 5 Section 8: Recursion
About this Problem Set
The purpose of this problem set is to give you practice with:
- Working with files
- Recursion, and how it relates to iteration.
turtlemodule for drawing.
There are four tasks:
Task 0 is the usual individual problem involving puzzles based on the problem set 8 solutions.
In Task 1 (Individual Task), you will write an iterative function to produce a multi-line hourglass string, and a related function which will read an hourglass string from a file and write a larger hourglass string to another file.
In Task 2 (Individual Task), you will write a recursive function that prints an hourglass shape like the ones you constructed in task 1.
- In Task 3 (Partner-recommended Task), you will create a recursive function that draws a branching tree-like structure, and then create a second version of that function with a customized appearance.
Use this shared Google Doc to find a pair programming partner.
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 CS 111 Code Style Guide
Based on data from Spring 2019, we expect that this assignment will take most students 3–5.5 hours, plus 1–1.5 hours of reading time. When you've been working on a task for about 1.5–2 hours, you should evaluate whether you are making efficient progress, and make use of some of the class resources available to you, like help-room hours or office hours. If you've been working on one task for 3–4 hours and still have a ways to go, you should definitely get some help with it. We have tweaked the assignment in a way that will hopefully slightly reduce the time required.
All code for this assignment is available in the
ps09folder in the
cs111/downloaddirectory within your
- For this assignment, there will be no Codder testing available: you are responsible for testing your own code.
Task 0: Scrambled Solutions
This is an individual problem which you must complete on your own, although you can ask for help from the CS111 staff.
This time we have two puzzles for you to solve to review the solutions to problem set 8. Go to:
and select the options under
Problem Set 8.
As before, please download and submit your solution files, and email
firstname.lastname@example.org if you run into trouble.
For this task you must write two functions:
buildHourglass which creates and
returns a multi-line string, and
growHourglass, which reads an hourglass file
and writes a larger hourglass to a different file. In this task and the next
task, an "hourglass" is made of alternating rows of characters like these three
******** ----- ====== %%% ||| **** $ - == %%% ||| **** ----- ====== ********
buildHourglass accepts three parameters: the size (i.e., the length of the
top and bottom rows), and the two characters to use (the first argument
specifies the character for the top and bottom rows, and the two characters
alternate every row. So for example,
buildHourglass(6, '-', '|') would
produce the following multi-line string:
------ |||| -- |||| ------
That string could also be written as (note the new line at the end):
"------\n ||||\n --\n ||||\n------\n"
In addition to filling out the
buildHourglass function in the
file, you must also fill out its docstring, describing in your own words what
the function does.
You may create the
buildHourglass function using whatever programming
techniques you wish; it does not have to use recursion. Using some kind of
loop is a natural approach to the problem.
Another way to approach building hourglass patterns is to grow them row by row
from the inside out. For this subtask, you will write a function
growHourglass that takes two parameters: an input filename and an output
filename. It must look at the hourglass inside the input file to figure out
what characters are used and how large the longest row is, and then it must
write a new hourglass into the output file that has two more rows than the
hourglass in the input file (i.e., one more row on the top and an identical
extra row on the bottom, to make the hourglass 2 characters wider).
For example, if the input file contains this hourglass:
~~~ Z ~~~
growHourglass should write the following hourglass into the output
ZZZZZ ~~~ Z ~~~ ZZZZZ
If the input file has too few rows to determine what character to use to expand
it, the hyphen character (
'-') should be used. Besides such cases, you may
assume that the input file will always contain a valid hourglass pattern.
As with the previous subtask, you need to fill in the docstring for the
growHourglass function with an explanation of what it does.
Task 2: Recursive Hourglass
For this task, you will need to write an
hourglassRecursive function which
prints an hourglass shape, just like the ones from Task 1. The
complication is that this hourglass function must be recursive!
In particular, you are not allowed to use any loops, and the
hourglassRecursive function must include a function call to itself. Remember
to think about your base case, and how the recursive case will build on the
base case one step at a time.
As with the previous functions, you must fill out the docstring for this
hourglassRecursive function takes one more parameter than
buildHourglass from Task 1 (as the first parameter): a number of
spaces to use for indentation. This parameter is important for enabling
For example, the call
hourglassRecursive(4, 7, '*', '+'), would print the
******* +++++ *** + *** +++++ *******
Task 3: Shrubs
(Use this shared Google Doc to find a pair programming partner.)
For this task, you will create a recursive
shrub function that draws a
branching pattern using
turtle graphics. Here is an example of the output:
In the shrub, everything starts with a trunk, and the first parameter of the
shrub function specifies the length of the trunk. Each branch is 80% as long
as the trunk that it branches out from, and is at a 30° angle either left or
right from the trunk orientation (so there is a 60° angle between the two
The second parameter to
shrub sets an upper limit on the total number of
branches that are drawn (although in some cases fewer branches may be drawn).
In order for this limit to be enforced, the recursive calls to
shrub must be
given smaller limit values than the original call receives.
Your job is to fill in the
shrub function in
shrub.py so that it draws the
exact shape shown above when given a trunk length of 100 and a branch limit of 63. It should also draw the following shapes for
shrub(100, 7) and
Note one more important fact: when the
shrub function is finished, the turtle
cursor ends up back in the exact position it started from. This is a critical
factor in making the recursion work properly (
shrub must be recursive and may
not use loops).
As with tasks 1 and 2, you must also fill in the docstring for the
Now that your
shrub function is working, copy your original code into a
second function called
fancyShrub. For this function, modify your code so
that the color and thickness of each shrub branch changes in different parts of
the shrub (use the
It's completely up to you how to set the color and thickness, and you are free
to change the branching angle, number of branches, and branch size as well, as
long as your function still respects the
parameters (in particular, it may not draw more than the given number of
allowed branches, although it is fine if it draws fewer branches). Your
docstring should explain how the fancy shrub is drawn. Here are some examples
of possible fancy shrubs:
Along with the code in your
shrub.py file, when your
fancyShrub function is
done, take a screenshot of it and submit a file named
what it looks like.
As long as your
fancyShrub function varies the pen width and color at
different layers of the shrub, and respects the
branchesAllowed parameters, you will get full credit for this subtask.
Honor Code Form and Final Checks
- As in the previous psets, your honor code submission for this pset will
involve entering values for the variables in the
- If you wrote any function invocations or
if __name__=='__main__'block at the end of a
.pyfile. Points will be deducted for isolated function invocations or superfluous
- Note that there are no Codder checks for this assignment: you have to test things on your own.
How to turn in this Problem Set
- Save your task 0
-solution.jsonfiles in your
- Save your
hourglassRecursive.pyfiles in your
- Each team member should save their
shrub.pyfile in their
- Save your filled-out
ps09folder as well.
- Note: It is critical that the name of the folder you submit is
ps09, and your submitted files are
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
ps09folder in your
dropfolder on the
csserver using Cyberduck by 11:59pm on Tuesday, Nov. 26, 2019.
- Failure to submit your code before the deadline will result in zero credit for PS09.