Exercises on Selected Topics

from __init__ import install_dependencies

await install_dependencies()

Functional Programming¶

import functools


def input_types(*types):
    def decorator(f):
        @functools.wraps(f)
        def wrapper(*args, **kwargs):
            # YOUR CODE HERE
            raise NotImplementedError

        return wrapper

    return decorator

# tests
@input_types(int, int)
def _sum(x, y):
    return x + y


assert _sum(1, 1) == 2

try:
    print(_sum(1.0, 1))
except TypeError:
    pass

def arithmetic_geometric_mean_sequence(x, y):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
agm = arithmetic_geometric_mean_sequence(6, 24)
assert [next(agm) for i in range(2)] == [(6, 24), (15.0, 12.0)]

agm = arithmetic_geometric_mean_sequence(100, 400)
for sol, ans in zip(
    [next(agm) for i in range(5)],
    [
        (100, 400),
        (250.0, 200.0),
        (225.0, 223.60679774997897),
        (224.30339887498948, 224.30231718318308),
        (224.30285802908628, 224.30285802843423),
    ],
):
    for a, b in zip(sol, ans):
        assert round(a, 5) == round(b, 5)

Sequence Types¶

def add_binary(*binaries):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
assert add_binary("0", "0") == "0"
assert add_binary("11", "11") == "110"
assert add_binary("101", "101") == "1010"

assert add_binary("1111", "10") == "10001"
assert add_binary("111110000011", "110000111") == "1000100001010"

def even_digit_numbers(lower_bound, upper_bound):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
assert even_digit_numbers(1999, 2001) == [2000]
assert even_digit_numbers(2805, 2821) == [2806, 2808, 2820]

assert even_digit_numbers(8801, 8833) == [
    8802,
    8804,
    8806,
    8808,
    8820,
    8822,
    8824,
    8826,
    8828,
]
assert even_digit_numbers(3662, 4001) == [4000]

Exercise 5 (Maximum subsequence sum)

Define a function max_subsequence_sum that

accepts as an argument a sequence of numbers, and
returns the maximum sum over non-empty contiguous subsequences.

E.g., when [-6, -4, 4, 1, -2, 2] is given as the argument, the function returns 5 because the nonempty subsequence [4, 1] has the maximum sum 5.

def max_subsequence_sum(a):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
assert max_subsequence_sum([-1]) == -1
assert max_subsequence_sum([-6, -4, 4, 1, -2, 2]) == 5
assert max_subsequence_sum([2.5, 1.4, -2.5, 1.4, 1.5, 1.6]) == 5.9

seq = [-24.81, 25.74, 37.29, -8.77, 0.78, -15.33, 30.21, 34.94, -40.64, -20.06]
assert round(max_subsequence_sum(seq), 2) == 104.86

# test of efficiency
assert max_subsequence_sum([*range(1234567)]) == 762077221461

Exercise 6 (Mergesort)

For this question, do not use the sort method or sorted function.

Define a function called merge that

takes two sequences sorted in ascending orders, and
returns a sorted list of items from the two sequences.

Then, define a function called mergesort that

takes a sequence, and
return a list of items from the sequence sorted in ascending order.

The list should be constructed by

recursive calls to mergesort the first and second halves of the sequence individually, and
merge the sorted halves.

def merge(left, right):
    # YOUR CODE HERE
    raise NotImplementedError

def mergesort(seq):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
assert merge([1, 3], [2, 4]) == [1, 2, 3, 4]
assert mergesort([3, 2, 1]) == [1, 2, 3]

assert mergesort([3, 5, 2, 4, 2, 1]) == [1, 2, 2, 3, 4, 5]

The following function computes the integer square root $\lfloor \sqrt{n}\rfloor$ of its non-negative integer argument $n$ using the idea of bisection:

def isqrt(n):
    def _(n, a, b):
        if a ** 2 <= n < b ** 2:
            if a + 1 == b:
                return a
            c = (a + b) // 2
            return _(n, a, c) or _(n, c, b)

    return _(n, 0, n + 1)


