For this assignment, you will create a Python source file (that is, a text file containing Python code) for each of the problems below. You should store all of these files in a folder named pa5, which you will zip up and submit.
Remember to comment your code, choose appropriate variable names, and use consistent spacing and indentation!
Note: You are responsible for protecting your solutions to these problems from being seen by other students, either physically (e.g., by looking over your shoulder) or electronically.
Test your functions to make sure they behave as shown in the examples. Before submitting your code, you should also download this file: test_pa5.py and do the following:
>>> from test_pa5 import * (OR > python3 -i test_pa5.py) >>> test_all()
These tests will automatically check that your function returns the correct value. If you don't see the message "All tests completed", then there is something that needs to be fixed for you to get full credit. You can isolate the problem as follows:
>>> test_select_strings() Finished testing select_strings() ...
and so forth. There is a test function for each of the functions you are to write. Please note: Passing the tests does not guarantee you full credit. There may be cases not covered in the tests we give you, and there are other requirements for your code that are stated in this assignment but not checked by the test file. It is your responsibility to think about whether your function definitions satisfy the requirements.
Note: the purpose of this assignment is to develop your ability to think and program recursively. No credit will be given for non-recursive programs, even if they return correct answers.
[2 points] For this problem you will
write a recursive function select_strings(names,
letter) that takes a list of strings and a
letter and returns a list of all the strings in the
list that end with the given letter. The output list
must contain the strings in the same order in which
they occur in the input list, and the input list must
be unchanged. To determine the last character of a
string, you can use indexing just as you do for the
last element of a list. But beware, there might be
empty strings in the list! Save your function definition
in a file called select_strings.py
Example:
>>> names = ['Christine', 'Yi', 'Mark', 'Vivek', 'Jonathan', 'Maung', 'David', 'Patrick',\ 'Elliott', 'Ronnie', 'Felicia', 'Yuto', 'Oliver', 'Daniel', 'Julie', 'Andrew',\ 'Shailja', 'Kevin', 'Aline', 'Abhiram', 'Meena', 'Jenna', 'Rachel'] >>> first_name = names[0] >>> first_name[-1] 'e' >>> select_strings(names, 'a') ['Felicia', 'Shailja', 'Meena', 'Jenna'] >>> select_strings(names, 'A') [] >>> select_strings(names, 'w') ['Andrew'] >>> select_strings(names, 'r') ['Oliver'] >>> select_strings([], 'a') [] >>>
Some hints: To review how to do recursion on lists and construct lists as answers, look at the code for reversing a list from Lecture Notes (unit05-1-Recursion.pdf). Be sure to review how a recursive function should break a list apart into the first element of the list and the rest of the list.
[2 points] For this problem you will
write almost the same function as before, and put it
in the same file (select_strings.py), but the
output list should contain the strings in reverse
order. There are many ways to accomplish this, but we
want you to do it by breaking the list
apart, not into the first element and the rest, but
into the last element and the rest, like this:
last = names[-1] rest = names[:-1]
Name your function as follows: select_strings_backward(names,
letter). Do not use the reverse
function in any form. For any credit, your function must
create its output in the required order as it
processes its input.
Example:
>>> names = ['Christine', 'Yi', 'Mark', 'Vivek', 'Jonathan', 'Maung', 'David', 'Patrick',\ 'Elliott', 'Ronnie', 'Felicia', 'Yuto', 'Oliver', 'Daniel', 'Julie', 'Andrew',\ 'Shailja', 'Kevin', 'Aline', 'Abhiram', 'Meena', 'Jenna', 'Rachel'] >>> select_strings_backward(names, 'a') ['Jenna', 'Meena', 'Shailja', 'Felicia'] >>> select_strings_backward(names, 'A') [] >>> select_strings_backward(names, 'l') ['Rachel', 'Daniel'] >>> select_strings_backward(names, 'w') ['Andrew'] >>> select_strings_backward(names, 'd') ['David'] >>> select_strings_backward(names, 'n') ['Kevin', Jonathan'] >>> select_strings_backward([], 'n') [] >>>
[3 points] Recursion on more than one input list.
In shuffle.py, write a recursive Python function shuffle(list1, list2) that takes two lists list1 and list2 as input and returns a new list where the elements from list1 and list2 are shuffled together into one list. The two input lists must be unchanged.
The elements in the output list must be drawn alternately from list1 and list2. If one list is longer than the other, the extra elements should not appear in the output. You are not allowed to compare the lengths of the two input lists to each other. You may use the len function only to check for an empty list. (Obeying this restriction gives you the opportunity to write a really, really simple function definition. Remember that you have the Boolean operators and and or available.)
Example:
>>> l1 = [1,3,5,7] >>> l2 = [2,4,6,8] >>> shuffle(l1,l2) [1, 2, 3, 4, 5, 6, 7, 8] >>> shuffle(l1[:3], l2) [1, 2, 3, 4, 5, 6] >>> shuffle(l1, l2[:2]) [1, 2, 3, 4] >>> shuffle(l2, []) []
Write shuffle(list1, list2) as a recursive function. The recursive case of this function must call shuffle recursively to form a shuffled list from the tails of the two lists. What is the base case and what should it do? How will you combine the result of the recursive call with the heads of list1 and list2?
[3 points] Accumulating a value while building an output list
The cumulative product for a list of integers is another list such that the element at the \(i^{th}\) index of the cumulative product is the product of the first \(i + 1\) elements of the original list. For example, the cumulative product for the list \([3,5,4,7]\) is the list \([3,15,60,420]\). The element at index 0 in the cumulative sum is the same as the element at index 0 of the input list (i.e. 3), the element at index 1 of the cumulative sum is the sum of the elements at indices 0 and 1 of the input list (i.e. 3*5 = 15) etc. If the input list is empty, the cumulative product is also empty.
In the file cumulative_product.py, define a function cumulative_product(nums) that takes a list of numbers as a parameter and returns the cumulative product, leaving the original list unchanged.
Note: We require the use of recursion (no loops!), but you can use it in any way you want. There is a lot of freedom in writing the cumulative_product function. Your code will likely have more than one function, one of which is a recursive helper function. For example you might have something like this:
def cumulative_product_helper(nums, subtotal):
# your code here
def cumulative_product(nums):
return cumulative_product_helper(nums, 0)
This is not the only way of designing a solution, but it is a common way.
Example:
>>> from cumulative_product import * (OR bash-3.2$ python3 -i cumulative_product.py) >>> vals = [5, 4, 3, 2, 1] >>> cumulative_product(vals) [5, 20, 60, 120, 120] >>> vals [5, 20, 60, 120, 120] >>> cumulative_product(vals[1:3]) [4, 12] >>> cumulative_product(vals[1:4]) [4, 12, 24] >>> cumulative_product(vals[2:5]) [3, 6, 6] >>> vals = list(range(-9, 0)) >>> vals [-9, -8, -7, -6, -5, -4, -3, -2, -1] >>> cumulative_product(vals) [-9, 72, -504, 3024, -15120, 60480, -181440, 362880, -362880] >>> vals = [-1, 1, -2, 2, -3, 3, 0, 4] >>> cumulative_product(vals) [-1, -1, 2, 4, -12, -36, 0, 0] >>> vals = [0]*10 >>> vals [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] >>> cumulative_product(vals) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
You should now have a pa5 directory that contains the files select_strings.py, shuffle.py, and cumulative_product.py, each containing the corresponding function(s). Zip up your directory and hand it in.