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

Read these instructions first!
Hw8a: TP + OOP (iteration allowed)

  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!

Hw8b: Recursion (iteration not allowed)

  1. 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.

  2. 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.

  3. 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).

  4. 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:
    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:
    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 "".