CMU 15-112: Fundamentals of Programming and Computer Science
Homework 4 (Due Saturday 8-Feb at 8pm)

This homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
To start:
1. Create a folder named 'unit4'
2. Download all three of these files into that folder:
3. Edit hw4.py using VSCode
4. When you have completed and fully tested hw4, submit hw4.py to Autolab. For this hw, you may submit up to 7 times, but only your last submission counts.
Do not use recursion in this unit.
Do not hardcode the test cases in your solutions.

Also note:

No lab this week (optional hw help instead)
Friday labs this week are optional. We will provide hw help all day, and you can attend as many sessions as you prefer.
15 required points, so do 85 points of mild, medium, and/or spicy
The mild + medium problems are 85 points, and the spicy problems are 90 points. You can mix and match as appropriate for you.
Some fun spicy problems here!
We found the spicy problems here to be fun and engaging if also a bit challenging. We sure hope a lot of you give them a try, if that is appropriate for your situation.
Some fun non-spicy problems here, too!
If you opt to do the medium problems instead, we think those are buckets of fun, too (truly)! So: enjoy!
We continue to do style grading!
So you should continue to use good style!

Required Problem

Person class [15 pts] [autograded]
Write the class Person so that the following test code passes:

def testPersonClass():
    print('Testing Person Class...', end='')
    fred = Person('fred', 32)
    assert(isinstance(fred, Person))
    assert(fred.getName() == 'fred')
    assert(fred.getAge() == 32)
    # Note: person.getFriends() returns a list of Person objects who
    #       are the friends of this person, listed in the order that
    #       they were added.
    # Note: person.getFriendNames() returns a list of strings, the
    #       names of the friends of this person.  This list is sorted!
    assert(fred.getFriends() == [ ])
    assert(fred.getFriendsNames() == [ ])

    wilma = Person('wilma', 35)
    assert(wilma.getName() == 'wilma')
    assert(wilma.getAge() == 35)
    assert(wilma.getFriends() == [ ])

    wilma.addFriend(fred)
    assert(wilma.getFriends() == [fred])
    assert(wilma.getFriendsNames() == ['fred'])
    assert(fred.getFriends() == [wilma]) # friends are mutual!
    assert(fred.getFriendsNames() == ['wilma'])

    wilma.addFriend(fred)
    assert(wilma.getFriends() == [fred]) # don't add twice!

    betty = Person('betty', 29)
    fred.addFriend(betty)
    assert(fred.getFriendsNames() == ['betty', 'wilma'])

    pebbles = Person('pebbles', 4)
    betty.addFriend(pebbles)
    assert(betty.getFriendsNames() == ['fred', 'pebbles'])

    barney = Person('barney', 28)
    barney.addFriend(pebbles)
    barney.addFriend(betty)
    barney.addFriends(fred) # add ALL of Fred's friends as Barney's friends
    assert(barney.getFriends() == [pebbles, betty, wilma])
    assert(barney.getFriendsNames() == ['betty', 'pebbles', 'wilma'])
    fred.addFriend(wilma)
    fred.addFriend(barney)
    assert(fred.getFriends() == [wilma, betty, barney])
    assert(fred.getFriendsNames() == ['barney', 'betty', 'wilma']) # sorted!
    assert(barney.getFriends() == [pebbles, betty, wilma, fred])
    assert(barney.getFriendsNames() == ['betty', 'fred', 'pebbles', 'wilma'])
    print('Passed!')

Note that your solution must work in general, and not hardcode to these specific test cases.

Mild Problems

destructiveRemoveEvens(L) [5 pts] [autograded]
Write the function destructiveRemoveEvens(L) that takes a possibly-empty list L that you can assume contains only integers. The function destructively removes all the even integers from L. As with most destructive functions, this function returns None.

nondestructiveRemoveEvens(L) [5 pts] [autograded]
Write the function nondestructiveRemoveEvens(L) that works the same as the previous function, only this version is nondestructive, so it does not modify L and it returns a new list without the evens.

Medium Problems

