CMU 15-112 Spring 2017: Fundamentals of Programming and Computer Science
Homework 11 (Due Fri 7-Apr, at 10pm)

• This hw is SOLO. For this hw, do not even discuss any portion of it with anyone except TA's and faculty. Please be sure to work alone on it.
• Starter files: none this week.
• This week you may use up to 5 submissions. Only your last submission counts.
• Do not hardcode the test cases in your solutions.
• As usual, there are no late days this week (though you may use a grace day if you have one available).
• Be sure to place all your graphics, include the import lines below the #ignore_rest line, and all your autograded functions above that line, or the autograder will not work!

1. Study Recursion Notes [0 pts]
   For this problem, you need to spend at least a few hours studying the recursion notes. There is nothing to submit here, but you will be expected to very quickly and facilely be able to write any example from the recursion notes (part 1 or part 2), or any reasonably similar sort of recursive problem. You are guaranteed these problems (or close variants) will appear on upcoming quizzes and exams and finals. This will require a lot of practice. So we have reserved time in hw9 for you to do just that. Do not skip this step, even though there is nothing to submit! Practice, practice, practice!


2. hFractal() [20 pts] [manually graded]
   Background: First, read about the H-Fractal here. Also, be sure to study the Sierpinksy Triangle example from the notes, particularly how it allows the user to use the arrow keys to move up and down to different recursive levels of the fractal.
   
   With this in mind, below the #ignore_rest line, write the function hFractal() that takes no parameters and uses our animation framework (so calls the run() function) to implement an "H-Fractal viewer", that starts by viewing a "level 0 H-Fractal", and allows the user to use the arrow keys to move up and down to view different recursive levels of the H-Fractal.
   
   Hint: The H that is drawn right in the middle should always have the same size (the width and height should be half the window width and height). At each level, we draw new H's with half the dimensions of the previous level. This is why the window size never has to change (since 1 + 1/2 + 1/4 + 1/8 + ... = 2).


3. solveABC(constraints, aLocation) [40 pts] [autograded]
   This problem is inspired by the "ABC Path" problems at BrainBashers.com. For more (optional) info, check this out.
   
   Background: In what we will call an "ABC Puzzle", you are given a 5x5 board like this:
   
   It is an empty board except that it contains a single "A" in an arbitrary cell. Also, the letters from "B" to "Y" are arranged around the outside of the board in an arbitrary order, along with arrows that constrain those letters to a certain row, column, or diagonal. For example, in the image, we see the "H" and "T" are constrained to column 0, "L" and "I" are constrained to row 0, and "C" and "G" are constrained to the column running from (0,0) to (4,4). The goal of this puzzle is to place every letter from "B" to "Y" on the board such that: (1) each letter from "B" to "Y" is placed in the row, column, or diagonal in which it is constrained; and (2) each letter from "B" to "Y" is placed adjacent (including diagonally) to the previous letter (so "B" is adjacent to "A", and "C" is adjacent to "B", and so on).
   
   A solution to the puzzle is here:
   
   Be sure you understand why this solves the puzzle! If you are unsure, go to the link at BrainBashers.com and read more about this kind of puzzle, including this help page, and maybe try to solve a few more of them (the puzzles include a button you can press to get the solutions!).
   
   Now, for us to represent one of these puzzles in Python, we have to represent the constraints. We'll do that by reading them clockwise starting from the top-left corner. Thus, in the given example, the constraints are: constraints = "CHJXBOVLFNURGPEKWTSQDYMI" And we also need to specify the position of the "A", which we will do as a (row,col) tuple, as such: aLocation = (0,4)
   
   With this in mind, write the function solveABC(constraints, aLocation), that takes constraints and the location of the "A", which together define an ABC Puzzle, and returns a completed board which solves the puzzle, or None if no such board exists. Here is a test function that is based on the puzzle used in the example above (notice how the constraints and aLocation match the unsolved puzzle, and the resulting board matches the solved puzzle):
   
   
   def testSolveABC(): print('Testing solveABC()...', end='') constraints = "CHJXBOVLFNURGPEKWTSQDYMI" aLocation = (0,4) board = solveABC(constraints, aLocation) solution = [['I', 'J', 'K', 'L', 'A'], ['H', 'G', 'F', 'B', 'M'], ['T', 'Y', 'C', 'E', 'N'], ['U', 'S', 'X', 'D', 'O'], ['V', 'W', 'R', 'Q', 'P'] ] assert(board == solution) print('Passed!')
   Note: To receive any credit for this problem, you must solve it recursively, even if you could dream up a non-recursive solution!
   Hint #1: This is a backtracking problem. Study nQueens. This is most like that problem.
   Hint #2: Our sample solution required about 50 lines of code. If you are ranging well past that, perhaps you should pause and rethink your approach. Probably in the vicinity of some blue hoodies!


4. ComplexNumber class [40 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()


5. No bonus!
   Note that there is no bonus on hw11. 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!