15-112 Fall 2015 Homework 9
Due Sunday, 8-Nov, at 10pm

• This hw is entirely SOLO.
• If you know what itertools are, don't use them to get around using recursion. If you don't know what itertools are, you may safely ignore this item.
• Portions of this hw are autograded. You may make up to 5 submissions. As usual, only your last one counts.
• Do not use global variables! Do use test functions! Do use helper functions!
• You may use iteration (for + while loops), but only if you use recursion meaningfully (except the decorator problem, where neither is required).

1. Study Recursion Notes [0 pts]
   For this problem, you need to spend at least a few hours studying the recursion notes. There is nothing to submit here, but you will be expected to very quickly and facilely be able to write any example from the recursion notes (part 1 or part 2), or any reasonably similar sort of recursive problem. You are guaranteed these problems (or close variants) will appear on upcoming quizzes and exams and finals. This will require a lot of practice. So we have reserved time in hw9 for you to do just that. Do not skip this step, even though there is nothing to submit! Practice, practice, practice!


2. findLargestFile(path) [20 pts]
   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.
   
   Also note: also regarding efficiency, it is overtly inefficient to create a list of files, say using listFiles. So you may not use listFiles here. Instead, you must compute the largestFile as you go, though perhaps returning it in a tuple to a wrapper function, as the previous note suggests.
   
   Finally: you may resolve ties as you wish.


3. flatten(L) [20 pts]
   Write the recursive function flatten(L), 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)
   



4. findRTP(digits) [15 pts]
   Background: A number n is a right-truncatable prime, or RTP, if every prefix of n (including n itself) are all prime. So, 593 is an RTP because 5, 59, and 593 are all prime. With this in mind, write the function findRTP(digits) that takes a positive int, digits, and returns the smallest RTP with that many digits, or None if no such number exists. To do this, you must use backtracking even if you could do it in some other way. At each step, try to add one more digit to the right of the number. Also, make sure you are only creating RTP's as you go. Note: even though findRTP(8) returns 23399339, it runs almost instantly because backtracking rules out most numbers without trying them, so it actually calls isPrime very few times.
   Hint: you may need to use callWithLargeStack so your isPrime does not stack overflow.


5. getCourse(courseCatalog, courseNumber) [20 pts]
   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, and without using any iteration, 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)
   



6. hFractal() [20 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).


7. @noError decorator [5 pts]
   Write the @noError function decorator so that the following test function works properly:
   def testNoErrorDecorator(): print("Testing @noError decorator...", end="") @noError def f(x, y): return x/y assert(f(1, 5) == 1/5) assert(f(1, 0) == None) @noError def g(): return 1/0 assert(g() == None) @noError def h(n): if (n == 0): return 1 else: return h(n+1) assert(h(0) == 1) assert(h(-1) == 1) assert(h(1) == None) print("Passed!")
   You may notice that a function decorated with @noError behaves the same, except if the original function would crash (technically, raise an exception), the decorated function instead just returns None. Be sure not to hardcode the number of parameters, so that your decorator works for a function no matter how many parameters it takes.


8. bonus/optional: solveSudoku(board) [up to 3 pts]
   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. Note: you must use backtracking here. Also, it will take way too long if you are not clever about the order in which you make your guesses. For that, always find the cell that is the most constrained, that is, the one that has the fewest possible legal choices (resolving ties arbitrarily).


9. bonus/optional: runSudokuoSolver() [up to 2 pts]
   Only attempt this problem if you have completed the solveSudoku bonus problem already. Write the function runSudokuSolver() that is a renamed and slightly adapted version of our run() function (from our standard animation framework) that implements a nice user interface for a Sudoku game, which should let the user solve the puzzle themselves (by filling in blanks with numbers, etc), but which also includes a solve-puzzle feature using the previous bonus problem. Be sure to rename mousePressed, keyPressed, etc, so as not to conflict with your hFractal code from above.