In just a few words of plain English (in your hw5.txt file), state what each of the following functions does in general. You will receive no credit for describing the line-by-line low-level behavior of the code. For example:
def mystery(list):
count = 0
for value in list:
if (value == 0):
count += 1
return count
Correct answer: "This function returns the number of 0's in the given list." Or, if you prefer to be succinct, just: "number of 0's".
Incorrect answer (no points): "This function sets count to 0, then sets value to each element in list in turn, and for each value, if it is 0, it adds one to count, and then returns count". This is all true, but completely misses the high-level behavior of the function, and so would receive zero points.
-
def f(n):
# assume n is a non-negative integer
if (n < 10):
return 1
else:
return 1 + f(n/10)
-
def f(a):
# assume a is a list of strings
if (len(a) == 0):
return ""
else:
x = f(a[1:])
if (len(x) > len(a[0])):
return x
else:
return a[0]
-
def f(a):
# assume a is a list of integers
if (len(a) == 0):
return 0
elif (len(a) == 1):
return (a[0] % 2)
else:
i = len(a)/2
return f(a[:i]) + f(a[i:])
-
def f(n):
# assume n is a non-negative integer
if (n == 0):
return 1
else:
return 2*f(n-1)
-
def f(n):
# assume n is a non-negative integer
if (n == 0):
return 0
else:
return f(n-1) + 2*n - 1
# Hint: you may want to try this function with a few sample values.
# The answer should quickly become apparent, though you may wish to
# think about why the answer is in fact what it is.
- permutations
[15 pts]
In the file hw5.py, write the recursive function permutations(a, k), which modifies the recursive permutations function from the course notes so that it returns all the permutations of length k from the elements in the list a, or the empty list [] if no such permutations exist. For example, permutations([1,2,3,4], 2) would return some ordering of this list:
[[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]
We say "some ordering" because your list must include the correct permutations, but in any order. And, once again, your solution must be recursive, and in fact it must be an obvious adaptation of the code in the course notes.
For your testing purposes, it might be helpful to use Pythons built-in permutations function. For example, this might be helpful (it generates the solution above):
import itertools
a = [1,2,3,4]
print [list(x) for x in itertools.permutations(a, 2)]
Hint: do not worry about the case where the original list contains duplicate values.
Note: regarding efficiency, your code should compute the 870-item result to permutations(range(30), 2) almost instantly, and the 117,600-item result to permutations(range(50),3) with at most a couple of seconds delay.
Most solutions that are not efficient enough will run much too long on these examples. The reason: generally, one way or another, they will create lots of "extra" permutations and then slice, pop, or remove their way down to the required size. For example, this modification of the permutation code is not acceptable:def permutations(a, k): # inefficient version that uses permutations code from class, unmodified, # and then, assuming len(a)>=k, uses only first k elements of each permutation, # ignoring the rest (which is not ok). This also produces some duplicates, # so either have to remove all the duplicates at the end (which is also not ok), # or add an expensive O(n) check inside our loop to check if a permutation # is already in our list (which is also not ok). result = [ ] allPerms = allPermutations(a) for fullLengthPerm in allPerms: perm = fullLengthPerm[0:k] # not ok: essentially "removes" (n-k) elements if perm not in result: # also not ok result += [perm] print "len(allPerms) = ", len(allPerms) print "len(result) = ", len(result) return resultdef allPermutations(a): # renamed permutations code from class notes # returns a list of all permutations of the list a if (len(a) == 0): return [[]] else: allPerms = [ ] for subPermutation in allPermutations(a[1:]): for i in xrange(len(subPermutation)+1): allPerms += [subPermutation[:i] + [a[0]] + subPermutation[i:]] return allPermsWhy is this unacceptable? Well, say we are finding permutations(range(9), 2). The answer contains 72 permutations of two numbers each. However, the code above will generate all 362,880 permutations of length 9 to find these 72 permutations. This huge amount of extra work makes it intractable to use this code to compute permutations(range(30),2), let alone permutations(range(50),3). Try it, if you want to wait a very, very long time!
Big Hint: one way to solve this is to modify the permutations code from class to take a second parameter, k, and to return all the permutations of a that are no larger than length k. This still requires a non-recursive wrapper function (like above) that drops all the permutations that are not of length k, but since we never produce any permutations larger than length k, this is much, much faster than the code above.
- flatten [15
pts]
In the file hw5.py, write the recursive function flatten(a), which takes a list which may contain lists (which themselves may contain lists, and so on), and returns a single list (which does not contain any other lists) which contains each of the non-lists, in order, from the original list. This is called flattening the list. For example:
flatten([1,[2]]) returns [1,2]
flatten([1,2,[3,[4,5],6],7]) returns [1,2,3,4,5,6,7]
flatten(['wow', [2,[[]]], [True]]) returns ['wow', 2, True]
flatten([]) returns []
flatten([[]]) returns []
flatten(3) returns 3 (not a list)
In this section, we will use recursion to find some interesting properties of folders and files you might store on your computer. For some context, you should refer to the printFiles and listFiles examples from this week's course notes. As with the course notes, the examples here use sampleFiles.zip.
Hint: you may not use the os.walk function in these problems (in case you know what that does). In essence, you are writing your own specialized recursive versions of that very function.
- countFiles [15
pts]
In the file hw5.py, write the recursive function countFiles(path), which takes a string specifying a path to a folder and returns the total number of files in that folder (and all its subfolders). Do not count folders (or subfolders) as files. Do not worry if the supplied path is not valid or is not a folder.To help test your code, here are some assertions for use with sampleFiles:
assert(countFiles("sampleFiles/folderB/folderF/folderG") == 0)
assert(countFiles("sampleFiles/folderB/folderF") == 0)
assert(countFiles("sampleFiles/folderB") == 2)
assert(countFiles("sampleFiles/folderA/folderC") == 4)
assert(countFiles("sampleFiles/folderA") == 6)
assert(countFiles("sampleFiles") == 10)Note: regarding efficiency, it is overtly inefficient to create a list of any kind in your solution to this problem. In particular, you may not do this:
def countFiles(path):
return len(listFiles(path))
- findLargestFile [15
pts]
In the file hw5.py, 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.
Another hint: if it is more convenient, findLargestFile can be non-recursive so long as it calls a recursive helper function.To help test your code, here are some assertions for use with sampleFiles:
assert(findLargestFile("sampleFiles/folderA") ==
"sampleFiles/folderA/folderC/giftwrap.txt")
assert(findLargestFile("sampleFiles/folderB") ==
"sampleFiles/folderB/folderH/driving.txt")
assert(findLargestFile("sampleFiles/folderB/folderF") == "")
Note: regarding efficiency, it is overtly inefficient to call os.path.getsize(path) more than once for any given file. One way to manage this is to use a helper function that not only returns the largest file for a given path, but returns it in a tuple along with other information that may be of use (hint, hint). Then findLargestFile is a non-recursive wrapper function that calls that helper function.
-
mickeyFace [10
pts]
In the file hw5-mickey.py, 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. While you need not be pixel-perfect, try to make the face as close as possible to the one in the image below (in part B). Hint: to draw the mouth, you should use the function create_arc(...) of Tkinter. For more information about this function see http://infohost.nmt.edu/tcc/help/pubs/tkinter/canvas.html
-
fractalMickeyMouse
[15 pts]
Also in the same file hw5-mickey.py, and 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. The following figure shows an example of a Fractal Mickey Mouse with maximum recursion level (depth) of 6.
Your file hw5-mickey.py should include a run() function which, when executed, behaves similarly to the Sierpinsky Triangle example in the course notes, where pressing arrows changes the depth of the recursion (though of course here you'll display recursive Mickey Mouses and not Sierpinsky Triangles).
- American Flag [2.5 pts]
In the file hw5-bonus-usflag.py, write a Tkinter program that draws an American Flag. Your program should ask the user for the width and height of the window, and display a window of that size, filled entirely with a US Flag (don't worry if the window is not "flag-shaped" -- you are not responsible for how your flag looks in that case). Your stars must match the pattern in the US flag. For that, it may help to notice that there seems to be an outer rectangle of stars, and within it an inner rectangle of stars. On the other hand, you may safely ignore that last sentence and draw the flag however you wish!
-
Motion Aftereffect [5
pts]
In the file hw5-bonus-aftereffect.py, write a Tkinter program which demonstrates the Motion Aftereffect as shown in the animation on this page. Actually, you are only responsible for the motion in the circle, and not for displaying the image (the Buddha). You also do not need any buttons or to respond to any keypresses -- just play the animation. You may wish to look into the canvas.create_arc method.
-
Arbitrary Fractal (in Turtle)
[2.5 pts]
In the file hw5-bonus-fractal.py, write a Turtle program which demonstrates an arbitrary (recursive, obviously) fractal of your choosing. You will be awarded points for style, finesse, and sheer beauty. This is only worth 2.5 points, so don't invest hundreds of hours into it. Even so, we are hoping to see some very interesting and compelling submissions. Plus, we aren't just doling out free points here, so you really have to do something interesting to earn some points. Have fun!