15-112 Spring 2016 Homework 10 (the last!)
Due never

• This hw is not submitted. We will review solutions in lecture and/or recitation and/or midterm review sessions. The material can appear on midterm2 or the final.
• 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.
• Do not use global variables! Do use test functions! Do use helper functions!
• You may use iteration (for + while loops) to solve rectangula, but only if you use recursion meaningfully.

1. solveRectangula(board) [60 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 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. Gate class and subclasses [20 pts] [autograded]
   Write the classes required to make the following test function work properly.
   import types def getLocalMethods(clss): # This is a helper function for the test function below. # It returns a sorted list of the names of the methods # defined in a class. result = [ ] for var in clss.__dict__: val = clss.__dict__[var] if (isinstance(val, types.FunctionType)): result.append(var) return sorted(result) def testGateClasses(): print("Testing Gate Classes... ", end="") # require methods be written in appropriate classes assert(getLocalMethods(Gate) == ['__init__', '__str__', 'numberOfInputs', 'setInput']) assert(getLocalMethods(AndGate) == ['getOutput']) assert(getLocalMethods(OrGate) == ['getOutput']) assert(getLocalMethods(NotGate) == ['getOutput', 'numberOfInputs']) # make a simple And gate and1 = AndGate() assert(type(and1) == AndGate) assert(isinstance(and1, Gate) == True) assert(and1.numberOfInputs() == 2) and1.setInput(0, True) and1.setInput(1, False) # Hint: to get the name of the class given an object obj, # you can do this: type(obj).__name__ # You might do this in the Gate.__str__ method... assert(str(and1) == "And(True,False)") assert(and1.getOutput() == False) and1.setInput(1, True) # now both inputs are True assert(and1.getOutput() == True) assert(str(and1) == "And(True,True)") # make a simple Or gate or1 = OrGate() assert(type(or1) == OrGate) assert(isinstance(or1, Gate) == True) assert(or1.numberOfInputs() == 2) or1.setInput(0, False) or1.setInput(1, False) assert(or1.getOutput() == False) assert(str(or1) == "Or(False,False)") or1.setInput(1, True) assert(or1.getOutput() == True) assert(str(or1) == "Or(False,True)") # make a simple Not gate not1 = NotGate() assert(type(not1) == NotGate) assert(isinstance(not1, Gate) == True) assert(not1.numberOfInputs() == 1) not1.setInput(0, False) assert(not1.getOutput() == True) assert(str(not1) == "Not(False)") not1.setInput(0, True) assert(not1.getOutput() == False) assert(str(not1) == "Not(True)") print("Passed!") testGateClasses()


3. ComplexNumber class [20 pts] [autograded]
   Write the ComplexNumber class to make the following test function work properly. Do not use the builtin complex numbers in Python, but rather only use integers.
   def testComplexNumberClass(): print("Testing ComplexNumber class... ", end="") # Do not use the builtin complex numbers in Python! # Only use integers! c1 = ComplexNumber(1, 2) assert(str(c1) == "1+2i") assert(c1.realPart() == 1) assert(c1.imaginaryPart() == 2) c2 = ComplexNumber(3) assert(str(c2) == "3+0i") # default imaginary part is 0 assert(c2.realPart() == 3) assert(c2.imaginaryPart() == 0) c3 = ComplexNumber() assert(str(c3) == "0+0i") # default real part is also 0 assert(c3.realPart() == 0) assert(c3.imaginaryPart() == 0) # Here we see that the constructor for a ComplexNumber # can take another ComplexNumber, which it duplicates c4 = ComplexNumber(c1) assert(str(c4) == "1+2i") assert(c4.realPart() == 1) assert(c4.imaginaryPart() == 2) assert((c1 == c4) == True) assert((c1 == c2) == False) assert((c1 == "Yikes!") == False) # don't crash here assert((c2 == 3) == True) s = set() assert(c1 not in s) s.add(c1) assert(c1 in s) assert(c4 in s) assert(c2 not in s) assert(ComplexNumber.getZero() == 0) assert(isinstance(ComplexNumber.getZero(), ComplexNumber)) assert(ComplexNumber.getZero() == ComplexNumber()) # This next one is the tricky part -- there should be one and # only one instance of ComplexNumber that is ever returned # every time you call ComplexNumber.getZero(): assert(ComplexNumber.getZero() is ComplexNumber.getZero()) # Hint: you might want to store the singleton instance # of the zero in a class attribute (which you should # initialize to None in the class definition, and then # update the first time you call getZero()). print("Passed!") testComplexNumberClass()


4. 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 progres on your term projects. We hope this helps!