15-110 Fall 2010 Homework 5

Due Monday, September 27, at 10pm (no late submissions accepted!)

Note: to do this homework, you should download Homework5.zip, then unzip it, edit the files, rezip, and submit that zipped file to Autolab.

Read these instructions first!

·         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!!!

Frequently Asked Questions

Once again: Late submissions will be rejected.

Log

We want to gauge how much time you are spending in each homework and how you are using your resources. This week we are going to record your answers using an online survey.  An email with the details will be sent to you.

 

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


  1. countFiles (15 points)
    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 hw5TestFolder:

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)


  1. findFile (15 points)
    Write the recursive function findFile(path, filename), which takes a string specifying a path to a folder and a string filename, and recursively searches the folder (and all its subfolders) for a file with the given name.  If the filename is found, its full path is returned.  If the filename is not found, the empty string ("") is returned.  If the filename occurs more than once, your function still returns only one path, but can arbitrarily choose any path to the filename.   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 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") == "")