Homework 4

Due Tuesday 7-Feb, at 10:00pm

To start

Create a folder named ‘hw4’
Download hw4.py to that folder
Edit hw4.py and modify the functions as required
When you have completed and fully tested hw4, submit hw4.py to Gradescope. For this hw, you may submit up to 15 times, but only your last submission counts.

Some important notes

This homework is solo. You may not collaborate or discuss it with anyone outside the course, and your options for discussing it with other students currently taking the course are limited. See the academic honesty policy for more details.
After you submit to Gradescope, make sure you check your score. If you aren’t sure how to do this, then ask a CA or Professor.
There is no partial credit on Gradescope test cases. Your Gradescope score is your Gradescope score.
Reread the last bullet point. Seriously, we won’t go back later and increase your Gradescope score for any reason. Even if you worked really hard and it was only a minor error…
Do not hardcode the test cases in your solutions.
The starter hw4.py file includes test functions to help you test on your own before you submit to Gradescope. When you run your file, problems will be tested in order. If you wish to temporarily bypass specific tests (say, because you have not yet completed some functions), you can comment out individual test function calls at the bottom of your file in main(). However, be sure to uncomment and test everything together before you submit! Ask a CA if you need help with this.
Remember the course’s academic integrity policy. Solving the homework yourself is your best preparation for exams and quizzes; cheating or short-cutting your learning process to improve your homework score will actually hurt your course grade long-term.

Limitations

Do not use sets, dictionaries, try/except, classes, or recursion this week. The autograder (or a manual CA review later) will reject your submission entirely if you do.

A Note About Style Grading

Like in the previous assignment, we will grade your code based on whether it follows the 15-112 style guide. We may deduct up to 10 points from your overall grade for style errors. We highly recommend that you try to write clean code with good style all along rather than fixing your style issues at the end. Good style helps you code faster and with fewer bugs. It is totally worth it. In any case, style grading already started, so please use good style from now on!

A Note About Testing

You will notice that the skeleton file only includes testcases for some of the functions you are writing. You should write testcases for the others. (You can find some nice ways to test in the write-up below, but you will need to translate those to actual testcases.)

Problems

isRotation(s, t) [10 pts]
Write the function isRotation(s, t) that takes two possibly-empty strings and returns True if one is a rotation of the other. Note that a string is not considered a rotation of itself.

applyCaesarCipher(message, shift) [15 pts]
A Caesar Cipher is a simple cipher that works by shifting each letter in the given message by a certain number. For example, if we shift the message "We Attack At Dawn" by 1 letter, it becomes "Xf Buubdl Bu Ebxo".

Write the function applyCaesarCipher(message, shift) which shifts the given message by shift letters. You are guaranteed that message is a string, and that shift is an integer between -25 and 25. Capital letters should stay capital, lowercase letters should stay lowercase, and non-letter characters should not be changed. Note that "Z" wraps around to "A". So, for example:
assert(applyCaesarCipher("We Attack At Dawn", 1) == "Xf Buubdl Bu Ebxo") assert(applyCaesarCipher("zodiac", -2) == "xmbgya")

topScorer(data) [15 pts]
Write the function topScorer(data) that takes a multi-line string encoding scores as csv data for some kind of competition with players receiving scores, so each line has comma-separated values. The first value on each line is the player's name (which you can assume has no integers in it), and each value after that is an individual score (which you can assume is a non-negative integer). You should add all the scores for that player, and then return the player with the highest total score. If there is a tie, return all the tied players in a comma-separated string with the names in the same order they appeared in the original data. If nobody wins (there is no data), return None (not the string "None"). So, for example:
data = '''\ Fred,10,20,30,40 Wilma,10,20,30 ''' assert(topScorer(data) == 'Fred') data = '''\ Fred,10,20,30 Wilma,10,20,30,40 ''' assert(topScorer(data) == 'Wilma') data = '''\ Fred,11,20,30 Wilma,10,20,30,1 ''' assert(topScorer(data) == 'Fred,Wilma') assert(topScorer('') == None)
Hint: you may want to use both splitlines() and split(',') here!

