CMU 15-112 Summer 2018: Fundamentals of Programming and Computer Science
Homework 13 (Due Mon 30-Jul, at 5pm)
- This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.
- To start:
- Create a folder named 'week5'
- Edit hw13.py using Pyzo
- When you are ready, submit hw13.py to Autolab. For this homework you will have 20 submissions.
- This homework is partially autograded.
- Do not hardcode the test cases in your solutions.
- This homework may be graded for style.
- Important Note: The autograder we use breaks when it tries to import tkinter. Therefore, all of your tkinter code must be included after a comment that reads #ignore_rest. The autograder will only grade code that appears before #ignore_rest. This means that your solutions to findLargestFile must appear before #ignore_rest, and runHFractalViewer must appear after.
- findLargestFile(path) [30 pts]
Without using os.walk, write the recursive function findLargestFile(path), which takes a string path to a folder and returns the full path to the largest file in the folder (and all its subfolders). You can compute the size of a file using os.path.getsize(path). If there are no files, the empty string ("") is returned. You do not need to handle the case where the supplied path is not valid or is not a folder, and you may handle ties however you wish.
Note that file systems can be very large, so in this problem, efficiency is important! Therefore, you may not use listFiles to gather all the files into one place, and you should avoid calling os.path.getsize on a single file more than once.
To help test your code, here are some assertions for use with sampleFiles (available in hw13_sampleFiles.zip):
assert(findLargestFile("sampleFiles"+os.sep+"folderA") == "sampleFiles"+os.sep+"folderA"+ \ os.sep+"folderC"+os.sep+"giftwrap.txt") assert(findLargestFile("sampleFiles"+os.sep+"folderB") == "sampleFiles"+os.sep+"folderB"+ \ os.sep+"folderH"+os.sep+"driving.txt") assert(findLargestFile("sampleFiles"+os.sep+"folderB"+ \ os.sep+"folderF") == "")
Hint: You may want to write a helper function to do most of the work for you.
- friendsOfFriends(d) [25 pts]
This function is not recursive. Background: we can create a dictionary mapping people to sets of their friends. For example, we might say:d = { } d["spongebob"] = set(["sandy", "patrick", "mr.krabs", "squidward"]) d["mr.krabs"] = set(["pearl", "spongebob", "squidward"]) d["pearl"] = set(["mr.krabs"]) d["sandy"] = set(["spongebob", "patrick"]) d["patrick"] = set(["spongebob", "sandy"]) d["squidward"] = set()With this in mind, write the function friendsOfFriends(d) that takes such a dictionary mapping people to sets of friends and returns a new dictionary mapping all the same people to sets of their friends of friends. For example, since Spongebob is a friend of Patrick, and Squidward is a friend of Spongebob, Squidward is a friend-of-friend of Patrick. This set should exclude any direct friends, so Sandy does not count as a friend-of-friend of Patrick (since she is simply a friend of Patrick) despite also being a friend of Spongebob's.
Thus, in this example, friendsOfFriends should return:{ 'spongebob': {'pearl'}, 'mr.krabs': {'patrick', 'sandy'}, 'pearl': {'spongebob', 'squidward'}, 'sandy': {'mr.krabs', 'squidward'}, 'patrick': {'mr.krabs', 'squidward'}, 'squidward': set(), }Note 1: your function should not modify the initial provided dictionary!
Note 2: you may assume that everyone listed in any of the friend sets also is included as a key in the dictionary.
Note 3: you may assume that a person will never be included in their own friend set. You should also not include people in their own friends-of-friends sets!
Note 4: you may not assume that if Person1 lists Person2 as a friend, Person2 will list Person1 as a friend! Sometimes friendships are only one-way. =( - hFractal() [25 pts]
Background: First, read about the H-Fractal here. Also, be sure to study the Sierpinksy Triangle example from the notes, particularly how it allows the user to use the arrow keys to move up and down to different recursive levels of the fractal.
With this in mind, below the #ignore_rest line, write the function hFractal() that takes no parameters and uses our animation framework (so calls the run() function) to implement an "H-Fractal viewer", that starts by viewing a "level 0 H-Fractal", and allows the user to use the arrow keys to move up and down to view different recursive levels of the H-Fractal.
Hint: The H that is drawn right in the middle should always have the same size (the width and height should be half the window width and height). At each level, we draw new H's with half the dimensions of the previous level. This is why the window size never has to change (since 1 + 1/2 + 1/4 + 1/8 + ... = 2).
- dotsGalore 2.0 [25 pts]
Using our animation framework and assuming that run() is already written, write init(data), mousePressed(event, data), keyPressed(event, data), and redrawAll(data) for an animation with the following elements:- Every 2 seconds, a dot appears on the canvas in a random position with a random direction that can be up, down, left, or right. It has a random radius between 5-50 and a random color from an assortment of any colors you choose.
- If the dot runs into the wall, it wraps around and re-appears on the other side.
- If two dots collide, they bounce off of each other.
- If you click inside a dot, it is removed from the canvas.
- If the user presses "p", the entire game is paused. The dots stop moving, no dots are added, and the user cannot click.
- If the user presses "r", all of the dots reverse their directions. Dots that were moving up now move down, dots that were moving right now move left, etc.
- Every 10 seconds, all of the dots grow by 5 pixels.
Note: Sometimes, dots will spawn on top of other dots and they will vibrate back and forth. This is okay. You do not need to handle this case.