CMU 15-112: Fundamentals of Programming and Computer Science
Homework 11 (Due Tue 13-Apr at 11pm ET)

• The same rules about recursion from hw10 apply to this hw, with one exception: Unlike last hw, in this hw you can use for loops or while loops, as long as you also use recursion meaningfully in each problem.
• This hw is collaborative. The same collaboration rules as in hw8 (Tetris) apply to this hw.

1. findLargestFile(path) [50 pts]
2. knightsTour(rows, cols) # with backtracking [50 pts]

1. findLargestFile(path) [50 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 terms of bytes 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 (or anything similar) 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 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") == "")
   
   Hints:
   1. You also may need to get rid of those pesky .DS_Store files that Macs like to add to folders that you unzip. To do that, use removeTempFiles. Remember to be careful, since it removes without asking and it does not move the removed files to the trash (they are really gone).
   2. Here are the headers for each of the functions we wrote, with brief descriptions:
      def findLargestFile(path): # Wrapper to extract just the bestPath from the helper # function that returns both bestPath and bestSize ... def findLargestFileAndSize(path): # Returns (bestPath, bestSize) starting from this path, which could # be to either a folder or a file ...


2. knightsTour(rows, cols) # with backtracking [50 pts] [autograded]
   First, read about the Knight's Tour problem here. Next, write the function knightsTour(rows, cols) that takes a non-negative int n and returns a 2d list of a knight's tour on an rows-by-cols board, or None if this does not exist. This is a slight generalization since here we will allow non-square rectangular boards.
   
   Following these instructions, knightsTour(4, 5) should return a legal 4x5 knight's tour, such as this one:

   [
    [ 1, 14,  5, 18,  7], 
    [10, 19,  8, 13,  4],
    [15,  2, 11,  6, 17],
    [20,  9, 16,  3, 12]
   ]
   

   Here we see that the tour started at 1, which is at the top-left corner. Then following the sequence 1,2,3,... to follow each move in order.
   
   Note that it is possible for some dimensions that there is a legal knight's tour, only not one starting at the top-left corner. You will have to account for that in your solution.
   
   Also: backtracking can be slow, and your solution will probably not run fast enough after 6-by-6 or so. That's ok. :-)
   
   Optional extra challenge: speed this up! There are techniques that can make this work fast enough for somewhat larger boards (though they still bog down eventually). You can do some pondering of your own, or some internet sleuthing, but in any case, try to make this run faster. Or not, since it is optional.
   
   In any case, have fun!