mostFrequentSubstring(text, n) [20 pts] )
Given a string text your task is to find the most frequently occurring substring of a given length. Consider the following example: the length is three (n = 3) and the text is just baababacb. The most frequent substring would then be aba because this is the substring with size 3 that appears most often in the whole text (it appears twice) while the other six diﬀerent substrings appear only once (baa ; aab ; bab ; bac ; acb). You can assume n >= 0. Here are more examples:
assert(mostFrequentSubstring("baababacb", 3) == "aba") assert(mostFrequentSubstring("thequickbrownfoxjumpsoverthelazydog", 1) == "o") assert(mostFrequentSubstring("testingthecodetofindtheerrortestandtestagain", 4) == "test")

patternedMessage(message, pattern) [20 pts]
Write the function patternedMessage(message, pattern) that takes two strings, a message, and a pattern, and returns a string produced by replacing the non-whitespace characters in the pattern with the non-whitespace characters in the message (where any leading or trailing newlines in the pattern are first removed). As a first example:

call	result
patternedMessage("Go Pirates!!!", """ ************* ** ** ************* """)	GoPirates!!!GoP irates !!!GoP irates!!!GoPira

Here, the message is "Go Pirates!!!" and the pattern is a block of asterisks with a few missing in the middle. Notice how the whitespace in the pattern is preserved, but the whitespace in the message is removed. Again, note that any leading or trailing newlines in the pattern are removed.

Here is another example:

call	result
patternedMessage("Three Diamonds!",""" * * * * * * * * * * * * * * * """)	T h r eeD iam ond s!Thr eeDia monds !Th ree Dia m o n

Hint: While you may solve this how you wish, our sample solution did not use replace in any way. Instead, we started with the empty string, and built up the result character by character. How did we determine the next character? Using both the message and the pattern in some way...

And here is one last example, just for fun:

patternedMessage("Go Steelers!",
"""
                          oooo$$$$$$$$$$$$oooo
                      oo$$$$$$$$$$$$$$$$$$$$$$$$o
                   oo$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o         o$   $$ o$
   o $ oo        o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o       $$ $$ $$o$
oo $ $ '$      o$$$$$$$$$    $$$$$$$$$$$$$    $$$$$$$$$o       $$$o$$o$
'$$$$$$o$     o$$$$$$$$$      $$$$$$$$$$$      $$$$$$$$$$o    $$$$$$$$
  $$$$$$$    $$$$$$$$$$$      $$$$$$$$$$$      $$$$$$$$$$$$$$$$$$$$$$$
  $$$$$$$$$$$$$$$$$$$$$$$    $$$$$$$$$$$$$    $$$$$$$$$$$$$$  '$$$
   '$$$'$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     '$$$
    $$$   o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     '$$$o
   o$$'   $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$       $$$o
   $$$    $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$' '$$$$$$ooooo$$$$o
  o$$$oooo$$$$$  $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$   o$$$$$$$$$$$$$$$$$
  $$$$$$$$'$$$$   $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     $$$$'
 ''''       $$$$    '$$$$$$$$$$$$$$$$$$$$$$$$$$$$'      o$$$
            '$$$o     '$$$$$$$$$$$$$$$$$$'$$'         $$$
              $$$o          '$$'$$$$$$'           o$$$
               $$$$o                                o$$$'
                '$$$$o      o$$$$$$o'$$$$o        o$$$$
                  '$$$$$oo     '$$$$o$$$$$o   o$$$$'
                     '$$$$$oooo  '$$$o$$$$$$$$$'
                        '$$$$$$$oo $$$$$$$$$$
                                '$$$$$$$$$$$
                                    $$$$$$$$$$$$
                                     $$$$$$$$$$'
                                      '$$$'
""")

