7/28/2019 15-112: Fundamentals of Programming
CMU 15-112 Summer 2019: Fundamentals of Programming and Computer Science
Homework 4-3 (Due Mon 29-Jul, at 5pm)
This assignment has both SOLO and COLLABORATIVE portions. Pay attention to which problem is which! For each problem, you must follow the course collaboration policy. For collaborative problems, remember that:
You may discuss anything about collaborative problems with other students, but all code you write must still be your own.
You may help other students debug by looking at their code and discussing how to debug it and what the issue might be.
Do not type on another student’s computer.
Do not send any code to other students, and do not copy any code from other students. Before you implement any parts of the game, erase any large chunks of code from a whiteboard/paper/shared files/etc.
Write the Andrew IDs of anyone you collaborate with at the top of your file.
You may have a maximum of 3-4 collaborators for the homework.
If you have any questions about what collaboration is allowed, email me (Chaya – cwurman@andrew.cmu.edu).
To start:
1. There is no starter file for this assignment! You should create a file, hw4-3.py, to start.
2. Edit hw4-3.py using Pyzo
3. When you are ready, submit hw4-3.py to Autolab. For this hw, you may submit up to 5
times, but only your last submission counts.
Do not use sets or dictionaries in this assignment.
Make sure to put all animation code, including the import to tkinter, underneath the “#ignore_rest” line
Do not hardcode the test cases in your solutions.
Remember to write your own test cases, and in general, follow the style guide!
1. findRTP(digits) [20 pts] SOLO [autograded]
Background: A number n is a right-truncatable prime, or RTP, if every prefix of n (including n itself) are all prime. So, 593 is an RTP because 5, 59, and 593 are all prime. With this in mind, write the function findRTP(digits) that takes a positive int, digits, and returns the smallest RTP with that many digits, or None if no such number exists. To do this, you must use backtracking even if you could do it in some other way. At each step, try to add one more digit to the right of the number. Also, make sure you are only creating RTP’s as you go. Note: even though findRTP(8) returns 23399339, it runs almost instantly because backtracking rules out most numbers without trying them, so it actually calls isPrime very few times.
2. OOPy Circuit Simulator [80 pts] COLLABORATIVE
Write the function run(), which is from our animation framework, that takes no parameters and runs
https://www.cs.cmu.edu/~112-n19/homeworks/hw4-3.html
1/7
7/28/2019 15-112: Fundamentals of Programming
an interactive circuit simulator. To get an idea of what we mean, first watch this video (https://youtu.be/9_i5fkKBLRc).
Gate Class [30 pts] [autograded]
Before implementing the animation portion, you should write the Gate class that passes the test cases below. You should carefully read the test cases to gain an understanding of how the Gate class should work.
One hint: when you set the input value of a gate, that may wind up setting the output value, in which case you need to set the input values of the gates you’re connected to. This may wind up in a recursive call to propogate changes to the gates that those gates in turn are connected to. (So yes, you need to write a recursive method within this class. Woohoo!)
https://www.cs.cmu.edu/~112-n19/homeworks/hw4-3.html
2/7
7/28/2019 15-112: Fundamentals of Programming
def testGateClass0_basics(): gate1 = Gate()
gate2 = Gate() assert(gate1.getInputGates() == []) assert(gate1.getOutputGates() == [])
assert(gate1.inputValues == [ ]) assert(gate1.outputValue == None)
# you can connect gates to each other!
gate1.connectTo(gate2) assert(gate1.getOutputGates() == [gate2]) assert(gate2.getInputGates() == [gate1])
# gate2 now has gate1 as an input, but since gate1.outputValue = None, # gate2.inputValues == [(gate1,None)]
assert(gate2.inputValues == [(gate1, None)])
def testGateClass1_inputToOutput():
# Connect an input gate to an output gate in1 = Input()
out1 = Output()
in1.connectTo(out1)
assert(in1.getInputGates() == [ ])
assert(in1.getMaxInputGates() == 0) # an input gate can’t have any inputs assert(in1.getOutputGates() == [ out1 ])
assert(out1.getInputGates() == [ in1 ])
assert(out1.getMaxInputGates() == 1)
assert(out1.getOutputGates() == [ ])
assert(in1.inputValues == [ ]) assert(in1.outputValue == None) assert(out1.inputValues == [(in1, None)]) assert(out1.outputValue == None)
in2 = Input()
in2.connectTo(out1)
# since out1 has a maximum of one input, and it already has in1 as an inp
ut,
# this shouldn’t do anything! assert(in2.getOutputGates() == []) assert(out1.getInputGates() == [ in1 ])
# setInputValue should take in two values – a fromGate and a value, which
# represent the gate the input is coming from, and the value of that gat
e.
# Here, in1 is an input gate, meaning that it’s input isn’t coming from
# anywhere! So, the fromGate = None, and the value = True in this case.
# be careful to examine the test cases to figure out what happens to the # gates you’re connected to once you set the input value! in1.setInputValue(None, True)
https://www.cs.cmu.edu/~112-n19/homeworks/hw4-3.html
3/7
7/28/2019
https://www.cs.cmu.edu/~112-n19/homeworks/hw4-3.html 4/7
15-112: Fundamentals of Programming
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 = Input()
out1 = Output()
not1 = Not()
in1.connectTo(not1)
not1.connectTo(out1)
assert(in1.outputValue == not1.outputValue == 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 = Input()
in2 = Input()
out1 = Output()
and1 = And()
in1.connectTo(and1)
in2.connectTo(and1)
and1.connectTo(out1)
assert(out1.outputValue == None)
in1.setInputValue(None, False)
assert(and1.inputValues == [(in1,False), (in2,None)]) 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)])
7/28/2019
https://www.cs.cmu.edu/~112-n19/homeworks/hw4-3.html 5/7
15-112: Fundamentals of Programming
assert(out1.outputValue == True)
def testGateClass4_oneOrGate(): in1 = Input()
in2 = Input()
out1 = Output()
or1 = Or()
in1.connectTo(or1)
in2.connectTo(or1)
or1.connectTo(out1)
assert(or1.inputValues == [(in1,None), (in2,None)]) assert(or1.outputValue == None)
assert(out1.outputValue == None)
in1.setInputValue(None, False)
assert(or1.inputValues == [(in1,False), (in2,None)]) 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 = Input()
in2 = Input()
out1 = Output()
and1 = And()
and2 = And()
not1 = Not()
not2 = Not()
or1 = 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)
7/28/2019
https://www.cs.cmu.edu/~112-n19/homeworks/hw4-3.html 6/7
15-112: Fundamentals of Programming
Copy
Circuit Simulator Animation [50 pts][manually graded]
Once your code passes the test cases above, then you should write the animation, using our animation framework. Your animation should use the Gate class you just wrote! It should follow the general description in the video above. You do not have to match the video exactly, just be reasonably close. Ultimately, your animation should be able to do the following:
1. You should have buttons on the left side of the canvas that represent the 5 types of classes: input, output, and, or, not. If you click on that button, and then click on the blank space, you should create a gate of that type on the screen.
2. If you click on one gate, then click on another gate, you should connect those gates together (provided that it’s a valid connection).
3. There should be two buttons at the top of the canvas: “power” and “clear”
Clicking on the “power” button should turn the power on! When the power is on, and you click on an input gate, that input gate should turn on, and any subsequent gates should also turn on.
Clicking on the “clear” button should remove all gates from the screen.
Clearly, there are several design decisions left to you. Make sure you plan out your code well before you write it, since your animation will likely be one of the longest ones you’ve written yet! Having a well written plan for your classes/animation framework will help you avoid getting “lost in the weeds”, and it will make debugging far easier for you.
A couple notes/hints for you:
Loading and Saving are Extra Credit! You do not need to implement them for this assignment, but you can if you would like.
You may wish to briefly review the File IO notes from when we studied strings!
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=””) testGateClass0_basics() testGateClass1_inputToOutput() testGateClass2_oneNotGate() testGateClass3_oneAndGate() testGateClass4_oneOrGate() testGateClass5_xor()
print(“Passed!”)
testGateClass()
7/28/2019 15-112: Fundamentals of Programming
You may add optional parameters to any methods or function that you wish! This may help for when you begin to add drawing functionality to your Gate class.
Have fun!
https://www.cs.cmu.edu/~112-n19/homeworks/hw4-3.html
7/7