CS 111
Summer 2 2018

# Problem Set 5

## Preliminaries

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

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email `cs111-staff@cs.bu.edu`.

Make sure to submit your work on Apollo, following the procedures found at the end of the assignment.

due by 9:00 p.m. on Thursday, July 12, 2018

### Problem 1: Caesar cipher and decipher

40 points; pair-optional

This is the only problem of the assignment that you may complete with a partner. 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 asks you to write two functions using aspects of functional programming that we have covered in class: conditionals, recursion, map, and/or list comprehensions. The guidelines that we gave you for [Problem Set 1, problem 3][ps1pr3] also apply here, except you are allowed to use map and/or list comprehensions instead of recursion.

Begin by downloading the file `ps5pr1.py` and opening it in IDLE. 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_probability` 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!'
```

You can write this function any way you like as long as you use functional programming–conditionals, recursion, map, and/or list comprehensions.

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 `ps3pr2.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 that is nearly identical to `transcribe` function that you wrote for Problem Set 3.

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.'
```
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_probability(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 need to do something like this:

```options = [_____________ for n in range(26)]
```
• Next, you should use the “list-of-lists” technique that we discussed in lecture to give each option a score:

```scored_options = [______________ for x in options]
```

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. 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 2: Algorithm design

40 points; individual-only

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

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

The guidelines that we gave you for Problem Set 2, problem 3 also apply here, except that you will be using list comprehensions for some of the functions. In particular, make sure that you use the exact function names that we have specified.

1. Write a function `abs_list_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 absolute values of the numbers in `values`. For example:

```>>> abs_list_lc([-2, 5, 8, -3])
[2, 5, 8, 3]
```

Use the built-in `abs` function (which returns the absolute value of a single number), in conjunction with a list comprehension. This version of the function may not use recursion.

2. Write a function `abs_list_rec(values)` that takes as input a list of numbers called `values`, and that uses recursion to create and return a list containing the absolute values 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:

```>>> abs_list_rec([-2, 5, 8, -3])
[2, 5, 8, 3]
```

Here again, you should use the built-in `abs` function, but in conjunction with recursion.
This version of the function may not use a list comprehension.

3. Write a function called `num_greater(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 greater than `threshold`. For example:

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

Here again, your function should use either a list comprehension or `map` combined with `list`. Hint: We looked at a function similar to this one in the first lecture on list comprehensions.

4. Write a function called `most_vowels(words)` that takes a list of strings called `words` and returns the string in the list with the most vowels. You may assume that the strings only contain lowercase letters. For example:

```>>> most_vowels(['vowels', 'are', 'amazing', 'things'])
'amazing'
>>> most_vowels(['obama', 'bush', 'clinton'])
'obama'
```

The function that you write should use the `num_vowels` function from lecture as a helper function. Copy `num_vowels` into your `ps5pr2.py` file, adjusting the indentation as needed.

Next, write your `most_vowels` function. We strongly encourage you to use the list-of-lists technique that we discussed in class, but you can use recursion instead if you prefer.

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

### Problem 3: More algorithm design!

20 points; individual-only

This problem asks you to write three additional functions using the functional-programming techniques that we have discussed in lecture.

In IDLE, use the File -> New Window 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.

In writing the functions described below, you should continue to follow the guidelines from problem 2.

Here are the descriptions of the functions:

1. Write a function `rem_last(c, s)` that takes as inputs a character `c` and a string `s` and that uses recursion to create and return a version of `s` in which the last occurrence of `c` (if any) has been removed. For example:

```>>> rem_last('a', 'banana')
'banan'
>>> rem_last('e', 'repeat')
'repat'
>>> rem_last('r', 'terriers')
'terries'
>>> rem_last('x', 'hello')    # no occurrences
'hello'
>>> rem_last('a', '')
''
```

Notes:

• In the recursive call, you will need to take a different approach to reducing the problem than we have typically taken when recursively processing a string.

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

• This function is somewhat similar to the `rem_first` function that we discussed in lecture, although that function operated on lists instead of strings, and it removed the first occurrence of an element rather than the last. If you base your code on `rem_first`, make sure to change its name to `rem_last` – both in the function header, and in the recursive call!

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

## Submitting Your Work

You should use Apollo to submit the following files:

• your modified `ps5pr1.py` file containing your answers for Problem 1; if you worked with a partner, make sure that you each submit a copy of your joint work, and that you include comments at the top of the file specifying the name and email of your partner
• your `ps5pr2.py` file containing your code for Problem 2
• your `ps5pr3.py` file containing your code for Problem 3

Warnings

• Make sure to use these exact file names, or Apollo will not accept your files. If Apollo reports that a file does not have the correct name, you should rename the file using the name listed in the assignment or on the Apollo upload page.

• If you make any last-minute changes to one of your Python files (e.g., adding additional comments), you should run the file in IDLE after you make the changes to ensure that it still runs correctly. Even seemingly minor changes can cause your code to become unrunnable.

• If you submit an unrunnable file, Apollo will accept your file, but it will print a warning message. If time permits, you are strongly encouraged to fix your file and resubmit. Otherwise, your code will fail most if not all of our tests.

Here are the steps:

1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
2. Find the appropriate problem set section on the main page and click “Upload files”.
3. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
4. Click the “Upload” button at the bottom of the page.
5. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
Note: If you encounter problems with Apollo, close your browser and try again. If possible, you may also want to wait an hour or two before retrying. If you are unable to submit and it is close to the deadline, email your homework before the deadline to `cs111-staff@cs.bu.edu`.