15-112 Spring 2016 Homework 8
Both parts are due Sunday, 20-Mar, at 10pm

• This hw is entirely SOLO.
• Starting this week, you may use OOP, exceptions, and recursion, in addition to sets and maps,2d lists, event-based animations, 1d-lists, tuples, strings, graphics, loops and conditionals.
• This hw has two parts -- hw8a covers OOP (with some animation and a little recursion) and hw8b covers recursion. Note that you may (and should) use iteration (while and for loops) in hw8a, but you may not use iteration in hw8b. Be sure to submit hw8a.py and hw8b.py separately.
• Each part uses up to 1 grace and late day separately. Thus, if you submit them both parts on Monday, you would use 2 separate grace or late days.
• 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.
• Portions of this hw are autograded. You may make up to 5 submissions each of hw8a and hw8b. As usual, only your last one counts.
• Do not use global variables! Do use test functions! Do use helper functions!


• Here are a few important hints:
  • As usual, you may not use strings in numeric problems (like nthLeftTruncatablePrime).
  • In your recursion problems, you may have stack overflow exceptions after a depth of 50-100 or so. This means your solutions may work for small n, but not for even moderately large n. For example, nthLeftTruncatablePrime(n) may fail around n=51 or so. That is ok for this hw. We'll discuss a workaround for this problem next week.
  • Keep the graphics portion of your circuit simulator simple. For instance, you may keep your intersection tests really simple, so for example, you might only check if mouse presses are within the bounding boxes of gates.
  • Also as discussed below, the circuit simulator may well be underspecified, with some small design decisions left to you. So please do not post to piazza asking for us to decide these for you. This is good practice for your term project. Just make good decisions and have confidence in yourself. You can do this!

