CMU 15-112: Fundamentals of Programming and Computer Science
Homework 6b (Due Saturday 10-Oct 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 'week6'
2. Download these files into that folder:
3. Edit hw6b.py using VSCode
4. When you have completed and fully tested hw6b, submit hw6b.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
Do not use recursion, sets, or dictionaries in this unit.
Do not hardcode the test cases in your solutions.

Important note: This hw is split into two parts, both entirely solo, as such:

Hw6a was due Friday at 8pm and is worth 60 points. It contains 6 standard problems and 1 spicy problem.
Hw6b (this part) is due Saturday at 8pm and is worth 40 points. It contains another two standard problems, and everyone has to do both of them, plus an optional bonus problem.
There is no Grace Day for hw6b.

We added the Saturday deadline because we will discuss the non-bonus Saturday problems in recitation on Friday, including some really useful hints, and we wanted everyone in every timezone to have the time to absorb those hints for those problems.

Again, both parts are entirely solo.

Standard Problems

Important Note: Everyone should do both of these!

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: Carefully review the test cases in the starter code to be sure you understand how this function is supposed to work. Also, it may be a really good idea for you to add your own test cases for this problem.

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

Hint #3: 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 #4: In particular, 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?

drawLetterTypePieChart(canvas, text, cx, cy, r) [20 pts] [manually graded]
Note: Be sure to see the hint below about the canvas.create_arc method!
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. Note that drawing an arc with extent 0 still draws a line which we don't want to see in this case.
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:

And as a second example, this test code (included in the hw starter file):
```
rA = min(width,height)*0.15
rB = min(width,height)*0.2
drawLetterTypePieChart(canvas, "aLpHaBeT!", width*0.175, height*0.575, rA)
drawLetterTypePieChart(canvas, "I ordered 2 eggs & 1 waffle for breakfast!",
                       width/2, height*0.375, rB)
drawLetterTypePieChart(canvas, "A_E_I_O_U", width*0.825, height*0.575, rA)
drawLetterTypePieChart(canvas, "#fbrkyz", width*0.5, height*0.8, rA)
```
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:

Bonus Problem

solvesCryptarithm(puzzle, solution) [1 pts bonus] [autograded]
Note: This is a medium-level problem, perhaps not as challenging as most bonus problems. But it sets the stage for the next problem, which is indeed quite challenging. Enjoy!
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.

Solving Puzzles with Combinatoric Generators [up to 5 pts] [autograded]
Notes:
- As with some other spicy and/or bonus problems, this one has a long writeup. Don't be daunted! You can do it! And it's really cool.
- TA's generally do not provide help for bonus problems. However, for this problem, a select group of TA's have volunteered to provide some modest help on piazza. But you should expect very little help, and perhaps with a longer turnaround time than usual. And that help is limited to piazza, not OH.
- You may wish to consult these notes from a recent Spicy Recitation that covered generators.
- 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
  Note: the sections (such as this one) that do not include point values are here to provide important background information for the other sections with point values.
  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 [1 pt]
  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).
  
  Note: While sorted() can convert a generator into a list the same way that list() can, your function must be a generator, so you cannot simply return the list of all sublists.
  
  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 [1 pt]
  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 (and not the empty list []). 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 [1 pt]
  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 (note that output in the pseudocode should be implemented using yield):
```
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 could write the function solveCryptarithm(puzzle) at this point (but we won't, so... don't!) 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 [1 pt]
    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, if maxDigit is 4, we only construct permutations of [0, 1, 2, 3, 4] instead of all 10 factorial permutations of all 10 digits, then we append 5 dashes to the end of the string so that we have 10 characters in total.
    
    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 [1 pt]
    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, we sorted the words and had 3 nested for loops: one to loop over each word, the second which looped over every word after the first word, and the third which checks every word that is not the first word or the second word. This speeds up our function by a factor of 2, which could mean the difference between your function timing out on Autolab or not.
    
    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!')
```
    Hint: For formatting purposes, it may be convenient to write a helper function that converts a given cryptarithm from numerical form to letter form, or vice versa.
  That's it, you made it, you solved two really interesting problems using two different combinatorial generators. Great job!!!!

CMU 15-112: Fundamentals of Programming and Computer Science Homework 6b (Due Saturday 10-Oct at 8pm)

CMU 15-112: Fundamentals of Programming and Computer Science
Homework 6b (Due Saturday 10-Oct at 8pm)