drawLetterTypePieChart(canvas, text, cx, cy, r) [25 pts] [manually graded]
Write the function drawLetterTypePieChart that takes 5 parameters: a canvas, some text (which is just a string), then cx and cy (specifying a point (cx,cy) on the canvas), and r (specifying a radius). The function draws a pie chart centered at (cx, cy) with radius r that indicates the number of vowels, consonants, and other characters in the text, with these constraints:
1. The fill color for vowels should be pink, consonants should be cyan, and others should be lightGreen.
2. Do not count whitespace characters at all. Hint: the isspace method can be handy here.
3. Draw the labels in 12-point Arial bold, formatted exactly as noted in the images below -- the letter type, and then in parentheses, the number of that letter type out of the total number of non-whitespace characters, a comma, and then that ratio as an integer percentage.
4. Center the text in the center of the pie wedge. Any reasonable interpretation of "center of the pie wedge" will be accepted.
5. The pink wedge (if it is present) must start at the vertical, followed counterclockwise by cyan, then lightGreen.
6. Do not draw a wedge if there are no characters of that type.
7. If all the characters are of a single type, draw a whole circle, with the label centered in the circle.
8. If there are no vowels, consonants, or other non-whitespace characters, then display "No data to display" centered in the window, in 18-point Arial bold.
9. Draw a title for the pie chart, centered 20 pixels above the top, also in 18-point Arial bold, with the title: ('Text = ' + repr(text)).
For example, this test code (included in the hw starter file):
```
r = min(width,height)*0.2
canvas.create_line(width/2, 0, width/2, height)
canvas.create_line(0, height/2, width, height/2)
drawLetterTypePieChart(canvas, "AB, c de!?!", width/4, height/4, r)
drawLetterTypePieChart(canvas, "AB e", width/4, height*3/4, r)
drawLetterTypePieChart(canvas, "A", width*3/4, height/4, r)
drawLetterTypePieChart(canvas, "               ", width*3/4, height*3/4, r)
```
produces this result on an 800x800 window:

Hint #1: you may find it helpful to write a helper function, something like drawPieWedge, that you might call several times, once for each wedge in the pie.

Hint #2: in any case, you will need to use the canvas.create_arc method. This method takes 4 required parameters, the bounding box of a circle, and then two more named (keyword) parameters -- the start angle of the arc, in degrees, and the so-called extent (or angle from the start angle to the end angle), also in degrees.

For example, in a 300x300 window, these calls:
```
canvas.create_rectangle(100, 100, 250, 250) # to see the bounding box
canvas.create_arc(100, 100, 250, 250, start=90, extent=45, fill="blue")
```
produce this result:

bestScrabbleScore(dictionary, letterScores, hand) [25 pts] [autograded]
Background: in a Scrabble-like game, players each have a hand, which is a list of lowercase letters. There is also a dictionary, which is a list of legal words (all in lowercase letters). And there is a list of letterScores, which is length 26, where letterScores[i] contains the point value for the ith character in the alphabet (so letterScores[0] contains the point value for 'a'). Players can use some or all of the tiles in their hand and arrange them in any order to form words. The point value for a word is 0 if it is not in the dictionary; otherwise it is the sum of the point values of each letter in the word, according to the letterScores list (pretty much as it works in actual Scrabble).

In case you are interested, here is a list of the actual letterScores for Scrabble:
```
letterScores = [
#  a, b, c, d, e, f, g, h, i, j, k, l, m,
   1, 3, 3, 2, 1, 4, 2, 4, 1, 8, 5, 1, 3,
#  n, o, p, q, r, s, t, u, v, w, x, y, z
   1, 1, 3,10, 1, 1, 1, 1, 4, 4, 8, 4,10
]
```
Note that your function must work for any list of letterScores that is provided by the caller.