assert isqrt(10 ** 2) == 10

For large $n$ , the above recursion can fail with RecursionError: maximum recursion depth exceed in comparison:

assert isqrt(10**100**2) == 10**5000

%%optlite -r -l
def isqrt(n):
    a, b = 0, n + 1
    while a + 1 < b:
        c = (a + b) // 2
    # YOUR CODE HERE
    raise NotImplementedError

assert isqrt(2**2) == 2

# tests
assert isqrt(10**100**2) == 10**5000

%%optlite -r -l
import functools


@functools.lru_cache
def combination(n, k):
    output = []
    if 0 <= k <= n:
        # YOUR CODE HERE
        raise NotImplementedError
    return output


combination(3, 2)

# tests
n = 3
got = [combination(n, k) for k in range(-1, n+2)]
expected = [[], [set()], [{0}, {1}, {2}], [{0, 1}, {0, 2}, {1, 2}], [{0, 1, 2}], []]
for i in range(len(expected)):
    assert set(frozenset(s) for s in got[i]) == set(frozenset(s) for s in expected[i])

YOUR ANSWER HERE

Exercise 10 (Rail Fence)

Complete the function rf_key so that encrypt and decrypt implement the Rail Fence transposition cipher. In particular, the plaintext

WE ARE DISCOVERED FLEE AT ONCE

with spaces removed is arranged in k=3 rails as

W...E...C...R...L...T...E
.E.R.D.S.O.E.E.F.E.A.O.C.
..A...I...V...D...E...N..

so the ciphertext is read from the above line-by-line (ignoring the dots) as

WECRLTE ERDSOEEFEAOC AIVDEN

with spaces removed. The sequence of indices that transpose the plaintext to ciphertext is given by rf_key(3)(25) as

[0,      4,      8,      12,     16,     20,     24, 
   1,  3,  5,  7,  9,  11, 13, 15, 17, 19, 21, 23, 
     2,      6,      10,     14,     18,     22     ]

def encrypt(plaintext, key):
    """
    Encryption function for a general transposition cipher.

    Parameters
    ----------
    plaintext: str
        Text to be encrypted.
    key: function
        A function that takes the length of the plaintext as an argument and
        returns a sequence of indices that transpose the plaintext into the
        ciphertext.

    Returns
    -------
    str: The ciphertext.
    """
    return "".join(plaintext[i] for i in key(len(plaintext)))


def decrypt(ciphertext, key):
    """
    Decryption function for a general transposition cipher.

    Parameters
    ----------
    ciphertext: str
        Text to be descrypted.
    key: function
        A function that takes the length of the plaintext as an argument and
        returns a sequence of indices that transpose the plaintext into the
        ciphertext.

    Returns
    -------
    str: The plaintext.
    """
    return "".join(
        ciphertext[i]
        for (i, j) in sorted(enumerate(key(len(ciphertext))), key=lambda x: x[1])
    )


def rf_key(k):
    """
    Generation of the sequence of indices for Rail Fence transposition cipher.

    Parameters
    ----------
    k: positive int
        Number of rails.

    Returns
    -------
    Function: The key function that takes the length of the plaintext as an
        argument and returns a sequence of indices that transpose the plaintext
        into the ciphertext.
    """
    # YOUR CODE HERE
    raise NotImplementedError

# tests
plaintext = "WE ARE DISCOVERED FLEE AT ONCE".replace(" ", "")
key = rf_key(3)
ciphertext = encrypt(plaintext, key)
assert ciphertext == 'WECRLTEERDSOEEFEAOCAIVDEN'
assert plaintext == decrypt(ciphertext, key)

Exercise 11 (Rail Fence demo)

Complete the function rf_demo that returns the string that demonstrates the Rail Fence cipher. For the previous example, it should return the string for

W...E...C...R...L...T...E
.E.R.D.S.O.E.E.F.E.A.O.C.
..A...I...V...D...E...N..

def rf_demo(plaintext, k):
    n = len(plaintext)
    arr = [["."] * n for i in range(k)]
    # YOUR CODE HERE
    raise NotImplementedError
    return "\n".join("".join(_) for _ in arr)

