Note: to do this homework, you should download Homework5.zip, then unzip it, edit the files, rezip, and submit that zipped file to Autolab.
· Include your name, AndrewID, and section clearly on the top of each file in your assignment.
· Place all your solutions in a single file ZIP file (extension.zip). Once again, start with Homework5.zip. No other file formats will be accepted. You need to start by downloading a ZIP file that contains a template (a file ending in .py) for each problem in this homework.
· Show your work. Correct answers without supporting calculations will not receive full credit.
· How to submit:
Your submission is not completed until you see that text!!!
Problem 1: Mystery code (10
points)
What do these functions do? State what each of
the following functions does in general, in just a few words of plain English.
You must identify the general pattern, and should not state line-by-line what
each step of the function does. Here is an example of the kind of answer we're
looking for:
Note: these are not necessarily the best algorithms for
solving these particular problems. Often, there are clearer and/or faster ways
to achieve the same result.
Example
def mysteryExample(x,y):
# assume x and y are positive integers
while x >= y:
x -= y
return x
Answer:
for positive integers (the assumed input), this function is equivalent to (x %
y). For full credit, you would have to provide a small explanation why this is
true. You would receive zero credit for the following answer: the function
loops while x is greater than or equal to y, subtracting y from x on each
iteration of the loop, and then returns the value of x. This is entirely
correct on a "line-by-line" level, but we want you to think more
generally in terms of the higher level algorithm that is being implemented and
so no credit would be awarded for this answer.
Problem 1.A. (3 points)
def mysteryA(n):
# Assume n is non-negative
if (n <= 0):
return 0
else:
return max(n%10, mysteryA(n/10))
Problem 1.B. (3 points)
def mysteryB(s1, a, b):
if ((a < 0) or (b <= a) or (b >= len(s1))):
return ""
else:
return mysteryB(s1, a, b-1) +
s1[b-1]
Problem 1.C. (4 points)
def
mysteryC(x, y):
if (x < 0):
return -mysteryC(-x, y)
elif (y < 0):
return -mysteryC(x, -y)
elif (x == 0 and y == 0):
return 0
else:
return 100 * mysteryC(x / 10, y / 10)
+ 10 * (x % 10) + y % 10
Problem 2: Recursion with
Folders and Files (30 points)
In this section, we will use recursion to find
some interesting properties of folders and files you might store on your
computer. To help get you started, here is a function we wrote in class
this week: listFiles(path). This recursive function takes a
string specifying a path to a folder and prints all the files in that folder
and all its subfolders. The function does not return anything.
import
os
def listFiles(path):
if (os.path.isdir(path) == False):
# base case: not a folder, but
a file, so print its path
print path
else:
# recursive case: it's a folder
for filename in os.listdir(path):
listFiles(path + "/" + filename)
To reliably test this function, it's easiest if we have the same folders
and files on our hard drives. So you can use the files in hw5TestFolder,
which is supplied in the hw5 directory (and available here: hw5TestFolder.zip).
And so:
This command:
listFiles("hw5TestFolder")
Produces this output:
hw5TestFolder/emergency.txt
hw5TestFolder/folderA/fishing.txt
hw5TestFolder/folderA/folderC/folderD/misspelled.txt
hw5TestFolder/folderA/folderC/folderD/penny.txt
hw5TestFolder/folderA/folderC/folderE/tree.txt
hw5TestFolder/folderA/folderC/giftwrap.txt
hw5TestFolder/folderA/widths.txt
hw5TestFolder/folderB/folderH/driving.txt
hw5TestFolder/folderB/restArea.txt
hw5TestFolder/mirror.txt
assert(countFiles("hw5TestFolder/folderB/folderF/folderG")
== 0)
assert(countFiles("hw5TestFolder/folderB/folderF") == 0)
assert(countFiles("hw5TestFolder/folderB") == 2)
assert(countFiles("hw5TestFolder/folderA/folderC") == 4)
assert(countFiles("hw5TestFolder/folderA") == 6)
assert(countFiles("hw5TestFolder") == 10)
To help test your code, here are some assertions for use with
hw5TestFolder:
assert(findFile("hw5TestFolder",
"fishing.txt" ) ==
"hw5TestFolder/folderA/fishing.txt")
assert(findFile("hw5TestFolder",
"tree.txt" ) ==
"hw5TestFolder/folderA/folderC/folderE/tree.txt")
assert(findFile("hw5TestFolder", "driving.txt"
) == "hw5TestFolder/folderB/folderH/driving.txt")
assert(findFile("hw5TestFolder",
"mirror.txt" ) ==
"hw5TestFolder/mirror.txt")
assert(findFile("hw5TestFolder", "noSuchFile.txt") ==
"")
Problem
3: Fractal
flowers (20 points; 5 points for simpleFlower; 15 points for fractalFlower)
A. Write
a function simpleFlower(size) that takes an integer number representing
the size of the flower. Your function will draw the following figure:
The position and
orientation of the flower will depend on the initial position and orientation
of the turtle. The origin of the flower is the bottom part of the stem, and its
length develops straight ahead on the current direction of the turtle. When
your function terminates, the turtle should be back to the same position and
the same orientation it started.
B. Write
a function fractalFlower(size, level) that takes an integer representing
the size of the flower, and an integer representing the maximum level (depth)
of recursion. Your function will paint a recursive fractal flower with the same
basic shape outlined above, but with each petal recursively replaced by a
scaled down version of the flower itself. For example, a fractal flower with a
maximum recursion level of 4 will result in a picture like this one:
Your program should
include some test code that draws three flowers, all of them facing up, on
three different positions of the screen: (a) a simple flower of size 200; (b) a
fractal flower of depth 3 and size 250; and (c) a fractal flower of depth 4 and
size 300. Your three test flowers should not overlap.
Problem 4: Fractal
Mickey Mouse (20 points; 5 points for mickeyFace; 15 points for fractalMickeyMouse)
Using Python's Tkinter library, you will
create a funny fractal cartoon character inspired by Disney's Mickey Mouse.
A. Write
a function mickeyFace(canvas, xc, yc, r) that draws a circular-shaped face
of a Mickey-like character, without ears. This function takes as input a canvas
to draw on, the (xc, yc) coordinates of the center of the face, and the radius
r of the face. The exact details of the face are up to your creativity; just
make sure it has at least two eyes, a nose, and a mouth. Hint: to draw the
mouth, you can (but you are not forced to) use the function create_arc(...) of
Tkinter. For more information about this
function see http://infohost.nmt.edu/tcc/help/pubs/tkinter/canvas.html
B. Exploiting
your previous function mickeyFace, write a function fractalMickeyMouse(canvas, xc,
yc, r, level) that recursively draws a character with the face you
previously defined, and a recursively downsized version of that same face as
ears. Your function will take as parameter a canvas to draw on, the (xc, yc)
coordinates of the center of the face, the radius r of the face, and an integer
level representing the maximum depth of recursion. The radius of each ear is
exactly half the radius of the face. Hint: if you do not manage to complete
mickeyFace on time, you can replace it with a plain circle of the correct size.
The following figure shows an example of a Fractal Mickey Mouse with maximum
recursion level (depth) of 6.
Your program should include some test code
that draws a Fractal Mickey Mouse of depth 6 on a canvas of your choice.
Problem 5: Fractal
Sun (20 points)
Using Python's Tkinter library, you will
paint a majestic fractal sun. The fractal sun is composed of a circle of radius
r, and 8 rays of length 2*r originating from the center of the circle and
radially equally spaced. The external tip of each ray is also the origin of a
recursively downsized fractal sun with radius equal to 1/4 of the radius of the
sun at the previous level. Also, the suns originating at the tip of the rays
will have different colors, i.e., the color of a sun is a function of the
recursion level of the fractal sun itself. You can invent the coloring function
you prefer, just make sure that your sun will look good no matter what the
maximum level of recursion is going to be. Your fractal sun will be generated
by a function fractalSun(canvas, xc, yc, r, level) which you will write. Your
function will take as parameter a canvas to draw on, the (xc, yc) coordinates
of the center of the sun, the radius r of the sun's circle, and an integer
level representing the maximum depth of recursion of your fractal sun.
The following picture shows a fractal sun
with a maximum recursion depth of 5, with colors fading from yellow to red.
Your program should include some test code
that draws a fractal sun of depth 5 on a canvas of your choice.
Bonus/Optional:
Problem 6: Bonus/Optional: findLargestFile (5 points)
Write the recursive function findLargestFile(path),
which takes a string path to a folder, returning the full path to the largest
file in the folder (and all its subfolders). If there are no files, the
empty string ("") is returned. Do not worry if the supplied
path is not valid or is not a folder.
Hint: to solve this, you may need the function os.path.getsize(path),
which returns the size of the given file.
To help test your code, here are some assertions for use
with hw5TestFolder:
assert(findLargestFile("hw5TestFolder/folderA")
== "hw5TestFolder/folderA/folderC/giftwrap.txt")
assert(findLargestFile("hw5TestFolder/folderB") ==
"hw5TestFolder/folderB/folderH/driving.txt")
assert(findLargestFile("hw5TestFolder/folderB/folderF") ==
"")