Returns this:

                          GoSteelers!GoSteeler
                      s!GoSteelers!GoSteelers!GoS
                   teelers!GoSteelers!GoSteelers!GoS         te   el er
   s ! Go        Steelers!GoSteelers!GoSteelers!GoSteel       er s! GoSt
ee l e rs      !GoSteeler    s!GoSteelers!    GoSteelers       !GoSteel
ers!GoSte     elers!GoSt      eelers!GoSt      eelers!GoSt    eelers!G
  oSteele    rs!GoSteele      rs!GoSteele      rs!GoSteelers!GoSteeler
  s!GoSteelers!GoSteelers    !GoSteelers!G    oSteelers!GoSt  eele
   rs!GoSteelers!GoSteelers!GoSteelers!GoSteelers!GoSteel     ers!
    GoS   teelers!GoSteelers!GoSteelers!GoSteelers!GoSteelers     !GoSt
   eele   rs!GoSteelers!GoSteelers!GoSteelers!GoSteelers!GoSt       eele
   rs!    GoSteelers!GoSteelers!GoSteelers!GoSteelers!Go Steelers!GoSteele
  rs!GoSteelers  !GoSteelers!GoSteelers!GoSteelers!GoS   teelers!GoSteelers
  !GoSteelers!G   oSteelers!GoSteelers!GoSteelers!Go     Steel
 ers!       GoSt    eelers!GoSteelers!GoSteelers!G      oSte
            elers     !GoSteelers!GoSteelers!         GoS
              teel          ers!GoSteel           ers!
               GoSte                                elers
                !GoSte      elers!GoSteele        rs!Go
                  Steelers     !GoSteelers!   GoStee
                     lers!GoSte  elers!GoSteeler
                        s!GoSteele rs!GoSteel
                                ers!GoSteele
                                    rs!GoSteeler
                                     s!GoSteeler
                                      s!GoS

bestScrabbleScore(dictionary, letterScores, hand) [20 pts]
Background: In a Scrabble-like game, players each have a hand, which is a list of tiles that represent lowercase letters plus one or more blank tiles. 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 tile that represents the ith character in the alphabet (so letterScores[0] contains the point value for tile 'a'). Players can use some or all of the tiles in their hand and arrange them in any order to form words. In addition, the game has two blank tiles that are unmarked and carry no point value. The blank tiles can stand in to be any letter. 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 tile used to form 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 as 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 returns a tuple of the highest-scoring word in the dictionary that can be formed by some arrangement of some subset of letters in the hand, followed by its score. In the case of a tie, the first element of the tuple should instead be a list of all such words in the order they appear in the dictionary. If no such words exist, return None.

Note: the dictionary is a list of words, not a Python dictionary. You are not allowed to use Python dictionaries in this homework.

Here's one example using the actual letter scores for Scrabble and a custom dictionary:
myDict = ['told', 'led', 'old', 'oldest', 'do', 'let', 'toledo'] myHand = ['l','d','e','o','t'] bestScrabbleScore(myDict, letterScores, myHand) == ('told', 5)
Here's the same example but now the hand includes one blank tile (denoted as '*'), which acts as a wildcard and allows to form longer (and higher score) words.
myDict = ['told', 'led', 'old', 'oldest', 'do', 'let', 'toledo'] myHand = ['*', 'l','d','e','o','t'] bestScrabbleScore(myDict, letterScores, myHand) == (['oldest', 'toledo'], 6)
Hint: 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.

Note: there is no fixed dictionary here. Each time we call the function, we may provide a different dictionary! It may contain 100 words or perhaps 100,000 words.

Another Hint: You may not use itertools for this problem! In fact, 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 the autograder will time out (hence, fail). There's a much simpler way to find all the legal words you can create...

Yet one more hint: Consider: if you had a single word w, and you have a single hand h, could you write a function f(w,h) (perhaps with a better name) that tells you whether or not that word could be constructed using that hand? And how might you use that function to help solve this problem?