CMU 15-112 Summer 2018: Fundamentals of Programming and Computer Science
Bonus Homework (Due Fri 10-Aug, at 11:59pm)

• This assignment is COLLABORATIVE. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.


• To start:
  1. Create a folder named 'week6'
  2. Edit hw-bonus.py using Pyzo
  3. When you are ready, submit hw-bonus.py to Autolab. For this homework you will have unlimited submissions.
• This homework is partially autograded.
• Do not hardcode the test cases in your solutions.
• This homework will not be graded for style.
• Important Note: The autograder we use breaks when it tries to import tkinter. Therefore, all of your tkinter code must be included after a comment that reads #ignore_rest. The autograder will only grade code that appears before #ignore_rest.

1. getCourse(courseCatalog, courseNumber) [2 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. evalPrefixNotation(lst) [2 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.
3. solveRectangula(board) [2 pts](manually graded)
   Background: first, watch this short video on how to play the game of Rectangula:
   
   Now, your task is to write the function solveRectangula(board). This function takes a board which is a 2d list of integers corresponding to the board you see in the video, where blank cells contain 0's. Your function should return a solution to that board, which consists of a list of rectangles (in any order) such that:
   1. Every rectangle in your solution is on the board.
   2. No two rectangles in your solution overlap.
   3. Every non-zero number on the board is inside exactly one rectangle in your solution, and the area of that rectangle matches the number.
   4. And every rectangle in your solution contains exactly one number on the board.
   One oddity is that your rectangles must be of the form (row0, col0, width, height), where (row0, col0) marks the top-left of the rectangle (remember, rows increase vertically, cols increase horizontally), and width is the total number of columns, and height is the total number of rows (so width*height is the area of the rectangle).
   
   If there is no possible solution, your function should return None.
   
   We have provided a lot of code for you. This code is in the file hw_bonus_rectangula_tester.py. You should place that code next to your hw_bonus.py file. Do not include any code from rectangula-tester.py in your hw_bonus.py file! Instead, include these lines in your hw_bonus.py file, below the #ignore_rest line:
   ############################################### # ignore_rest ############################################### # Place these imports in hw_bonus.py below the ignore_rest line! from hw_bonus_rectangula_tester import testSolveRectangula from hw_bonus_rectangula_tester import playRectangula testSolveRectangula(solveRectangula) playRectangula(solveRectangula)
   Then, when you run your hw_bonus.py file, you'll run the testSolveRectangula function and the playRectangula function in rectangula-tester.py.
   
   Remember: Do not include any code from rectangula-tester.py in your hw_bonus.py file!
   
   Now, how should you solve a Rectangula puzzle? You may do this any way you wish, so long as you use backtracking meaningfully. That said, here are some hints about how we did this in our sample solution:
   
   
   • We first created a list of intPositions, which are tuples of the form (row, col, intValue), one for each non-zero integer on the board.
   
   
   • We separately created what we termed a "rectBoard", which is a board of the same size as the original board, but where each cell indicates whether or not it is included in a rectangle yet. This simplified testing whether a new rectangle intersects with any existing rectangle. But you can skip this step if you wish, and just try to intersect each new rectangle to all previous rectangles. But we found this approach to be easier.
   
   
   • The backtracking involves trying to place each intPosition onto the board. To "place" an intPosition means to place a rectangle of that area so that it contains that intPosition. When you run out of intPositions, you're done!
   
   
   • When you have to backtrack, don't forget to undo everything you did to make a move! This is the most common source of bugs in backtracking, so be careful about this step.
   
   
   • We found it was helpful to have a helper function that computed all the possible dimensions for a rectangle of a given area. For example, for an area of 8, the possible dimensions are 1x8, 2x4, 4x2, and 8x1.
   
   
   • When you try to place an intPosition, you should try to place every rectangle of the given area (using that helper function we just mentioned to find all the dimensions for the given area), and then to anchor the top-left of each of these different-dimensioned rectangles at every possible location where that rectangle includes the given position on the board. That may be worth re-reading once or twice...
   
   
   • For each of those possible rectangles that contains the given intPosition, don't forget to check the numbered rules given at the top of this writeup concerning what constitutes a solution.
   
   
   • We also found it handy to include an optional depth parameter so we could print out debug information indented by depth, which is really helpful in recursive debugging.
   
   
   • Also, to easily turn off all your debug printing, which you want to do before you submit, we suggest using a function that looks something like this:
     # To easily turn on/off db output def db(*args): dbOn = True if (dbOn): print(*args)
     So you call db() instead of print() for all your debug printing. Then, when you're done, instead of removing all those db() calls, you just dbOn to False, and voila, all your db printing is disabled. Handy!
   
   Have fun!!!