Practice 1

Due: Never


To start

  1. Create a folder named ‘practice1’
  2. Download practice1.py to that folder
  3. Edit practice1.py and modify the functions as required
  4. When you have completed and fully tested practice1, submit practice1.py to Gradescope. For this practice, you may submit up to 100 times.

Some important notes

  1. These practice problems will help you prepare for the final exam. They are optional and you are encouraged to collaborate when working on them.
  2. These practice problems are NOT GRADED, and they don’t count as bonus points, nor they have any impact on your grade.
  3. Read the last bullet point again. THIS IS NOT GRADED.
  4. As usual, do not hardcode the test cases in your solutions.
  5. The starter practice1.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.

Limitations

Do not use sets, dictionaries, try/except, classes, or recursion this week. The autograder should reject your submission entirely if you do.

A Note About Style

Like in homework, we will be checking your code based on whether it follows the 15-112 style guide. Gradescope may deduct points from your overall score 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 has already started, so this is also a way to practice your good style!

  1. carrylessAdd(x, y) [10 pts]
    First, you may wish to read the first page (page 44) from here about Carryless Arithmetic. Or, just understand that carryless addition is what it sounds like -- regular addition, only with the carry from each column ignored. So, for example, if we carryless-ly add 8+7, we get 5 (ignore the carry). And if we add 18+27, we get 35 (still ignore the carry). With this in mind, write the function carrylessAdd(x, y) that takes two non-negative integers x and y and returns their carryless sum. As the paper demonstrates, carrylessAdd(785, 376) returns 51.

  2. destructiveRemoveRepeats(L) [10 pts]
    Write the function destructiveRemoveRepeats(L), that removes any repeating elements in L, 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. patternedMessage(message, pattern)[10 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:

    callresult
    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:

    callresult
    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

  4. bestStudentAndAvg(gradebook) [10 pts]
    Background: for this problem, a "gradebook" is a multiline string where each row contains a student's name (one word, all lowercase) followed by one or more comma-separated integer grades. A gradebook always contains at least one student, and each row always contains at least one grade. Gradebooks can also contain blank lines and lines starting with the "#" character, which should be ignored.

    With this in mind, write the function bestStudentAndAvg(gradebook), that takes a gradebook and finds the student with the best average (ignoring the case where there is a tie) and returns a string of that student's name followed by a colon (":") followed by his/her average (rounded to the nearest integer). For example, here is a test case:
    gradebook = """ # ignore blank lines and lines starting with #'s wilma,91,93 fred,80,85,90,95,100 betty,88 """ assert(bestStudentAndAvg(gradebook) == "wilma:92"))
    Note: you most likely will want to use both s.split(",") and s.splitlines() in your solution.

  5. extractAssignStatements(text) [10 pts]
    Write the function extractAssignStatements(text) that extracts all valid assignment statements from string text. A valid assignment statement is of the form lhs=rhs. The left-hand side (lhs) of the statement must be a variable name. For simplicity, only alphabetical characters are allowed in the variable name (that is, no numbers or symbols). The right-hand side (rhs) must be a non-negative integer. Between both sides, only the character '=' or spaces can occur. The function should return a list of tuples, (lhs, rhs) where lhs is a string and rhs is an integer. Here are some examples:
    assert(extractAssignStatements("hello,class=15112 and anotherVar=42. The end") == [('class','15112'), ('anotherVar','42')]) assert(extractAssignStatements(" .-, anotherVar = 42.") == [('anotherVar','42')]) assert(extractAssignStatements("a=98,b=23232;c=543- --=- d=-42.23") == [('a','98'), ('b', '23232'),('c','543')])

  6. bestScrabbleScore(dictionary, letterScores, hand) [10 pts]
    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 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) -- 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: 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.

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