With this in mind, write the function bestScrabbleScore(dictionary, letterScores, hand) that takes 3 lists -- dictionary (a list of lowercase words), letterScores (a list of 26 integers), and hand (a list of lowercase characters) -- and finds the highest-scoring word in the dictionary that can be formed by some arrangement of some set of letters in the hand.
- If there is only one highest-scoring word, return it and its score in a tuple.
- If there are multiple highest-scoring words, return a tuple with two elements: a list of all the highest-scoring words in the order they appear in the dictionary, then the score.
- If no highest-scoring word exists (ie, if no legal words can be formed from the hand), return None instead of a tuple.
The dictionary in this problem is a list of words, and thus not a true Python dictionary (which we haven't taught you and you may not use in this assignment)! It is ok to loop through the dictionary, even if the dictionary we provide is large.

Hint #1: You should definitely write helper functions for this problem! In fact, try to think of at least two helper functions you could use before writing any code at all.

Hint #2 (important!): Do not create permutations of the letters at all -- that is, do not try to generate all the possible ways to arrange the hand! If you do, your solution will take too long and Autolab will time out (hence, fail). Also, you may not use itertools for this problem. In any case, there's a much simpler way to find all the legal words in the given dictionary that you can create, as suggested by the next hint...

Hint #3: We found it enormously helpful to write a helper function that takes a word and a hand, and tells whether or not that word could be constructed using that hand. How might you use that function to help solve this problem?

solvesCryptarithm(puzzle, solution) [25 pts] [autograded]
Background: a cryptarithm is a puzzle where we start with a simple arithmetic statement but then we replace all the digits with letters (where the same digit is replaced by the same letter each time). We will limit such puzzles to strings the form "A + B = C" (always exactly one space on either side of '+' and '='), where A, B, and C are positive integers. For example, "SEND + MORE = MONEY" is such a puzzle. The goal of the puzzle is to find an assignment of digits to the letters to make the math work out properly. For example, if we assign 0 to "O", 1 to "M", 2 to "Y", 5 to "E", 6 to "N", 7 to "D", 8 to "R", and 9 to "S" we get:
```
    S E N D       9 5 6 7
  + M O R E     + 1 0 8 5
  ---------     ---------
  M O N E Y     1 0 6 5 2
```
And so we see that this assignment does in fact solve the problem! Now, we need a way to encode a possible solution. For that, we will use a single string where the index of the letter corresponds to the digit it represents. Thus, the string "OMY--ENDRS" represents the assignments listed above (the dashes are for unassigned digits).

With this in mind, write the function solvesCryptarithm(puzzle, solution) that takes two strings, a puzzle (such as "SEND + MORE = MONEY") and a proposed solution (such as "OMY--ENDRS"). Your function should return True if substituting the digits from the solution back into the puzzle results in a mathematically correct addition problem, and False otherwise. You do not have to check whether a letter occurs more than once in the proposed solution, but you do have to verify that all the letters in the puzzle occur somewhere in the solution (of course). You may not use the eval() function. Also, you almost surely will want to write at least one well-chosen helper function.

Spicy Problems

Solving Puzzles with Combinatoric Generators [45 pts] [autograded]
Note: as with some other spicy problems, this one has a long writeup. Don't be daunted! You can do it! And it's really cool. Enjoy!!!

Here, we will learn about combinatoric generators, then use these to solve two interesting puzzles: subsetSum and cryptarithms (yes, the same cryptarithms mentioned above).
1. Understanding generators
  Consider the following function:
```
def specialRange(n):
    # seemingly the same as range(n), but omits multiples of 3
    result = [ ]
    for x in range(n):
        if (x % 3 != 0):
            result.append(x)
    return result
```
  This function appears to work the same as range(n), but omits the multiples of 3. To wit:
```
for v in specialRange(10):
    print(v) # prints 1 2 4 5 7 8
```
  Yep, this looks like it works just fine. But it doesn't! Let's try that last example again, only with a much larger range, up to 10**8 say. And we can't print out so many values, so we'll break after we print the first value, like so:
```
# this time we'll see a problem....
for v in specialRange(10**8):
    print(v)
    break
```
  Did you see the problem? There was a huge delay before anything printed. Why? Because we are constructing an enormous list of values, and Python must build the whole list before we can use any of it. At 10**8 that takes a long time. By 10**10 it may take impossibly long, plus we will also soon run out of memory. So this is clearly not working well for large n.
  
  As you may have guessed, there is a better way. We can convert our specialRange function into a generator. Instead of constructing a list and returning it, we can yield each value that we would have placed on the list. Python stops running the function at that point, uses the yielded value, then starts the function right where it left off to get the next yielded value. Awesome!
  
  To make this work, we simply change our specialRange function from this:
```
def specialRange(n):
    # seemingly the same as range(n), but omits multiples of 3
    result = [ ]
    for x in range(n):
        if (x % 3 != 0):
            result.append(x)
    return result
```
  To this:
```
def specialRange(n):
    # this time as a generator!
    for x in range(n):
        if (x % 3 != 0):
            yield x
```
  Then re-run the examples above that use specialRange(n), and you will see that they work exactly the same with the generator, only there is no delay at all, even for huge n. Try this:
```
for v in specialRange(10**50):
    # 10**50 is ridiculously huge, yet this still works just fine with a generator
    print(v)
    break
```
  The generator never creates the list, it just creates one value of the list at a time. This is a beautiful solution!
2. The allSublists(L) generator
  Now you get to actually write your own generator! The goal is to the write the generator allSublists(L) that takes a possibly-empty list L, and generates all the sublists of L -- that is, all the lists made up of some (or all) of the elements of L. If L was a set and not a list, this is what we would call the powerset of L. Here are some test cases:
```
assert(sorted(allSublists([1])) == [ [], [1] ])
assert(sorted(allSublists([3, 5])) == [ [], [3], [3, 5], [5] ])
assert(sorted(allSublists([6,7,8])) == [ [], [6], [6, 7], [6, 7, 8],
                                         [6, 8], [7], [7, 8], [8] ])
```
  We include a call to sorted in the test cases because your generator can produce the sublists in any order (so we sort them and compare the result to the sorted order).
  
  Now, how to do this? We will first observe that a list with N elements in it has 2**N sublists (think about that). Then, we realize that we can have a counter k run from 0 to (2**N)-1, and we can use that counter to generate the kth sublist. How? By considering k in base 2, and using 0's to exclude values and 1 to include them in the sublist. You may have to re-read that a couple times. Plus, an example would help.
  
  Say we have the list L = [5,6,7,8]. Here, N=4, and there are 2**4 or 16 sublists. So we run k from 0 to 15 inclusive. What happens when k is, say, 13? Well, 13 in base 2 is 1101. We use those 4 digits to determine whether each of the 4 values of the list L are in this sublist:
```
L = [ 5, 6, 7, 8 ]
k =   1  1  0  1   (13)
```
  Look at the figure above, and see that there is a 1 under 5, 6, and 8, and a 0 under 7. So when k==13, the sublist is [5, 6, 8].
  
  Use this technique to write the generator allSublists(L). Also, as a hint, you probably should write getKthBinaryDigit(n, k), which works the same as getKthDigit(n, k) only in binary instead of decimal (basically, change the 10 to a 2 and you're done).
3. Solving subsetSum
  Ok, now we can use that generator to solve a real problem! The problem we will try to solve is called subsetSum. Given a list L, return a sublist of L that sums to 0, or return None if no such sublist exists. We will discuss this problem a lot more, later on in this course, since it has some fascinating properties. For now, we'll just try to solve it.
  
  How do we solve it? Quite easily at this point, in fact. We just use the allSublists generator you just wrote, and check if each sublist sums to 0 (using sum(sublist)). This should be quick!
  
  One word of caution: while this does solve the problem, the solution is very slow (in fact, exponentially slow). So only test it on very small lists. In any case, the starter file includes testSolveSubsetSum to help check if you got this step right.
4. The heapsAlgorithmForPermutations(L) generator
  Ok, so we now understand generators and how they can be used to solve some kinds of puzzle problems (basically by trying every possible answer). We'll move on to a new kind of generator. This time, instead of allSublists, we are interested in permutations. That is, for a list L, every possible way to order the values in L.
  
  There are numerous ways to solve this, but we will use a specific approach: namely, the iterative (non-recursive) form of Heap's Algorithm. You can read about it on the linked Wikipedia page if you wish, or not, as you can do this problem without fully understanding how Heap's Algorithm works. You just have to translate it into a Python generator. This is the pseudocode from that website:
```
procedure generate(n : integer, A : array of any):
    //c is an encoding of the stack state. c[k] encodes the for-loop counter for when generate(k+1, A) is called
    c : array of int

    for i := 0; i < n; i += 1 do
        c[i] := 0
    end for

    output(A)
    
    //i acts similarly to the stack pointer
    i := 0;
    while i < n do
        if  c[i] < i then
            if i is even then
                swap(A[0], A[i])
            else
                swap(A[c[i]], A[i])
            end if
            output(A)
            //Swap has occurred ending the for-loop. Simulate the increment of the for-loop counter
            c[i] += 1
            //Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
            i := 0
        else
            //Calling generate(i+1, A) has ended as the for-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
            c[i] := 0
            i += 1
        end if
    end while
```
  Your task here is to closely translate that pseudocode into the generator heapsAlgorithmForPermutations(L). Here are some test cases for you:
```
assert(sorted(heapsAlgorithmForPermutations([1])) == [[1]])
assert(sorted(heapsAlgorithmForPermutations([1,2])) == [
        [1,2], [2,1]
    ])
assert(sorted(heapsAlgorithmForPermutations([3,1,2])) == [
        [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
    ])
```
  Important Hint: use yield copy.copy(A) instead of yield A. This avoids a challenging bug to find based on aliasing.
5. Solving cryptarithms
  Ok, we're on the last step! Here, we will use the permutation generator you just wrote to solve cryptarithms! First, read the solvesCryptarithm problem above. Here, instead of testing if a solution solves a cryptarithm, we will find the solution that solves a cryptarithm. Sweet!
  1. solveCryptarithm
    We will write the function solveCryptarithm(puzzle) like so:
    1. extract the 3 words from the puzzle (so go from 'SEND + MORE = MONEY' to the list ['SEND', 'MORE', 'MONEY']).
    2. generate a string of the unique letters in the 3 words in the puzzle (so for 'SEND + MORE = MONEY', this would be 'SENDMORY' (in any order)).
    3. augment that string with dashes so it is of length 10 (so the string above becomes 'SENDMORY--'
    4. Now we observe that any possible solution to the puzzle must be a permutation of the string we just made. This is key. So...
    5. We use the generator we just wrote to generate every possible permutation of the string, and we check each one in turn to see if it does in fact solve the puzzle. If so, we return it (actually, as you will see in the test cases, we return a more-nicely-formatted version of it). If none of the permutations solves the puzzle, then we return None.
    That's it. We're done! Except... This runs SO slowly that it is almost not even testable. Ugh. So... We will modify the problem a little bit, constraining it so that we can in fact test it.
  2. solveCryptarithmWithMaxDigit
    For that, we will add a maxDigit, and require that the solution not contain any digits larger than maxDigit. Thus, we change solveCryptarithm(puzzle) to become solveCryptarithmWithMaxDigit(puzzle, maxDigit). This way, we only construct permutations of strings of length (maxDigit+1), and then we append (10 - (maxDigit+1)) dashes to those strings to make candidate solutions to use as above. Read this a few times and think about it!
    
    Here is a test function for you:
```
def testSolveCryptarithmWithMaxDigit():
    print('  Testing solveCryptarithmWithMaxDigit()...', end='')
    assert(solveCryptarithmWithMaxDigit('RAM + RAT = ANT', 4) == '''\
RAM + RAT = ANT
120 + 123 = 243''')
    assert(solveCryptarithmWithMaxDigit('ANT + CAT = EEL', 4) == None)
    assert(solveCryptarithmWithMaxDigit('ANT + CAT = EEL', 5) == '''\
ANT + CAT = EEL
125 + 315 = 440''')
    print('Passed!')
```
  3. countCryptarithmsWithMaxDigit
    Ok, we are getting close. To best test these puzzles, it would be nice to find puzzles that have a single unique solution (can you see why?). Ok, let's do that. For this, you will write the function countCryptarithmsWithMaxDigit(puzzle, maxDigit). This requires just a tiny change or two to the function you just wrote, solveCryptarithmWithMaxDigit(puzzle, maxDigit). Instead of returning the first match, now you just count all the matches, and return that count. That's it!
  4. getAllSingletonCryptarithmsWithMaxDigit
    Ok, now we can write the last function for this exercise, getAllSingletonCryptarithmsWithMaxDigit(words, maxDigit). This function takes a list of words, from which it will generate possible puzzles. Then it will call your countCryptarithmsWithMaxDigit function on each such puzzle, and if the result is 1, then that means that that puzzle has a single unique solution (with the maxDigit restriction). Great! We will include that puzzle in our result, which is just a multiline string of all such puzzles.
    
    Note that your output must list the puzzles in alphabetical order. Note that 'A + B = C' and 'B + A = C' are considered the same problem, so only the first would be included in our answer, as 'A' is alphabetically before 'B'. To do that, our function first sorts the words, which helped to that end. We also included 3 nested 'for' loops -- one for each of the 3 words in the puzzle. Finally, here is a test function you may want to closely study:
```
def testGetAllSingletonCryptarithmsWithMaxDigit():
    print('  Testing getAllSingletonCryptarithmsWithMaxDigit()...', end='')
    words = ['EEL', 'RAM', 'CAT', 'BEE', 'FLY',
             'HEN', 'RAT', 'DOG', 'ANT']
    assert(getAllSingletonCryptarithmsWithMaxDigit(words, 3) == '')
    assert(getAllSingletonCryptarithmsWithMaxDigit(words, 4) == '''\
RAM + RAT = ANT
120 + 123 = 243''')
    assert(getAllSingletonCryptarithmsWithMaxDigit(words, 5) == '''\
ANT + CAT = EEL
125 + 315 = 440
ANT + CAT = HEN
105 + 315 = 420
ANT + RAT = EEL
125 + 315 = 440
ANT + RAT = HEN
105 + 315 = 420
BEE + EEL = FLY
411 + 112 = 523''')

    words = ['DEER', 'BEAR', 'GOAT', 'MULE', 'PUMA',
             'COLT', 'ORCA', 'IBEX', 'LION', 'WOLF']
    assert(getAllSingletonCryptarithmsWithMaxDigit(words, 5) == '')
    assert(getAllSingletonCryptarithmsWithMaxDigit(words, 6) == '''\
BEAR + DEER = IBEX
4203 + 1223 = 5426
COLT + GOAT = ORCA
4635 + 1605 = 6240''')
    print('Passed!')
```
  That's it, you made it, you solved two really interesting problems using two different combinatorial generators. Great job!!!!

runSimpleProgram(program, args) [45 pts] [autograded]
First, carefully watch this video that describes this problem:

Then, write the function runSimpleProgram(program, args) that works as described in the video, taking a legal program (do not worry about syntax or runtime errors, as we will not test for those cases) and runs it with the given args, and returns the result.

Here are the legal expressions in this language:
- [Non-negative Integer]
  Any non-negative integer, such as 0 or 123, is a legal expression.
- A[N]
  The letter A followed by a non-negative integer, such as A0 or A123, is a legal expression, and refers to the given argument. A0 is the value at index 0 of the supplied args list. It is an error to get or set arg values that are not supplied. And you may ignore these errors, as we will not test for them!
- L[N]
  The letter L followed by a non-negative integer, such as L0 or L123, is a legal expression, and refers to the given local variable. It is ok to get an unassigned local variable, in which case its value should be 0.
- [operator] [operand1] [operand2]
  This language allows so-called prefix expressions, where the operator precedes the operands. The operator can be either + or -, and the operands must each be one of the legal expression types listed above (non-negative integer, A[N] or L[N]).
And here are the legal statements in this language (noting that statements occur one per line, and leading and trailing whitespace is ignored):
- ! comment
  Lines that start with an exclamation (!), after the ignored whitespace, are comments and are ignored.
- L[N] [expr]
  Lines that start with L[N] are assignment statements, and are followed by the expression (as described above) to be stored into the given local variable. For example: L5 - L2 42 This line assigns (L2 - 42) into L5.
- [label]:
  Lines that contain only a lowercase word followed by a colon are labels, which are ignored except for when they are targets of jump statements.
- JMP [label]
  This is a jump statement, and control is transferred to the line number where the given label is located. The given label will always exist in our test cases.
- JMP+ [expr] [label]
  This is a conditional jump, and control is transferred to the line number where the given label is located only if the given expression is positive. Otherwise, the statement is ignored.
- JMP0 [expr] [label]
  This is another kind of conditional jump, and control is transferred only if the given expression is 0.
- RTN [expr]
  This is a return statement, and the given expression is returned.
Hints:
1. Do not try to translate the program into Python! Even if you could do so, it is not allowed here. Instead, you are going to write a so-called interpreter. Just keep track of the local variables, and move line-by-line through the program, simulating the execution of the line as appropriate.
2. You will find it useful to keep track of the current line number.
3. How long do you run the program? Until you hit a RTN statement! You may assume that will always eventually happen.
4. We used strip, split, and splitlines in our sample solution, though you of course may solve this how you wish.
Finally, here is a sample test function for you. You surely will want to add some addition test cases. In fact, a hint would be to build your function incrementally, starting with the simplest test cases you can think up, which use the fewest expression and statement syntax rules. Then add more test cases as you implement more of the language.
def testRunSimpleProgram(): print("Testing runSimpleProgram()...", end="") largest = """! largest: Returns max(A0, A1) L0 - A0 A1 JMP+ L0 a0 RTN A1 a0: RTN A0""" assert(runSimpleProgram(largest, [5, 6]) == 6) assert(runSimpleProgram(largest, [6, 5]) == 6) sumToN = """! SumToN: Returns 1 + ... + A0 ! L0 is a counter, L1 is the result L0 0 L1 0 loop: L2 - L0 A0 JMP0 L2 done L0 + L0 1 L1 + L1 L0 JMP loop done: RTN L1""" assert(runSimpleProgram(sumToN, [5]) == 1+2+3+4+5) assert(runSimpleProgram(sumToN, [10]) == 10*11//2) print("Passed!")

CMU 15-112: Fundamentals of Programming and Computer Science Homework 4 (Due Saturday 8-Feb at 8pm)

CMU 15-112: Fundamentals of Programming and Computer Science
Homework 4 (Due Saturday 8-Feb at 8pm)