%config InteractiveShell.ast_node_interactivity="none"
def f(globals, locals):
import base64
code="ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ=="
exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f
Lecture 8, Lab A: More Recursion¶
All of today's exercises should use recursion, unless the question says otherwise. As taught in lecture, make sure to always define your base case(s) and recursive case(s).
# Run this cell so you can check your answers below
def check(actual, expected):
if expected != actual:
print(
f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
Warm-up¶
Count how many words that start with a capital letter the string contains.
def how_many_capital_words(sentence):
"""Returns the number of capital words in the sentence.
Input: sentence (str).
Output: The number of capital words in sentence (int).
"""
# Write your base case here
# Write your recursive/other cases here
# Test cases.
check(how_many_capital_words("I like jamcoders"), 1)
check(how_many_capital_words("i like Jamcoders a Lot"), 2)
1. Recursion with Lists¶
1.1 sort_pairs¶
Given a list of pairs of integers, sort each member of the pair in ascending order.
Feel free to skip this question.
def sort_pairs(lst):
"""Sorts each pair within lst, modifying the pairs themselves.
Input: A list of pairs (List[Pair[int, int]]).
Output: None. The function should modify the pairs.
"""
# Write your base case here
# Write your recursive/other cases here
check(sort_pairs([[1, 3], [5, 2], [3, 0]]), [[1, 3], [2, 5], [0, 3]])
check(sort_pairs([]), [])
1.2 deep_add¶
Add all the integers in the list (whose elements might also be lists of lists).
def deep_add(lst):
"""Finds the sum of all integers in a list whose members may be other lists.
Input: A deep list, whose elements are integers or other deep lists.
Output: The sum of all integers (int).
"""
# Write your base case here
# Write your recursive/other cases here
# Test cases.
check(deep_add([3, 5, [1, 3], 6]), 18)
check(deep_add([2]), 2)
1.3 replace_nat¶
Unfortunately, Natnael can't. However, there's a good replacement, Jabari. In the following list, replace every instance of Natnael with Jabari. (Make sure the test passes!)
def replace_nat(lst):
"""Replace every instance of "Natnael" in lst with "Jabari".
Input: lst, the original list of names (List[str]).
Output: A list with all names replaced (List[str]).
"""
# Write your base case here
# Write your recursive/other cases here
check(replace_nat(["Barak", "Mansingh", "Nelson", "Jabari"]), ["Barak", "Mansingh", "Nelson", "Tyler"])
1.4 find_max_population¶
The following is a list of places in Jamaica and their population. Each entry is a list with two elements: the first is the name of the place, and the second is the population.
[("Spanish Town", 147152),("Kingston", 1041203), ("Montego Bay", 110115), ("Portmore", 182153)].
The function should return the population of the most populous city.
Note: Do not use the max function.
def find_max_population(lst):
"""Finds the population of the place with the maximum population in a list of places.
Input: A list of city pairs. The first element in a place pair is the name
of the place, and the second element is the population
(List[Pair[str, int]]).
Output: The population of the place with the greatest population (int).
"""
# Write your base case here
# Write your recursive/other cases here
check(find_max_population([("Spanish Town", 147152),("Kingston", 1041203), ("Montego Bay", 110115), ("Portmore", 182153)]), 1041202)
2. Recursion and Counting¶
2.1 count_arrangements¶
Suppose there are $N$ students in JamCoders. How many different ways can the students sit in the computer lab assuming there are only $N$ places to sit?
Hint: Suppose there are $5$ students ($N = 5$). Then, in the first seat, there are $5$ students who can sit in that seat. In the second seat, there are $4$ remaining students who can sit in that seat. In the third, there are $3$ remaining possible students, and so on. So the total number of arrangements of students is $5 \times 4 \times 3 \times 2 \times 1 = 5! = 120$.
> Input: N = 5
> Output: 120
Seems like we have countless options to rearrange your seats! :)
def count_arrangements(N):
"""Computes the number of arrangements of students, given N students and N seats.
Input: N, the number of students and seats (int).
Output: The number of arrangements of students(int).
"""
# Write your base case here
# Write your recursive/other cases here
# Test cases.
check(count_arrangements(5), 120)
check(count_arrangements(20), 2432902008176640000)
check(count_arrangements(1), 1)
def print_pyramid_desc_asc(N):
"""Prints an descending-ascending pyramid with height N*2.
Input: N, half the height of the pyramid (int).
Output: Prints the pyramid. Returns None.
"""
# Write your base case here
# Write your recursive/other cases here
3.2 print_pyramid_2¶
Print the following pyramids for the corresponding heights.
height = 1:
#
#
height = 2:
#
# #
# #
#
height = 3:
#
# #
# # #
# # #
# #
#
and so on.
Test your result with different heights.
Hint: you might need to define a helper function that takes two arguments.
def print_pyramid_asc_desc(height):
"""Prints an ascending-descending pyramid with height N*2.
Input: N, half the height of the pyramid (int).
Output: Prints the pyramid. Returns None.
"""
# Write your base case here
# Write your recursive/other cases here
4 More Challenges¶
4.1 How many assignments?¶
Suppose there are $n$ students who are in JamCoders this year and the computer lab has $k$ computers. We have more computers than students, so $k \geq n$. In how many different ways can the $k$ computers be occupied by the students?
Hint: Suppose we had the same number of students as computers ($k$). As we saw earlier, there are $k!$ different ways to assign those $k$ students to those computers. Call these assignments "full" assignments.
Now, what if we only had $n$ students? Given any full assignment of $k$ students, we could replace $k - n$ students with blank slots. That would leave us with a "blank" assignment of $n$ students and $k - n$ blank slots.
For example, let $k = 5$ and $n = 3$. Here is a sample "full" assignment:
Computers: 1 2 3 4 5
Students: 5 2 3 1 4
# Student 5 is assigned to computer 1, student 2 is assigned to computer 2, and
so on.
And by removing $k - n = 2$ students (in this example, let's always choose students 5 and 4), we can produce an assignment with blanks:
Computers: 1 2 3 4 5
Students: 2 3 1
Notice that there are multiple "full" assignments that give us the same "blank" assignment. Indeed, when you remove students 5 and 4 from the following different full assignment, you arrive at the same "blank" assignment as above.
Computers: 1 2 3 4 5
Students: 4 2 3 1 5
# The same full assignment as above except with 5 and 4 swapped. But when 4 and
5 are removed, we arrive at the same blank assignment (try it!).
Recall again that there are $k!$ full assignments. For every blank assignment, how many corresponding full assignments are there? Can you express that number in terms of factorial ($!$) as well? How can you combine the number of full assignments with the number of full assignments that "map" to a blank assignment to find the number of blank assignments?
def num_comp_assigns(n, k):
"""Computes the number of possible assignments of n students to k computers.
Assume there are at least as many computers than students.
Inputs: n, the number of students (int).
k, the number of computers (int).
Output: The number of possible assignments (int).
"""
# Test cases.
check(num_comp_assigns(5, 3), 20)
check(num_comp_assigns(10, 10), 1)
check(num_comp_assigns(1, 5), 5)
check(num_comp_assigns(0, 100), 1)
4.2¶
Did your solution to 2.2 Part A use recursion? Why or why not?
ANSWER_4_2 = "Type your answer in this string."
check(ANSWER_4_2 == "Type your answer in this string.", False)
4.3¶
Now write a recursive function recur_num_comp_assigns that computes the same value but DOES NOT use the function factorial.
def recur_num_comp_assigns(n, k):
"""Computes the number of possible assignments of n students to k computers.
Do NOT call the factorial() function.
Assume there are at least as many computers than students.
Inputs: n, the number of students (int).
k, the number of computers (int).
Output: The number of possible assignments (int).
"""
check(recur_num_comp_assigns(5, 3), 10)
check(recur_num_comp_assigns(10, 7), 120)
check(recur_num_comp_assigns(10, 10), 1)
check(recur_num_comp_assigns(5, 0), 1)