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

3. Challenge Problems¶

3.1 `print_pyramid`¶

Print the following pyramids for the corresponding $N$ 's.

N = 1:
#
#

N = 2:
# #
# 
#
# #

N = 3:
# # #
# #
#
#
# # 
# # #

Hint: Notice that the N=2 pyramid is contained within the N=3 pyramid.

Test your result with different values of N.

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)

JamCoders

Lecture 8, Lab A: More Recursion¶

Warm-up¶

1. Recursion with Lists¶

1.1 sort_pairs¶

1.2 deep_add¶

1.3 replace_nat¶

1.4 find_max_population¶