# tests
expected = 'W...E...C...R...L...T...E\n.E.R.D.S.O.E.E.F.E.A.O.C.\n..A...I...V...D...E...N..'
got = rf_demo(plaintext,3)
print(got)
assert got == expected

Associative Containers¶

def concat_two_dicts(a, b):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
a = {"x": 10, "z": 30}
b = {"y": 20, "z": 40}
a_copy = a.copy()
b_copy = b.copy()
assert concat_two_dicts(a, b) == {"x": 10, "z": 30, "y": 20}
assert concat_two_dicts(b, a) == {"x": 10, "z": 40, "y": 20}
assert a == a_copy and b == b_copy

a = {"x": 10, "z": 30}
b = {"y": 20}
a_copy = a.copy()
b_copy = b.copy()
assert concat_two_dicts(a, b) == {"x": 10, "z": 30, "y": 20}
assert concat_two_dicts(b, a) == {"x": 10, "z": 30, "y": 20}
assert a == a_copy and b == b_copy

def count_characters(string):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
assert count_characters("abcbabc") == {"a": 2, "b": 3, "c": 2}
assert count_characters("aababcccabc") == {"a": 4, "b": 3, "c": 4}

assert count_characters("abcdefgabc") == {
    "a": 2,
    "b": 2,
    "c": 2,
    "d": 1,
    "e": 1,
    "f": 1,
    "g": 1,
}
assert count_characters("ab43cb324abc") == {
    "2": 1,
    "3": 2,
    "4": 2,
    "a": 2,
    "b": 3,
    "c": 2,
}

def count_non_fibs(container):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
assert count_non_fibs([0, 1, 2, 3, 5, 8]) == 0
assert count_non_fibs({13, 144, 99, 76, 1000}) == 3

assert count_non_fibs({5, 8, 13, 21, 34, 100}) == 1
assert count_non_fibs({0.1, 0}) == 1

Exercise 15 (Calculate total salaries)

Suppose salary_dict contains information about the name, salary, and working time about employees in a company. An example of salary_dict is as follows:

salary_dict = {
     'emp1': {'name': 'John', 'salary': 15000, 'working_time': 20},
     'emp2': {'name': 'Tom', 'salary': 16000, 'working_time': 13},
     'emp3': {'name': 'Jack', 'salary': 15500, 'working_time': 15},
}

Define a function calculate_total that accepts salary_dict as an argument, and returns a dict that uses the same keys in salary_dict but the total salaries as their values. The total salary of an employee is obtained by multiplying his/her salary and his/her working_time. E.g., for the salary_dict example above, calculate_total(salary_dict) should return

{'emp1': 300000, 'emp2': 208000, 'emp3': 232500}.

where the total salary of emp1 is $15000 \times 20 = 300000$ .

def calculate_total(salary_dict):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
salary_dict = {
    "emp1": {"name": "John", "salary": 15000, "working_time": 20},
    "emp2": {"name": "Tom", "salary": 16000, "working_time": 13},
    "emp3": {"name": "Jack", "salary": 15500, "working_time": 15},
}
assert calculate_total(salary_dict) == {"emp1": 300000, "emp2": 208000, "emp3": 232500}

salary_dict = {
    "emp1": {"name": "John", "salary": 15000, "working_time": 20},
    "emp2": {"name": "Tom", "salary": 16000, "working_time": 13},
    "emp3": {"name": "Jack", "salary": 15500, "working_time": 15},
    "emp4": {"name": "Bob", "salary": 20000, "working_time": 10},
}
assert calculate_total(salary_dict) == {
    "emp1": 300000,
    "emp2": 208000,
    "emp3": 232500,
    "emp4": 200000,
}

Exercise 16 (Delete items with value 0 in dictionary)

Define a function zeros_removed that

takes a dictionary as an argument,
mutates the dictionary to remove all the keys associated with values equal to 0,
and return True if at least one key is removed else False.

Hint

