CMU 15-112 Fall 2018: Fundamentals of Programming and Computer Science
Homework 10 (Due Sunday 4-Nov, at 5pm)





    COLLABORATIVE PROBLEMS


  1. 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)

  2. 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...

  3. 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:
    1. To receive credit, you must use backtracking to solve the problem, even if another approach would work.
    2. 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.
    3. While there are multiple valid approaches to the problem, consider starting with a list of size 2n and fill it in as you go.


  4. SOLO PROBLEMS


  5. 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 []
    

  6. 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.

  7. 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.



BONUS PROBLEMS