Problem Set 5

due by 10 p.m. on Saturday, September 16, 2023

suggested self-deadline of Friday September 15, 2023

Preliminaries
Submitting Your Work

Preliminaries

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

This entire problem set is pair-optional or group-optional. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

If you have questions while working on this assignment, please come to TA Help Hours, office hours, or post them on Piazza.

Important note regarding test cases and Gradescope:

You must test each function after you write it. Here are two ways to do so:
- Run your file after you finish a given function. Doing so will bring you to the Shell, where you can call the function using different inputs and check to see that you obtain the correct outputs.
- Add test calls to the bottom of your file, inside the if __name__ == '__main__' control structure. For example:
```
if __name__ == '__main__':

    print("mystery(6,7) returned", mystery(6,7))
```
  These tests will be called every time that you run the file, which will save you from having to enter the tests yourself. We have given you an example of one such test in the starter file.
You must not leave any print statements in the global scope. This will cause an error with the Gradescope autograder. Make sure all of your print statements are inside a function scope or inside the if __name__ == '__main__' control structure.

Problem 1: Tracing list comprehensions

*10 points;

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

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

*30 points;

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

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 'cu see you']
```
  so that it produces the list [True, True, False, True, False, False, False, False, False, True]. Note that the expression 'cu see 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 continue to follow the guidelines from problem set 3, but you should use list comprehensions and not recursion.

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!
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', 'Worcester', 'Washington', 'Houston']
>>> shorter_than(7, cities)
['Boston']
>>> shorter_than(6, cities)
[]
```
Hint: Your list comprehension will need an if clause.

Problem 3: Algorithm design

40 points

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 VS Code, 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.

The guidelines that we gave you for Problem Set 2, Problem 1 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.

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.
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.
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
```
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.
The final function of this problem does not require the use of either recursion or a list comprension. Rather, it will allow you to practice using conditional logic and variable assignment to gradually build up a return value.

Write a function price_string(cents) that takes as input a positive integer cents representing a price given in cents, and that constructs and returns a string in which the price is expressed as a combination of dollars and cents.

In general, the format of the returned string should be 'd dollars, c cents', where d is the whole number of dollars in the price and c is the remaining cents. For example:
```
>>> price_string(452)
'4 dollars, 52 cents'
>>> price_string(871)
'8 dollars, 71 cents'
```
However, there are two additional rules that you must observe:
- If either component of the price is 0, it should be omitted:
```
>>> price_string(27)
'27 cents'
>>> price_string(300)
'3 dollars'
```
  (Because we assume that the input cents is positive, it will never be the case that both of the components are 0!)
- If either component of the price is 1, you should omit the 's' from the word for that component:
```
>>> price_string(201)
'2 dollars, 1 cent'
>>> price_string(117)
'1 dollar, 17 cents'
>>> price_string(101)
'1 dollar, 1 cent'
```

Important Guidelines

You should begin by copying the following template into your file:

def price_string(cents):
    """ docstring goes here """
    d = _______________   # compute whole number of dollars
    c = _______________   # compute remaining cents

    price = ''            # initial value of the price string

    ## add code below to build up the price string (using concatenation)

    return price

You should begin by replacing the two blanks with expressions that will compute the values of d (the whole number of dollars) and c (the remaining cents), based on the value of the parameter cents.
Next, you should add code to determine the appropriate value of the variable price, which is the string that the function will return. We have given you a line assigns an empty string to price as its initial value. You should use conditional execution and string concatenation to gradually build up the final value of this variable. You will need to use assignment statements that look like this:
```
price = price + ...
```
You can use the built-in str() function to turn numbers into strings. For example, str(d) will turn the number represented by the variable d into a string.
Your function must limit itself to the single return statement that we have given you at the very end of the function. You will lose points if you use more than one return statement in this function.

Submitting Your Work

You should use Gradesope to submit the following files:

your modified 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

Warnings

Make sure to use these exact file names, or Gradescope will not accept your files. If Gradescope 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 Gradescope 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 VS Code 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, Gradescope will accept your file, but it will not be able to auto-grade it. 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.