CMU 15-112 Spring 2018: Fundamentals of Programming and Computer Science
Colab 10 (Due Thursday 29-Mar, at 10pm)

• This assignment is collaborative. That means you may work with other students enrolled in the course, and you may even help each other write code and debug. However, you must still type all of your own work, and you must fully understand the code that you submit. Even though this is collaborative, you may not directly copy any code from anyone, and you may not electronically share your code with anyone. See the syllabus for more details.
• List your collaboration partners (name and andrew id) in a comment on the first line of this file. If you collaborate with another student and do not include their name in a comment, it will be considered cheating. You may work alone if you want to, but we recommend working with others, as it generally leads to better learning.
• Be a good collaborator! Help everyone in your group, and accept their help if you need it. Don't be in a hurry to finish the problems. Instead, take your time and be sure that everyone in the group is following and understanding. The goal is to learn, not just to finish.
• If you're looking for more people to collaborate with, you can request to be paired up with other 112 students using this form.

---

• To start:
  1. Go to your folder named 'week10'
  2. Create a file named colab10.py.
  3. Edit colab10.py using Pyzo
  4. When you are ready, submit colab10.py to Autolab. You may submit up to 5 times.
• Do not hardcode the test cases in your solutions.

1. evalPrefixNotation(lst) [30 pts]
   Background: in so-called 'prefix notation', an arithmetic expression is listed with the operator first. So instead of writing '2 + 3' we would write '+ 2 3'. Actually, for this problem, we'll represent the expression in a list, so we'd write ['+', 2, 3]. Each value can itself be another full expression, so for example we could have:
   

   ['+', 2, '*', 3, 4]

   This would be the same as (2 + (3 * 4)), or 14. Again, we could have:
   

   ['+', '*', 2, 3, '*', 4, 5]

   This would be the same as ((2 * 3) + (4 * 5)), or 26. You can visualize this as a hierarchical structure, where each operator must be followed by two values on the next column:
   

   +
       *
           2
           3
       *
           4
           5
   

   These expressions can become fairly complex; consider:

   ['*', '+', 2, '*', 3, '-', 8, 7, '+', '*', 2, 2, 5]

   This is the expression (2 + (3 * (8 - 7))) * ((2 * 2) + 5), which is equal to 45.
   
   With this in mind, write the function evalPrefixNotation(lst) that takes a list lst that contains a legal arithmetic expression in prefix notation, as just described, and returns the value that the expression evaluates to. Your function only needs to work for '+', '-', and '*'.
   
   Hint: this problem becomes drastically easier to solve if you implement it destructively. Our sample solution used lst.pop(0) to get the first element, for example. Evaluating the operands then becomes much simpler.


2. 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 colab10_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. solveSudoku(board) [40 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. You will want to make use of the code you wrote in colab5. 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 certainly will...
   
   
   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!')
   
   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.