Homework 4

Due Monday 7-Feb, at 10:00pm

To start

  1. Create a folder named ‘hw4’
  2. Download hw4.py to that folder
  3. Edit hw4.py and modify the functions as required
  4. 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

  1. This homework is solo. You may not collaborate or discuss it with anyone outside of the course, and your options for discussing with other students currently taking the course are limited. See the academic honesty policy for more details.
  2. 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.
  3. There is no partial credit on Gradescope testcases. Your Gradescope score is your Gradescope score.
  4. Read the last bullet point again. 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…
  5. Do not hardcode the test cases in your solutions.
  6. 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.
  7. 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 in order 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 be grading 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

  1. nondestructiveRemoveRepeats(L) [15 pts]
    Important Note: to receive any credit for this problem, you may not simply create a copy of L and then call the destructiveRemoveRepeats function below. Instead, you must create the resulting list from scratch here. Also, note that the autograder has no way to check this, so our CA's will check this manually after the hw deadline.
    Write the function nondestructiveRemoveRepeats(L), which takes a list L and nondestructively returns a new list in which any repeating elements in L are removed. For example:
    assert(nondestructiveRemoveRepeats([1, 3, 5, 3, 3, 2, 1, 7, 5]) == [1, 3, 5, 2, 7])
    Also:
    L = [1, 3, 5, 3, 3, 2, 1, 7, 5] assert(nondestructiveRemoveRepeats(L) == [1, 3, 5, 2, 7]) assert(L == [1, 3, 5, 3, 3, 2, 1, 7, 5]) # nondestructive!
    Note that the values in the resulting list occur in the order they appear in the original list, but each occurs only once in the result. Also, since this is a nondestructive function, it returns the resulting list.

  2. destructiveRemoveRepeats(L) [15 pts]
    Important Note: this is the analog of the previous important note. Here, to receive any credit for this problem, you may not simply call nondestructiveRemoveRepeats(L) and then somehow remove all the elements in L and then append the elements from that call. Instead, you must destructively modify the list as you go. Also, again, note that the autograder has no way to check this, so our CA's will check this manually after the hw deadline.
    Write the function destructiveRemoveRepeats(L), which implements the same function destructively. Thus, this function should directly modify the provided list to not have any repeating elements. Since this is a destructive function, it should not return any value at all (so, implicitly, it should return None). For example:
    L = [1, 3, 5, 3, 3, 2, 1, 7, 5] assert(destructiveRemoveRepeats(L) == None) assert(L == [1, 3, 5, 2, 7]) # destructive!

  3. mostFrequentLetters(s) [20 pts]
    Write the function mostFrequentLetters(s), that takes a string s, and ignoring case (so "A" and "a" are treated the same), returns a lowercase string containing the letters of s in most frequently used order. (In the event of a tie between two letters, follow alphabetic order.) So:
    assert(mostFrequentLetters("We Attack at Dawn")=="atwcdekn")

    Note that digits, punctuation, and whitespace are not letters! Also note that seeing as we have not yet covered sets, maps, or efficiency, you are not expected to write the most efficient solution. (And you should not use sets, or maps in your solution.) Finally, if s does not contain any alphabetic characters, the result should be the empty string ("").

  4. rotateStringLeft(s, n) [20 pts]
    Note: To receive credit, do not use loops on this problem.
    Write the function rotateStringLeft(s, n) that takes a string s and a possibly-negative integer n. If n is non-negative, the function returns the string s rotated n places to the left. If n is negative, the function returns the string s rotated |n| places to the right. So, for example:
    assert(rotateStringLeft('abcd', 1) == 'bcda') assert(rotateStringLeft('abcd', -1) == 'dabc')

  5. isRotation(s, t) [1 pts] (this problem will count for the next homework)
    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.
    Hint: rotateStringLeft may be helpful here.

  6. bestScrabbleScore(dictionary, letterScores, hand) [30 pts]
    Background: In a Scrabble-like game, players each have a hand, which is a list of tiles that represent lowercase letters. A hand can also include one or more wildcard tiles (also called blank tiles). There is also a dictionary, which is a list of legal words (all in lowercase letters). And there is a list of letter scores that defines the point value of each tile. Players can use some or all of the tiles in their hands and arrange them in any order to form words. In addition, the game has 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 letter scores. In this task, we will represent the letter scores with a list 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) (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 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 plus zero or more blank tiles represented by *) -- and returns a tuple of the highest-scoring word in the dictionary that can be formed by some arrangement of some subset of tiles 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.

    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 with a hand that 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)
    Note that now with the wildcard we could form longer words: oldest (using the wildcard in place of s) and toledo (using the wildcard in place of an additional o).

    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?