15-112 Fall 2015 Homework 10 (the last!)
Due Sunday, 15-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.
• None of this hw is autograded. Even so, 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. solveRectangula(board) [50 pts]
   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 hw10_rectangula_tester.py. You should place that code next to your hw10.py file. Do not include any code from rectangula-tester.py in your hw10.py file! Instead, include these lines in your hw10.py file, below the #ignore_rest line:
   ############################################### # ignore_rest ############################################### # Place these imports in hw10.py below the ignore_rest line! from hw10_rectangula_tester import testSolveRectangula from hw10_rectangula_tester import playRectangula testSolveRectangula(solveRectangula) playRectangula(solveRectangula)
   Then, when you run your hw10.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 hw10.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!!!


2. OopyInvaders (with inheritance)
   Write the OopyInvaders game described in this video:
   In case it helps, here is the code at the end:
   game1 = OopyInvaders() game1.run() print(game1.getFinalScore()) game2 = OopyInvaders() game2.run() print(game2.getFinalScore()) assert(OopyInvaders.totalGamesPlayed == 2)
   Focus on the OOP parts, and make the UI just-good-enough to prove it works, as this is chiefly about OOP design and only partly about animations and UI. Enjoy!


3. No bonus!
   Note that there is no bonus on hw10. This is to leave you plenty of time to study for midterm2 and to make some solid progress on your term projects. We hope this helps!