The main issue is that, for any dicionary d,

    for k in d: 
        if d[k] == 0: del d[k]

raises the RuntimeError: dictionary changed size during iteration.

One solution is to duplicate the list of keys, but this is memory inefficient especially when the list of keys is large.
Another solution is to record the list of keys to delete before the actual deletion. This is memory efficient if the list of keys to delete is small.

def zeros_removed(d):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
d = {"a": 0, "b": 1, "c": 0, "d": 2}
assert zeros_removed(d) == True
assert zeros_removed(d) == False
assert d == {"b": 1, "d": 2}

d = {"a": 0, "b": 1, "c": 0, "d": 2, "e": 0, "f": "0"}
assert zeros_removed(d) == True
assert zeros_removed(d) == False
assert d == {"b": 1, "d": 2, "f": "0"}

def search_fuzzy(myset, word):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
assert search_fuzzy({"cat", "dog"}, "car") == True
assert search_fuzzy({"cat", "dog"}, "fox") == False

myset = {"cat", "dog", "dolphin", "rabbit", "monkey", "tiger"}
assert search_fuzzy(myset, "lion") == False
assert search_fuzzy(myset, "cat") == True
assert search_fuzzy(myset, "cat ") == False
assert search_fuzzy(myset, "fox") == False
assert search_fuzzy(myset, "ccc") == False

def get_keys_by_value(d, value):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
d = {
    "Tom": "99",
    "John": "88",
    "Lucy": "100",
    "Lily": "90",
    "Jason": "89",
    "Jack": "100",
}
assert get_keys_by_value(d, "99") == {"Tom"}

d = {
    "Tom": "99",
    "John": "88",
    "Lucy": "100",
    "Lily": "90",
    "Jason": "89",
    "Jack": "100",
}
assert get_keys_by_value(d, "100") == {"Jack", "Lucy"}
d = {
    "Tom": "99",
    "John": "88",
    "Lucy": "100",
    "Lily": "90",
    "Jason": "89",
    "Jack": "100",
}
assert get_keys_by_value(d, "0") == set()

def count_letters_and_digits(string):
    # YOUR CODE HERE
    raise NotImplementedError

assert count_letters_and_digits("hello world! 2020") == {"DIGITS": 4, "LETTERS": 10}
assert count_letters_and_digits("I love CS1302") == {"DIGITS": 4, "LETTERS": 7}

assert count_letters_and_digits("Hi CityU see you in 2021") == {
    "DIGITS": 4,
    "LETTERS": 15,
}
assert count_letters_and_digits(
    "When a dog runs at you, whistle for him. (Philosopher Henry David Thoreau, 1817-1862)"
) == {"DIGITS": 8, "LETTERS": 58}

Exercise 20 (Dealers with lowest price)

Suppose apple_price is a list in which each element is a dict recording the dealer and the corresponding price, e.g.,

apple_price = [{'dealer': 'dealer_A', 'price': 6799},
 {'dealer': 'dealer_B', 'price': 6749},
 {'dealer': 'dealer_C', 'price': 6798},
 {'dealer': 'dealer_D', 'price': 6749}]

Define a function dealers_with_lowest_price that takes apple_price as an argument, and returns the set of dealers providing the lowest price.

def dealers_with_lowest_price(apple_price):
    # YOUR CODE HERE
    raise NotImplementedError

# tests
apple_price = [
    {"dealer": "dealer_A", "price": 6799},
    {"dealer": "dealer_B", "price": 6749},
    {"dealer": "dealer_C", "price": 6798},
    {"dealer": "dealer_D", "price": 6749},
]
assert dealers_with_lowest_price(apple_price) == {"dealer_B", "dealer_D"}

apple_price = [
    {"dealer": "dealer_A", "price": 6799},
    {"dealer": "dealer_B", "price": 6799},
    {"dealer": "dealer_C", "price": 6799},
    {"dealer": "dealer_D", "price": 6799},
]
assert dealers_with_lowest_price(apple_price) == {
    "dealer_A",
    "dealer_B",
    "dealer_C",
    "dealer_D",
}