CMU 15-112: Fundamentals of Programming and Computer Science
Homework 6a (Solo) (Due Saturday 13-Mar at 8pm)

  1. destructiveRemoveEvens(L) [5 pts]
  2. nondestructiveRemoveEvens(L) [5 pts]
  3. areaOfPolygon(L) [10 pts]
  4. evalPolynomial(coeffs, x) [10 pts]
  5. multiplyPolynomials(p1, p2) [10 pts]
  6. solvesCryptarithm(puzzle, solution) [15 pts]
  7. bestScrabbleScore(dictionary, letterScores, hand) [20 pts]
  8. Bonus / Optional: runSimpleProgram(program, args) [up to 2.5 pts]
  9. Bonus / Optional: Solving Puzzles with Combinatoric Generators [up to 2.5 pts]

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

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

    Note: you may not simply call destructiveRemoveEvens() here, nor can you copy-paste-edit that code. Thus, instead of copying the list L and then destructively mutating it to get the answer, you need to build up a new list from scratch.

  3. areaOfPolygon(L) [10 pts] [autograded]
    Write the function areaOfPolygon(L) that takes a list of (x,y) points that are guaranteed to be in either clockwise or counter-clockwise order around a polygon, and returns the area of that polygon, as described here. For example (taken from that text), areaOfPolygon([(4,10), (9,7), (11,2), (2,2)]) returns 45.5 (at least the result is almostEqual to 45.5). Here is a sample test function for you:
    def testAreaOfPolygon():
        print("Testing areaOfPolygon()...", end="")
        assert(almostEqual(areaOfPolygon([(4,10), (9,7), (11,2), (2,2)]), 45.5))
        assert(almostEqual(areaOfPolygon([(9,7), (11,2), (2,2), (4, 10)]), 45.5))
        assert(almostEqual(areaOfPolygon([(0, 0), (0.5,1), (1,0)]), 0.5))
        assert(almostEqual(areaOfPolygon([(0, 10), (0.5,11), (1,10)]), 0.5))
        assert(almostEqual(areaOfPolygon([(-0.5, 10), (0,-11), (0.5,10)]), 10.5))

  4. evalPolynomial(coeffs, x) [10 pts] [autograded]
    Background: we can represent a polynomial as a list of its coefficients. For example, [2, 3, 0, 4] could represent the polynomial 2x**3 + 3x**2 + 4. With this in mind, write the function evalPolynomial(coeffs, x) that takes a list of coefficients and a value x and returns the value of that polynomial evaluated at that x value. For example, evalPolynomial([2,3,0,4], 4) returns 180 (2*4**3 + 3*4**2 + 4 = 2*64 + 3*16 + 4 = 128 + 48 + 4 = 180).

  5. multiplyPolynomials(p1, p2) [10 pts] [autograded]
    Background: we can represent a polynomial as a list of its coefficients. For example, [2, 3, 0, 4] could represent the polynomial 2x3 + 3x2 + 4. With this in mind, write the function multiplyPolynomials(p1, p2) which takes two lists representing polynomials as just described, and returns a third list representing the polynomial which is the product of the two. For example, multiplyPolynomials([2,0,3], [4,5]) represents the problem (2x**2 + 3)(4x + 5), and:
        (2x**2 + 3)(4x + 5) = 8x**3 + 10x**2 + 12x + 15
    And so this returns the list [8, 10, 12, 15].

  6. solvesCryptarithm(puzzle, solution) [15 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.

  7. bestScrabbleScore(dictionary, letterScores, hand) [20 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?

  8. Bonus / Optional: runSimpleProgram(program, args) [up to 2.5 pts] [autograded]
    Both of the bonus problems in this hw are a bit more involved, but are really fun and interesting (or so we think -- we hope you agree!). Again, these are worth just a few points, so do these for the love of learning.

    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.

    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!")

  9. Bonus / Optional: Solving Puzzles with Combinatoric Generators [up to 2.5 pts] [autograded]
    Note: while this has a long writeup, don't be daunted! You can do it! And it's really cool. Also, you can get partial credit for solving just the early parts of this problem. 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):
          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):
      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):
          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
      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
          //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])
                      swap(A[c[i]], A[i])
                  end if
                  //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
                  //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''')

      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''')
      That's it, you made it, you solved two really interesting problems using two different combinatorial generators. Great job!!!!