1. 5-Minute TP Meetings [10pts] [manually graded]
   By the hw8 deadline, everyone must have completed a 5-minute meeting (yes, just 5 minutes, though they may expand to 10 minutes at your CA's discretion) with one of the CA's from your assigned recitation, to begin a discussion about your term project ideas. This is very brief, just to be sure you've started thinking about TP's at least a bit. You do not have to prepare for these meetings, but it would be nice (and probably more effective) if you showed up with some ideas about what you might want to pursue. Also, at this point about 20% of you have already discussed your ideas with your CA or professor. Great! Even so, you still need to meet with your CA's. Perhaps the additional conversation may help give you even more cool ideas on how to pursue your project at this early stage.
   
   Early in this hw cycle, you will receive an email from your CA's with instructions about how to sign up for these meetings. Be sure to sign up right away, and be sure to be on time to these meetings. And move quickly, since they will be kept to 5 minutes, for real. So you know: They are worth 10 points in hw8, and the only way to get the points is to be on time. If you are late, or if you miss the meeting, you will not get the points, even if you have a make-up meeting. Of course, this does not include students with hw8 extensions for university-approved conflicts, or documented medical emergencies, etc.
   
   These meetings are only to help you. But you can help yourself, too. Look over the gallery a bit. Get an idea of what constitutes a term project. And start thinking about what you might be interested in.
   
   Also, once you have an idea, the next step after this meeting is to start fleshing it out. First, poke around the web and find some related projects, and check out what they do well and what they do poorly (this is a required part of the TP, and you might as well do it now, since it's a nice way to help you organize your thinking). Also, think about the technologies or modules you might need, and start downloading and installing them and seeing if you can use them. This is also required: to use a technology or module, you will have to demonstrate basic proficiency with it prior to starting the actual term project (that is, right after the second midterm). So now is the time to play around with them and see where you get the most traction.
   
   The hardest part of a TP for many students is choosing a good problem. And for that, time is your friend. So we are getting the TP clock ticking now, giving you the time you need to really blue-sky and innovate and dream up really fun, interesting, and doable projects.
   
   What to submit?
   For this problem, there is nothing to submit, as the CA's will record these meeting times and enter your grades accordingly.


2. OOPy Circuit Simulator [50 pts] [manually graded]
   Write the function run(), which is from our animation framework, that takes no parameters and runs an interactive circuit simulator. To get an idea of what we mean, first watch this video.
   
   Next, before implementing the animation portion, you should write the Gate class so that your code passes the test cases included at the end of this question's writeup. You should carefully read the test cases to gain an understanding of how the Gate class should work, and then only after you watched the video above.
   
   One hint: when you set the input value of a gate, that may wind up setting the output value (if it changed), in which caes you need to set the input values of the gates that that gate is connected to. This may wind up in a recursive call to propagate changes to the gates that those gates in turn are connected to. (So, yes, this problem involves OOP, animations, and recursion. Woohoo!)
   
   Once your code passes the Gate class test cases, then you should write the animation, which must use our animation framework (our run() function from the animation notes. Place your animation below the #ignore_rest line of your hw8.py file. Your animation should use your Gate class, of course! And it should follow the general description in the video above. You do not have to exactly match the user interface, just be reasonably close.
   
   The video makes fairly clear what is required. For example, it says you have to have buttons (well, labeled rectangles that act like buttons when you press the mouse inside them) for "Clear", "Save", and "Load". It does not say what shape or color those buttons have to be, or where on the screen they have to be, etc. Similarly, the video does not say anything about the size of the gates, or even the size of the window, but you would naturally have to choose sizes that make your tool usable (particularly by the graders!). And there's no description of the format you use inside the file that you save. That's entirely up to you.
   
   Aside: here's a hint: you may wish to briefly review the File IO notes from way back when we studied strings!
   
   So, clearly, several design decisions are left to you. This is to help move you even further along towards "term-project readiness", since in just a few weeks you will be working on an almost entirely unconstrained design problem. Have fun and be creative, but do not go crazy with this -- it is just one part of one hw. The focus is on OOP more than graphics and great user interface design or amazing circuit simulation, so keep it simple, but still make sure that basic tool works (so the xor circuit in the video, for example, could be created, then saved to file, then the circuit cleared, then the file loaded, and then the inputs toggled on and off to demonstrate that xor is in fact being computed by the circuit). Again, keep your graphics very simple. And have fun!
   
   def testGateClass1_inputToOutput(): # Connect and input gate to an output gate in1 = Gate("input") out1 = Gate("output") in1.connectTo(out1); assert(in1.getInputGates() == [ ]) assert(in1.getMaxInputGates() == 0) assert(in1.getOutputGates() == [ out1 ]) assert(out1.getInputGates() == [ in1 ]) assert(out1.getMaxInputGates() == 1) assert(out1.getOutputGates() == [ ]) assert(in1.inputValues == None) assert(in1.outputValue == None) assert(out1.inputValues == None) assert(out1.outputValue == None) # now set the input to True in1.setInputValue(None, True) assert(in1.inputValues == { None:True}) assert(in1.outputValue == True) assert(out1.inputValues == { in1:True}) assert(out1.outputValue == True) # and set the input to False in1.setInputValue(None, False) assert(in1.inputValues == { None:False}) assert(in1.outputValue == False) assert(out1.inputValues == { in1:False}) assert(out1.outputValue == False) def testGateClass2_oneNotGate(): in1 = Gate("input") out1 = Gate("output") not1 = Gate("not") in1.connectTo(not1) not1.connectTo(out1) assert(out1.outputValue == None) in1.setInputValue(None, False) assert(not1.inputValues == { in1:False }) assert(out1.inputValues == { not1:True }) assert(out1.outputValue == True) in1.setInputValue(None, True) assert(not1.inputValues == { in1:True }) assert(out1.inputValues == { not1:False }) assert(out1.outputValue == False) def testGateClass3_oneAndGate(): in1 = Gate("input") in2 = Gate("input") out1 = Gate("output") and1 = Gate("and") in1.connectTo(and1) in2.connectTo(and1) and1.connectTo(out1) assert(out1.outputValue == None) in1.setInputValue(None, False) assert(and1.inputValues == { in1:False }) assert(and1.outputValue == None) # not ready, need both inputs in2.setInputValue(None, False) assert(and1.inputValues == { in1:False, in2:False }) assert(and1.outputValue == False) assert(out1.outputValue == False) in1.setInputValue(None, True) assert(and1.inputValues == { in1:True, in2:False }) assert(out1.outputValue == False) in2.setInputValue(None, True) assert(and1.inputValues == { in1:True, in2:True }) assert(out1.outputValue == True) def testGateClass4_oneOrGate(): in1 = Gate("input") in2 = Gate("input") out1 = Gate("output") or1 = Gate("or") in1.connectTo(or1) in2.connectTo(or1) or1.connectTo(out1) assert(out1.outputValue == None) in1.setInputValue(None, False) assert(or1.inputValues == { in1:False }) assert(or1.outputValue == None) # not ready, need both inputs in2.setInputValue(None, False) assert(or1.inputValues == { in1:False, in2:False }) assert(or1.outputValue == False) assert(out1.outputValue == False) in1.setInputValue(None, True) assert(or1.inputValues == { in1:True, in2:False }) assert(out1.outputValue == True) in2.setInputValue(None, True) assert(or1.inputValues == { in1:True, in2:True }) assert(out1.outputValue == True) def testGateClass5_xor(): in1 = Gate("input") in2 = Gate("input") out1 = Gate("output") and1 = Gate("and") and2 = Gate("and") not1 = Gate("not") not2 = Gate("not") or1 = Gate("or") in1.connectTo(and1) in1.connectTo(not1) in2.connectTo(and2) in2.connectTo(not2) not1.connectTo(and2) not2.connectTo(and1) and1.connectTo(or1) and2.connectTo(or1) or1.connectTo(out1) in1.setInputValue(None, False) in2.setInputValue(None, False) assert(out1.outputValue == False) in1.setInputValue(None, True) in2.setInputValue(None, False) assert(out1.outputValue == True) in1.setInputValue(None, False) in2.setInputValue(None, True) assert(out1.outputValue == True) in1.setInputValue(None, True) in2.setInputValue(None, True) assert(out1.outputValue == False) def testGateClass(): print("Testing Gate class... ", end="") testGateClass1_inputToOutput() testGateClass2_oneNotGate() testGateClass3_oneAndGate() testGateClass4_oneOrGate() testGateClass5_xor() print("Passed!")


3. Bonus/Optional: 3d Tetris [5 pts, manually graded]
   Write the function play3dTetris() that takes no arguments and plays a 3d version of Tetris, similar for example to this video. To do this, basically rename run() to play3dTetris, and then rename mousePressed to tetrisMousePressed, keyPressed to tetrisKeyPressed, etc, so you don't interfere with the other animation in the same hw8.py file. Include a help screen when the user presses "h", which explains the controls. Do this using Tkinter, so keep the graphics as simple as you can while still looking 3d. Keep your time on this capped to 5 hours or less. Have fun!

• Every problem in hw8b must be solved using recursion. No iteration is allowed in hw8b.py (no while or for loops, no itertools, etc).


• You may (and in some cases really should) use helper functions. You may not use "for" or "while". Some of these are the break-down-into-smaller-problems kind of problems, others are the count-up sort.


• For longestSubpalindrome, as we discussed in lecture, you will want to test every possible substring -- you may wish to think about how you would solve this iteratively, and adapt that to a recursive solution.


• As usual, you may not use strings in numeric problems (like nthLeftTruncatablePrime).


• In your recursion problems, you may have stack overflow exceptions after a depth of 50-100 or so. This means your solutions may work for small n, but not for even moderately large n. For example, nthLeftTruncatablePrime(n) may fail around n=51 or so. That is ok for this hw. We'll discuss a workaround for this problem next week.

4. nthLeftTruncatablePrime [10 pts] [autograded]
   Adapted from f14-hw2. Without using any iteration, write the recursive function nthLeftTruncatablePrime(n). See here for details. So nthLeftTruncatablePrime(0) returns 2, and nthLeftTruncatablePrime(10) returns 53.


5. carrylessAdd [10 pts] [autograded]
   Adapted from f14-hw2. First, read the first page (page 44) from here about Carryless Arithmetic. Fun! Then, without using any iteration, write the recursive function carrylessAdd(x, y) that takes two non-negative integers x and y and returns their carryless sum. As the paper demonstrates, carrylessAdd(785, 376) returns 51.


6. longestDigitRun [10 pts] [autograded]
   Adapted from f14-hw2. Without using any iteration, write the recursive function longestDigitRun(n) that takes an int value n and returns the digit that has the longest consecutive run, or the smallest such digit if there is a tie. So, longestDigitRun(117773732) returns 7 (because there is a run of 3 consecutive 7's).


7. longestSubpalindrome [10 pts] [autograded]
   Adapted from f14-hw4. Without using any iteration, write the recursive function longestSubpalindrome(s), that takes a string s and returns the longest palindrome that occurs as consecutive characters (not just letters, but any characters) in s. So:

      longestSubpalindrome("ab-4-be!!!") 
   

   returns "b-4-b". If there is a tie, return the lexicographically larger value -- in Python, a string s1 is lexicographically greater than a string s2 if (s1 > s2). So:

      longestSubpalindrome("abcbce") 
   

   returns "cbc", since ("cbc" > "bcb"). Note that this function is case-sensitive (so "A" is not treated the same as "a" here). Also, from the explanation above, we see that longestSubpalindrome("aba") is "aba", and longestSubpalindrome("a") is "a". Note that longestSubpalindrome("") is "".

---