Problem Set 5: List Comprehensions and Algorithm Design

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

For each problem in this problem set, we will be writing or evaluating some Python code. You are encouraged to use the Spyder IDE which will be discussed/presented in class, but you are welcome to use another IDE if you choose.

If you have questions while working on this assignment, please post them on Piazza! This is the best way to get a quick response from your classmates and the course staff.

Problem 1: Tracing list comprehensions

10 points; individual-only

Begin by downloading this file: ps5pr1.txt, and fill in your answers in this text file.

1. Consider the following Python statement:

   lc = [y ** 2 for y in range(5)]
   

   In section 1-1 of ps5pr1, we have given you a table that you should complete to illustrate the execution of the list comprehension.

   More specifically, for each new value of the list comprehension’s “runner” variable, you should show the current partial result of the list comprehension. For example, if we were tracing the list comprehension

   lc = [2*x for x in [3, 5, 7]]
   

   the table would look like this:

     x  |  lc
   ------------
     3  | [6,
     5  | [6, 10,
     7  | [6, 10, 14]
   

   You may not need all of the rows provided in the tables, but please do not remove any rows (you may add).

2. Consider the following Python program:

   def mystery(x):
       lc = [y % 3 for y in range(x)]   
       return sum(lc)
   
   x = 4
   y = 2
   print(x, y)
   y = mystery(y)
   print(x, y)
   x = mystery(x)
   print(x, y)
   

   In section 2-2 of ps5pr1, we have given you tables that you should complete to illustrate the execution of the program.

   We have started some of the tables for you. You should:

   • complete the first table so that it illustrates how the values of the global variables change over time

   • complete the second table so that it illustrates how the values of the local variables change over time. In the column for lc, you should show the how the result of the list comprehension is gradually built up, just as you did in the first part of this problem.

   • complete the output table so that it shows the output of the program.

   You may not need all of the rows provided in the tables, but please do not remove or add any rows.

Problem 2: Writing list comprehensions

15 points; individual-only

Begin by downloading the file ps5pr2.py and opening it in Spyder.

1. LC puzzles! You will see that the file includes several incomplete list comprehensions. Complete them by filling in the blanks to produce the results specified below.

   1. Complete the following list comprehension

      lc1 = [            for x in range(5)]
      

      so that it produces the list [0, 2, 4, 6, 8].

   2. Complete the list comprehension shown below

      words = ['hello', 'world', 'how', 'goes', 'it?']
      lc2 = [            for w in words]
      

      so that it produces the list ['e', 'o', 'o', 'o', 't'].

   3. Complete the following list comprehension

      lc3 = [            for word in ['hello', 'bye', 'no']]
      

      so that it produces the list ['olleholleh', 'eybeyb', 'onon']. Hint: Use skip-slicing.

   4. Complete the following list comprehension

      lc4 = [            for x in range(1, 10) if               ]
      

      so that it produces the list [4, 16, 36, 64]. Note that you need to fill in two blanks for this one: the expression before the for, and the expression after the if.

   5. Complete the following list comprehension

      lc5 = [            for c in 'bu be you']
      

      so that it produces the list [True, True, False, True, False, False, False, False, True]. Note that the expression 'bu be you' is a string, not a list.

   Test your list comprehensions by running ps5pr2.py and checking to see that the correct values are printed.

The next two parts of the problem involve writing functions. You should use list comprehensions and not recursion.

2. Write a function called powers_of(base, count) that takes as inputs a number base and a positive integer count, and that uses a list comprehension to construct and return a list containing the first count powers of base, beginning with the 0th power. For example:

   >>> powers_of(2, 5)        
   [1, 2, 4, 8, 16]
   >>> print(powers_of(3, 4))
   [1, 3, 9, 27]
   

   Warning

   Make sure that your function returns the correct value rather than printing it. If your function is printing the return value, you will see the word None as part of the output for the second test above. If you are seeing None in your output, you must fix your function so that it uses a return statement rather than a print statement.

   Don’t forget to include a docstring!

3. Write a function called shorter_than(n, wordlist) that takes as inputs an integer n and a list of strings wordlist, and that uses a list comprehension to construct and return a list consisting of all words from wordlist that are shorter than n. For example:

   >>> shorter_than(4, ['only', 'recursion', 'on', 'the', 'brain'])
   ['on', 'the']       
   >>> cities = ['Boston', 'Chicago', 'Washington', 'Houston']
   >>> shorter_than(7, cities)
   ['Boston']
   >>> shorter_than(6, cities)
   []
   

   Hint: Your list comprehension will need an if clause.

Problem 3: Algorithm design, part 1

20 points; individual-only*

See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

This problem provides additional practice with list comprehensions and recursion. It also provides an opportunity to use the list-of-lists technique that we discussed in lecture.

In Spyder, use the File -> New File menu option to open a new editor window for your code, and save it using the name ps5pr3.py. Make sure to specify the .py extension.

Make sure that you use the exact function names that we have specified.

1. Write a function cube_all_lc(values) that takes as input a list of numbers called values, and that uses a list comprehension to create and return a list containing the cubes of the numbers in values (i.e., the numbers raised to the third power). For example:

   >>> cube_all_lc([-2, 5, 4, -3])
   [-8, 125, 64, -27]
   >>> print(cube_all_lc([1, 2, 3]))
   [1, 8, 27]
   

   This version of the function may not use recursion.

2. Write a function cube_all_rec(values) that takes as input a list of numbers called values, and that uses recursion to create and return a list containing the cubes of the numbers in values. In other words, this function will do the same thing as the previous function, but it must use recursion instead of a list comprehension. For example:

   >>> cube_all_rec([-2, 5, 4, -3])
   [-8, 125, 64, -27]
   >>> print(cube_all_rec([1, 2, 3]))
   [1, 8, 27]
   

   This version of the function may not use a list comprehension.

3. Write a function called num_larger(threshold, values) that takes as inputs a number threshold and a list of numbers values, and that returns the number of elements of values that are larger than threshold. You may use either a list comprehension or recursion. For example:

   >>> num_larger(5, [1, 7, 3, 5, 10])   # there are 2 values > 5
   2
   >>> num_larger(2, [1, 7, 3, 5, 10])   # there are 4 values > 2
   4
   >>> print(num_larger(10, [1, 7, 3, 5, 10]))   # there are 0 values > 10
   0
   

4. Write a function called most_consonants(words) that takes a list of strings called words and returns the string in the list with the most consonants (i.e., the most letters that are not vowels). You may assume that the strings only contain lowercase letters. For example:

   >>> most_consonants(['python', 'is', 'such', 'fun'])
   'python'
   >>> most_consonants(['oooooooh', 'i', 'see', 'now'])
   'now'
   

   The function that you write should use the num_vowels function from lecture as a helper function, along with either a list comprehension or recursion. Copy num_vowels into your ps5pr3.py file, adjusting the indentation as needed.

   Note: You don’t need to worry about cases in which two or more words are tied for the most consonants.

Problem 4: Caesar cipher and decipher

20 points; individual-only

This problem asks you to write two functions using aspects of functional programming that we have covered in class: conditionals, recursion, and/or list comprehensions. You are allowed to use list comprehensions instead of recursion.

Do not use loops or any other techniques that have not been taught in class.

Make sure that you use the exact function names that we have specified.

Begin by downloading the file ps5pr4.py and opening it in Spyder. We have given you:

• a template for a helper function called rot that we recommend that you write in conjunction with your work on the first function below.
• another (already completed) helper function called letter_probrability that you may find useful when writing the second function.

Here are the descriptions of the two functions:

1. Write a function encipher(s, n) that takes as inputs an arbitrary string s and a non-negative integer n between 0 and 25, and that returns a new string in which the letters in s have been “rotated” by n characters forward in the alphabet, wrapping around as needed. For example:

   >>> encipher('hello', 1)
   'ifmmp'
   >>> encipher('hello', 2)
   'jgnnq'
   >>> encipher('hello', 4)
   'lipps'
   

   Upper-case letters should be “rotated” to upper-case letters, even if you need to wrap around. For example:

   >>> encipher('XYZ', 3)
   'ABC'
   

   Lower-case letters should be “rotated” to lower-case letters:

   >>> encipher('xyz', 3)
   'abc'
   

   Non-alphabetic characters should be left unchanged:

   >>> encipher('#caesar!', 2)
   '#ecguct!'
   

   Hints/reminders:

   • You can use the built-in functions ord and chr convert from single-character strings to integers and back:

     >>> ord('a')
     97
     >>> chr(97)
     'a'
     

   • You can use the following test to determine if a character is between 'a' and 'z' in the alphabet:

     if 'a' <= c <= 'z':
     

     A similar test will work for upper-case letters.

   • We recommend writing a helper function rot(c, n) that rotates a single character c forward by n spots in the alphabet. We have given you a template for this helper function in ps5pr4.py that checks to ensure that c is a single-character string. We wrote rot13(c) in lecture; rot(c, n) will be very close to rot13(c)! You can test your rot(c, n) as follows:

     >>> rot('a', 1)
     'b'
     >>> print(rot('a', 1))
     b
     >>> rot('y', 2)
     'a'
     >>> rot('A', 3)
     'D'
     >>> rot('Y', 3)
     'B'
     >>> rot('!', 4)
     '!'
     

   • Once you have rot(c, n), you can write a recursive encipher function.

   Once you think you have everything working, here are three more examples to try:

   >>> encipher('xyza', 1)
   'yzab'
   >>> encipher('Z A', 2)
   'B C'
   >>> encipher('Caesar cipher? I prefer Caesar salad.', 25)
   'Bzdrzq bhogdq? H oqdedq Bzdrzq rzkzc.'
   

Deciphering

2. Write a function decipher(s) that takes as input an arbitrary string s that has already been enciphered by having its characters “rotated” by some amount (possibly 0). decipher should return, to the best of its ability, the original English string, which will be some rotation (possibly 0) of the input string s. For example:

   >>> decipher('Bzdrzq bhogdq? H oqdedq Bzdrzq rzkzc.')
   'Caesar cipher? I prefer Caesar salad.'
   

   Note that decipher does not take a number specifying the amount of rotation! Rather, it should determine the rotation (out of all possible rotations) that produces the most plausible English string. We have given you a helper function called letter_prob(c) that takes a single-character string c and returns a value that is based on the frequency with which that character appears in English texts. That function provides the basis for a number of possible approaches for judging the “Englishness” of a given rotation, but you are welcome to try an alternative approach. Use a short comment above your decipher function to describe your overall approach.

   Your function does not need to be perfect. Some strings have more than one English “deciphering.” In addition, it’s difficult if not impossible to handle very short strings correctly. However, your function should work almost all of the time on long stretches of English text (e.g., sentences of 8 or more words). You will not lose any credit for not getting the correct deciphering of a single word or short phrase.

   Here are two more examples:

   >>> decipher('Hu lkbjhapvu pz doha ylthpuz hmaly dl mvynla lclyfaopun dl ohcl slhyulk.')
   'An education is what remains after we forget everything we have learned.'
   >>> decipher('python')
   'eniwdc'
   

   Note that our version of decipher gets the second example wrong! (When you provide English text as the input, you should ideally get back the text itself–i.e., a string that has been deciphered using a rotation of 0–but that didn’t happen in this case, which is completely okay!) It’s possible that your version of decipher will return a different value here. It might even return 'python', but it’s okay if it doesn’t.

   Hints/reminders:

   • Since deciphering involves rotating the characters, you already have the function needed to create each of the possible decipherings!

   • We recommend that you start by using a list comprehension to create a list of all possible decipherings. You will consider all possible shifts – from 0 to 25 – that could be used to create a deciphering. Assign the result of this list comprehension to a variable.

   • Next, you should use the “list-of-lists” technique that we discussed in lecture to give each possible deciphering a score. The best_word function from lecture is a good example of this technique.

     As discussed above, the score that you assign to a given deciphering should provide some measure of its “Englishness.” You are welcome to write additional helper functions to assist you in the scoring and in the other steps involved.

   • After you have scored all of the options, you should choose the option with the highest score. Here again, the best_word function from lecture is a good model for this.

   • Once you think you have a working decipher, try it on the following string:

     'kwvozibctibqwva izm qv wzlmz nwz iv mfkmttmvb rwj'
     

Problem 5: Algorithm design, part 2

20 points; individual-only

This problem asks you to write three additional functions using the functional-programming (recursive) techniques that we have discussed in lecture. Do not use loops or any other techniques that have not been taught in class.

In Spyder, use the File -> New Window menu option to open a new editor window for your code, and save it using the name ps5pr5.py. Make sure to specify the .py extension.

Here are the descriptions of the functions:

1. Write a function index(elem, seq) that takes as inputs an element elem and a sequence seq, and that uses recursion to find and return the index of the first occurrence of elem in seq. The sequence seq can be either a list or a string. If seq is a string, elem will be a single-character string; if seq is a list, elem can be any value. Don’t forget that the index of the first element in a sequence is 0.

   Important notes:

   • If elem is not an element of seq, the function should return -1.

   • You may not use the in operator in this function.

   Here are some examples:

   >>> index(5, [4, 10, 5, 3, 7, 5])
   2
   >>> index('hi', ['well', 'hi', 'there'])
   1
   >>> index('b', 'banana')
   0
   >>> index('a', 'banana')
   1
   >>> index('i', 'team')
   -1
   >>> print(index('hi', ['hello', 111, True]))
   -1
   >>> print(index('a', ''))      # the empty string 
   -1
   >>> print(index(42, []))       # the empty list
   -1
   

   Hints:

   • You will need more than one base case for this function.

   • To figure out the logic of the function, we strongly encourage you to begin by considering concrete cases. Ask yourself the types of design questions that we have asked in lecture and lab, and use the answers to those questions to determine what the function should do.

   • When deciding what to do after the recursive call returns, you will need to base your decision on the result of the recursive call.

The Jotto Game

2. Write a function jscore(s1, s2) that takes two strings s1 and s2 as inputs and returns the Jotto score of s1 compared with s2 – i.e., the number of characters in s1 that are shared by s2. The positions and the order of the shared characters within each string do not matter. Repeated letters are counted multiple times, as long as they appear multiple times in both strings. For example:

   >>> jscore('diner', 'syrup')            # just the 'r'
   1
   >>> jscore('always', 'bananas')         # two 'a's and one 's'
   3
   >>> jscore('always', 'walking')         # one 'a', 'l', and 'w'
   3
   >>> jscore('recursion', 'excursion')    # everything but the 'r' in s1 is shared by s2
   8
   >>> jscore('recursion', '')             # 0 because s2 is empty
   0
   

   Notes/hints:

   • Unlike the words in traditional Jotto, which always have five letters, there are no restrictions on the lengths of the input strings s1 and s2.

   • If either s1 or s2 is the empty string, the Jotto score is 0.

   • You can write the function any way you like as long as you use functional programming.

   • We encourage you to consider using one or more helper functions. In particular, one possible approach involves using a function like the rem_first function that we considered in lecture. However, you would need to rework that function so that it operates on a string rather than a list.

   • This line turns out to be useful:

     if s1[0] in s2:
     

Subsequences and Longest Common Subsequence

3. Write a function lcs(s1, s2) that takes two strings s1 and s2 and returns the longest common subsequence (LCS) that they share. The LCS is a string whose letters appear in both s1 and s2; these letters must appear in the same order in both s1 and s2, but not necessarily consecutively. For example:

   >>> lcs('human', 'chimp')          # 'h' comes before 'm' in both strings
   'hm'
   >>> lcs('gattaca', 'tacgaacta')
   'gaaca'
   >>> lcs('wow', 'whew')
   'ww'
   >>> lcs('', 'whew')                 # first string is empty
   ''
   >>> lcs('abcdefgh', 'efghabcd')     # tie! 'efgh' would also be fine
   'abcd'
   

   Notes/hints:

   • If either s1 or s2 is the empty string, the LCS is also the empty string.

   • If there are ties for the LCS, any one of the ties is acceptable. In the last example above, a return value of 'efgh' would also have been fine, because both 'abcd' and 'efgh' are common subsequences of the two strings, and both of these subsequences have a length of 4.

   • Here’s one possible strategy for the recursive case (after you have tested and confirmed that your base case(s) are correct):

     • If the first characters in the two strings match, include that character in the LCS, and process the remaining characters of the two strings.

     • If the first characters don’t match, make two recursive calls: one that eliminates the first character in s1, and one that eliminates the first character in s2. Your code will look something like this:

       result1 = lcs(s1[1:], s2)
       result2 = lcs(___, ___)
       

       where you should fill in the blanks in the appropriate way.

     • Return the better of these two results.

   • WARNING: The previously described strategy has a high branching factor, on the order of O(n!), where n is the length of the string). For long strings, this strategy could require an extremely large number of recursive calls, which will make it slow to complete.

     • For example, the call to lcs('mellow yellow', 'watermellon pie') required 24744433 recursive function calls and took about 8.38 seconds on my computer.

     • We can do better!

       Suppose we are comparing s1 = 'always' and s2 = 'walking'.

       The next simpler case is not to compare: s1 = 'lways' and s2 = 'walking' or s1 = 'always' and s2 = 'alking'.

       Rather, the simpler sub case is to compare all of the characters in each string that occur after the first occurence of the common character. That is, we should compare: s1 = 'lways' and s2 = 'lking' —- note that we removed all characters up to and including the 'a' from s1, and up to and including the 'a' from s2.

       In the video above, we suggest using a helper function rem_upto, which would produce the new s2 with only the characters in s2 that appear after the appearance of s1[0].

       With the revised strategy, the call to lcs('mellow yellow', 'watermellon pie') required 181 recursive calls, and took about 0.00021 seconds to complete.

Submitting Your Work

You should use Gradesope to submit the following files:

• your ps5pr1.txt file containing your solutions for Problem 1
• your ps5pr2.py file containing your solutions for Problem 2
• your ps5pr3.py file containing your solutions for Problem 3
• your ps5pr4.py file containing your solutions for Problem 4
• your ps5pr5.py file containing your solutions for Problem 5