CMU 15-112 Fall 2018: Fundamentals of Programming and Computer Science
Homework 10 (Due Sunday 4-Nov, at 5pm)
- Reminder: all problems that are not explicitly marked COLLABORATIVE must be completed individually, as stated in the course syllabus.
- To start:
- Create a folder named 'week10'
- Create a new file hw10.py in that folder.
- Edit hw10.py using Pyzo
- When you are ready, submit hw10.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
- Important Note: the autograder we use breaks when it tries to import tkinter. Therefore, all of your tkinter code (for fractalSunViewer() and graphics-related bonus questions) 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 all autograded problems must appear before #ignore_rest!
- Do not hardcode the test cases in your solutions.
- Note: you are not required to generate additional test cases for fractalSunViewer() but you should write test cases for each other problem.
- getCourse(courseCatalog, courseNumber) [10 pts] [autograded]
Background: for this problem, we will use a so-called courseCatalog, which for this problem is a recursively-defined list-of-lists like so (this being just an example, your solution must work for any similarly-defined courseCatalog):courseCatalog = ["CMU", ["CIT", [ "ECE", "18-100", "18-202", "18-213" ], [ "BME", "42-101", "42-201" ], ], ["SCS", [ "CS", ["Intro", "15-110", "15-112" ], "15-122", "15-150", "15-213" ], ], "99-307", "99-308" ]Each level is defined by a list, and the first element of the list is the name of that level ("CMU", "CIT", "ECE", etc). The rest of the elements of a list contain either strings, which are course names offered at that level, or lists, which contain a sub-level. So we see that "99-307" is offered by "CMU", and "15-122" is offered by "CS". Also, the fully-qualified name of a course includes the dot-separated names of all the levels that contain it, in top-down order. Thus, the fully-qualified name of "15-112" is "CMU.SCS.CS.Intro.15-112", and the fully-qualified name of "99-307" is just "CMU.99-307". Finally, you may assume that a course name may not occur more than once in a course catalog.
With this in mind, write the function getCourse(courseCatalog, courseNumber) that takes a courseCatalog, as defined above, and a courseNumber (as a string, such as "18-100" or "15-112"), and returns the fully-qualified name of the given course, or None if it is not in the catalog. For example, given the courseCatalog above, here are some test cases:assert(getCourse(courseCatalog, "18-100") == "CMU.CIT.ECE.18-100") assert(getCourse(courseCatalog, "15-112") == "CMU.SCS.CS.Intro.15-112") assert(getCourse(courseCatalog, "15-213") == "CMU.SCS.CS.15-213") assert(getCourse(courseCatalog, "99-307") == "CMU.99-307") assert(getCourse(courseCatalog, "15-251") == None) - findLargestFile(path) [15 pts] [autograded]
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 hw10p2_sampleFiles.zip):
assert(findLargestFile("sampleFiles/folderA") == "sampleFiles/folderA/folderC/giftwrap.txt") assert(findLargestFile("sampleFiles/folderB") == "sampleFiles/folderB/folderH/driving.txt") assert(findLargestFile("sampleFiles/folderB/folderF") == "")
Hint: You will almost certainly want to use a wrapper function or an optional parameter to make the problem easier to solve. This will make it easier to pass file size information back along with file names... - distList(n) [15 pts] [autograded]
Write a recursive backtracking function, distList(n), that, given a number n, returns a list of size 2n that contains all the numbers from 1 to n twice such that if x is in the list then the two xs are separated by exactly x other numbers. If such a list cannot be generated, return None.
Consider the following examples:
distList(3) returns [3, 1, 2, 1, 3, 2] distList(2) returns None distList(4) returns [4, 1, 3, 1, 2, 4, 3, 2]
Notes/Hints:- To receive credit, you must use backtracking to solve the problem, even if another approach would work.
- If you don't understand the problem, look at the examples again. Notice that the 3s always have three other numbers between them, the 2s always have two other numbers between them, etc.
- While there are multiple valid approaches to the problem, consider starting with a list of size 2n and fill it in as you go.
- flatten(lst) [10 pts] [autograded]
Write the recursive and non-destructive function flatten(lst), 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 []
- solveSudoku(board) [25 pts] [autograded]
Write the function solveSudoku(board) that takes a partially-completed Sudoku board (a 2d list with 0's representing empty cells), and returns a solved version of the same puzzle, or None if no such solution exists. You will want to make use of the code you wrote in HW5. If you never completed that code, you should meet with a TA as soon as possible to help you get that code working.
Here is a very simple testing function to help get you started. You will need to test more than this. We will be testing on boards you haven't seen before.
def testSolveSudoku(): print('Testing solveSudoku()...', end='') board = [ [ 5, 3, 0, 0, 7, 0, 0, 0, 0 ], [ 6, 0, 0, 1, 9, 5, 0, 0, 0 ], [ 0, 9, 8, 0, 0, 0, 0, 6, 0 ], [ 8, 0, 0, 0, 6, 0, 0, 0, 3 ], [ 4, 0, 0, 8, 0, 3, 0, 0, 1 ], [ 7, 0, 0, 0, 2, 0, 0, 0, 6 ], [ 0, 6, 0, 0, 0, 0, 2, 8, 0 ], [ 0, 0, 0, 4, 1, 9, 0, 0, 5 ], [ 0, 0, 0, 0, 8, 0, 0, 7, 9 ] ] solved = solveSudoku(board) solution = [ [5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8], [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 4, 5, 2, 8, 6, 1, 7, 9] ] assert(solved == solution) print('Passed!')
...and here's a board with lots of empty spaces and no solution! You may want to use this or a similar board to test the efficiency of your code. Autolab doesn't always give good feedback if your code times out. For reference, our code takes about 15 seconds to return None on this board.def testSolveSudoku2(): print('Testing solveSudoku()...', end='') board = [ [ 0, 0, 2, 0, 0, 0, 1, 0, 9 ], [ 0, 0, 0, 3, 0, 0, 2, 8, 0 ], [ 0, 0, 0, 0, 5, 0, 3, 0, 0 ], [ 0, 0, 0, 0, 0, 6, 4, 0, 0 ], [ 8, 7, 6, 5, 4, 3, 0, 2, 1 ], [ 0, 0, 0, 0, 0, 0, 6, 7, 0 ], [ 0, 0, 3, 0, 0, 0, 7, 0, 4 ], [ 0, 2, 0, 0, 1, 0, 8, 0, 0 ], [ 1, 0, 0, 0, 0, 0, 9, 0, 0 ] ] solved = solveSudoku(board) solution = None assert(solved == solution) print('Passed!')
Notes/Hints:- To receive any credit for this problem, you must solve it recursively, even if you could dream up a non-recursive solution!
- This is a backtracking problem. Study the backtracking template and backtracking examples; they will help.
- Make sure to return None as soon as you determine that a step has no solutions! Otherwise, the code might take a very long time to run.
- runFractalSunViewer() [25 pts] [manually graded]
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.
All your code for this problem should be written below the #ignore_rest line. 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.
Also below the #ignore_rest line, write the function runFractalSunViewer() that 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 your sun and not Sierpinsky Triangles). The initial depth of recursion for your suns should be 5.
The following picture shows a fractal sun with a maximum recursion depth of 5, with colors fading from yellow to red.
COLLABORATIVE PROBLEMS
SOLO PROBLEMS
BONUS PROBLEMS
- runStellaFractalViewer() [3 pts] [manually graded]
Note: This problem is pretty much runTeddyFractalViewer from last semester's HW.
Below the #ignore_rest line, write a function drawStellaFace(canvas, xc, yc, r) that draws a circular-shaped face of Prof. Rivers' dog Stella, 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. You don't need to do anything overly complex as long as it looks (sort of) like Stella. Does it have eyes, a nose and/or mouth, and approximately the right colors? If yes, you're probably good.
Hint: to draw the mouth, you might consider the function create_arc(...) of Tkinter with the optional parameters style and extent. For more information about this function read the documentation here.
Also below the #ignore_rest line, and exploiting your previous function drawStellaFace, write a function drawFractalStella(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. We don't have any examples of a Fractal Stella, but here's a picture of Real Stella and an example of a desaturated Fractal Teddy with maximum recursion level (depth) of 6. (Just... umm... imagine it's a Stella instead of a Teddy.)
Also below the #ignore_rest line, write the function runStellaFractalViewer() that behaves similarly to runFractalSunviewer, except you'll be drawing Stellas and their ears instead of suns.
Super Special Prize: If you make a great Fractal Stella, we might use it in the course notes next semester. Secure your legacy! - runKimcheeFractalViewer [3 pts] [manually graded]
Note: This problem is an extension on the Pythagoras Tree practice problem.
Prof. Taylor's axolotl Kimchee doesn't want to be left out. Read carefully, because he wants something a little different. Below the #ignore_rest line, write a function drawKimcheeFace(canvas, xc, yc, faceWidth, faceHeight) that draws an oval-shaped face of Kimchee, without gill feathers. This function takes as input a canvas to draw on, the (xc, yc) coordinates of the center of the face, and the dimensions of the face (faceWidth and faceHeight). You don't need to do anything overly complex as long as it looks (sort of) like an axolotl. Does it have eyes, a big mouth, and approximately the right colors? If yes, you're probably good. Here's a picture of him, and you can always google for more pictures of axolotls if you need inspiration:
Now for the gills. First, read about the Pythagoras Tree here. With this in mind, write the function drawGills() that creates a majestic, symmetrical set of gills for Kimchee that incorporates Pythagoras Trees in some way. You can choose how exactly they ought to look, as long as they are majestic and are drawn recursively.
Finally, below the #ignore_rest line, write the function runKimcheeFractalViewer() that behaves similarly to runFractalSunviewer, except you'll be drawing Kimchee's gills. Make sure they don't obscure his adorable face.
Another Super Special Prize: If you make a great Fractal Kimchee, we might use it in the course notes next semester. Kimchee will also appreciate you.