15-112 Fall 2014 Homework 9
Due Wednesday, 5-Nov, at 8pm (no late submissions)

Read these instructions first!

• As with hw8, hw9 has two parts. Hw9c is COLLABORATIVE. You may work in teams of up to 2 current 15-112 students on it. See hw8 and also see the syllabus for more details. Hw9s is SOLO. You must work entirely alone on hw9s. Again, see hw8 or the syllabus for more details.


• For hw9c (collaborative), you may not use any iteration at all. That is, you may not use "while", "for", or "itertools". Instead, you may only use recursion. This is only for hw9c, and will be strictly enforced by the autograder (it will not even attempt to grade files which have a single instance of one of those terms in it!). For hw9s (solo), however, you are free to use iteration whereever you think it is appropriate, so long as you definitely use recursion in some meaningful way in every solution (which should be automatic, since the only reasonable way to solve the hw9s problems involves recursion anyhow).


• This week, you may only make up to 5 submissions max to Autolab each for hw9c and hw9s. As usual, only your last one counts.


• This week, no late submissions will be accepted. So the latest you can submit hw9 is by the main deadline, 8pm on Wednesday (except, of course, if you have a pre-arranged extension due to a university-approved conflict).


• Some hints and clarifications are included at the end of this document.

---


Hw9c: [COLLABORATIVE]


1. hw9c: nthHappyPrime (recursive) [15 pts] [autograded] [COLLABORATIVE]
   Without using any iteration, write nthHappyPrime from here (see #2), along with the other helper functions specified in the writeup. Also, here's a handy hint: any test to see if any given number is happy will eventually get to either 1 or 4.


2. hw9c: bubblesort (recursive) [15 pts] [manually graded] [COLLABORATIVE]
   Without using any iteration, write a non-destructive bubblesort. So bubblesort(a) returns a new list, sorted with bubblesort, without modifying the original list.


3. hw9c: getCourse (recursive) [15 pts] [autograded] [COLLABORATIVE]
   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, and without using any iteration, 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)
   

---


Hw9s: [SOLO]


4. hw9s: solveABC [40 pts] [manually graded] [SOLO]
   Do solveABC from here (see #6), using backtracking. Hint: you may benefit by first carefully reviewing our nqueens case study.


5. hw9s: hFractal() [15 pts] [manually graded] [SOLO]
   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, write the function hFractal() that takes no parameters and uses our OOP-based MVC framework (so creates an instance of a subclass of BasicAnimationClass) 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.
   
   Note: do not copy-paste any BasicAnimation code (from basicAnimation.py or from basicAnimationClass.py) in your hw9s.py file. Instead, import from basicAnimationClass. We will make sure that this import works when we run your code.
   
   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).


6. hw9s: FarmGame [0 pts on hw9 (part of hw8)] [manually graded] [SOLO]
   Note: Don't forget to submit FarmGame in your hw9s.py file (even though it is part of hw8s).


7. hw9s: Bonus/Optional: bonusTwoStackHanoi [2 pts] [manually graded] [SOLO]
   Background: Here, we will consider a modified form of the Towers of Hanoi problem. Given an input n>0, there are 2n discs of increasing size (instead of just n discs of increasing size). There are 3 poles as in the original problem (Pole 0, Pole 1, and Pole 2). We label the discs with numbers {1, 2, 3, ..., 2n}, where the label of a disc corresponds to its size. Initially, the odd-numbered discs (i.e. the discs {1, 3, 5, ..., 2n-1}) are on Pole 0, and the even-numbered discs (i.e. the discs {2, 4, 6, ..., 2n}) are on Pole 2. The goal is to get all the discs on Pole 1 (the middle pole).
   
   With this in mind, write the function bonusTwoStackHanoi(n) that takes a positive int n and returns a list of the moves in order required to solve a 2-stack Hanoi problem as described above (so, to ultimately move the n discs from Pole 0 and the n other discs from Pole 2 all to Pole 1, while also maintaining the Hanoi rule that no disc can be placed on a smaller disc). A "move" will be represented as a tuple (x,y), where x and y are both in the set {0,1,2}, and means to move one disc from Pole x to Pole y.


8. hw9s: Bonus/Optional: bonusPythagorasTree() [4 pts] [manually graded] [SOLO]
   Background: First, read about the Pythagoras Tree here. With this in mind, write the function bonusPythagorasTree() that works like hFractal() only here it makes a Pythagoras Tree. For half-credit, just make the balanced one in the first row of the image. For full-credit, oscillate between sloped trees, as in the second image, but varying the angles back and forth over time so that there is a waving effect, as though blowing in the wind (well, with enough imagination).

---

Here are some hints and clarifications:

• Study linearSearch() and largest() examples (optional parameters and wrapper functions)
  These are at the top of the course notes on recursion. They show how to use optional parameters and wrapper functions to help convert iterative solutions to recursive ones.


• nthHappyPrime: Minimize recursive depth
  Search for nthHappyPrime(n) starting from nthHappyPrime(n-1). This will help reduce your recursion depth. Also, since all happy primes are odd, step by 2's, not 1's.


• nthHappyPrime: use fasterIsPrime
  Be sure to use an adapted form of fasterIsPrime and not slowerIsPrime!


• getCourse: Study listFiles() in the notes!
  This problem is most like that one, so be sure you thoroughly understand how listFiles works first. In particular, the nested lists in the problem are sort of like folders (right?), and the course names are sort of like file names (right?).


• getCourse: Solve with a "for" loop first
  This is not required, of course, but it's very helpful probably to first solve getCourse using a "for" loop, in the same way that our listFiles example uses one. Then, as a second step, get rid of the "for" loop -- in the same way you already got rid of "for" loops in the nthHappyNumber problem.


• Do not use mutable values (like lists) to initialize default parameters!
  Here is an important hint regarding a very strange Python behavior. You should never use lists or other mutable values to initialize default parameters. The outcome is weird. To see this, check this out:

  def f(x, a=[]):
      a.append(x)
      return a
  print f(5)     # prints [5]
  print f(6, []) # prints [6]
  print f(7)     # prints [5, 7] <-- where did the 5 come from?!?
  

  Ugh!


• Don't use nested functions, they are too hard to test and debug
  Nested functions (defined inside other functions) can be hard to test and debug. And then much of the yummy goodness of top-down design is lost, making debugging painful to impossible (since a bug in the outer function can in fact be anywhere inside any of the helper functions -- ugh!). So the way forward is easy to see: (1) Do not use nested functions (functions defined inside other functions), and (2) Do test all your helper functions before using them. This hint can save you many hours of frustration!