Review - CS1302

CS1302 Introduction to Computer Programming

%reload_ext divewidgets

Topic 8¶

def concat_two_dicts(a, b):
    ### BEGIN SOLUTION
    return {**b, **a}
    ### END SOLUTION

# 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):
    ### BEGIN SOLUTION
    counts = {}
    for char in string:
        counts[char] = counts.get(char, 0) + 1
    return counts
    ### END SOLUTION

# 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):
    ### BEGIN SOLUTION
    def fib_sequence_inclusive(stop):
        Fn, Fn1 = 0, 1
        while Fn <= stop:
            yield Fn
            Fn, Fn1 = Fn1, Fn + Fn1

    non_fibs = set(container)
    non_fibs.difference_update(fib_sequence_inclusive(max(container)))
    return len(non_fibs)
    ### END SOLUTION

# 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 4 (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$ .

Hint

Use items method of dict to return the list of key values pairs, and
use a dictionary comprehension to create the desired dictionary by iterating through the list of items.

def calculate_total(salary_dict):
    ### BEGIN SOLUTION
    return {
        emp: record["salary"] * record["working_time"]
        for emp, record in salary_dict.items()
    }
    ### END SOLUTION

# 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 5 (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):
    ### BEGIN SOLUTION
    for k in (to_delete := [k for k in d if d[k] == 0]):
        del d[k]
    return len(to_delete) > 0
    ### END SOLUTION

# 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):
    ### BEGIN SOLUTION
    for myword in myset:
        if (
            len(myword) == len(word)
            and len([True for mychar, char in zip(myword, word) if mychar != char]) <= 1
        ):
            return True
    return False
    ### END SOLUTION

# 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):
    ### BEGIN SOLUTION
    return {k for k in d if d[k] == value}
    ### END SOLUTION

# 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):
    ### BEGIN SOLUTION
    return {'DIGITS': len([True for c in string if c.isdigit()]),
            'LETTERS': len([True for c in string if c.isalpha()])}
    ### END SOLUTION

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 9 (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.

Hint

Use the class method setdefault of dict to create a dictionary that maps different prices to different sets of dealers.
Compute the lowest price at the same time.
Alternatively, use comprehension to find lowest price and then create the desired set of dealers with the lowest price.

def dealers_with_lowest_price(apple_price):
    ### BEGIN SOLUTION
    lowest_price = min(pricing['price'] for pricing in apple_price)
    return set(pricing['dealer'] for pricing in apple_price
               if pricing['price'] == lowest_price)
    ### END SOLUTION

# 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",
}

Topic 7¶

def add_binary(*binaries):
    ### BEGIN SOLUTION
    if len(binaries)<1:
        return ''
    if len(binaries)<2:
        return binaries[0]
    k = len([1 for b in binaries if b[-1] == '1'])
    return add_binary(*[b[:-1] for b in binaries if len(b)>1], *((k//2)*'1')) + str(k%2)

def add_binary(*binaries):
    def d2b(d):
        return (d2b(d//2) if d>1 else '') + str(d%2)
    d = sum(int(b, base=2) for b in binaries)
    return d2b(d)
    ### END SOLUTION

# 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):
    ### BEGIN SOLUTION
    def is_even_digit(n):
        return not n or not n % 10 % 2 and is_even_digit(n // 10)

    return [n for n in range(lower_bound, upper_bound + 1) if is_even_digit(n)]
    ### END SOLUTION

# 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 12 (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.

Hint

For a list $[a_0, a_1, \dots]$ , let

c_k:=\max_{j\leq k} \sum_{i=j}^{k} a_i = \max\{a_k, c_{k-1}+a_{k}\},

(1)

namely the maximum non-empty tail sum of $[a_0,\dots,a_{k}]$ .

Then, the current best maximum subsequence sum of $[a_0,\dots,a_{k}]$ is

b_k := \max_{j\leq k} c_j.

(2)

See Kadane's algorithm.

def max_subsequence_sum(a):
    ### BEGIN SOLUTION
    b = c = -float("inf")
    for x in a:
        c = max(x, c + x)
        b = max(b, c)
    return b

    ## Alternative (less efficient) solution using list comprehension
    # def max_subsequence_sum(a):
    #     return max(sum(a[i:j]) for i in range(len(a)) for j in range(i+1,len(a)+1))

    ### END SOLUTION

# 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 13 (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.

Hint

For merge(left, right):

If left or right is empty, just return the non-empty one as a list.
Otherwise, take out one of the largest item from left and right and call merge again on the resulting list.
Return the sorted list from the recursive call appended with the largest item that was taken out in the last step.

def merge(left, right):
    ### BEGIN SOLUTION
    if left and right:
        if left[-1] > right[-1]:
            left, right = right, left
        return merge(left, right[:-1]) + [right[-1]]
    return list(left or right)
    ### END SOLUTION

def mergesort(seq):
    ### BEGIN SOLUTION
    if len(seq) <= 1:
        return list(seq)
    i = len(seq) // 2
    return merge(mergesort(seq[:i]), mergesort(seq[i:]))
    ### END SOLUTION

# 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]

Topic 6¶

import functools


def input_types(*types):
    def decorator(f):
        @functools.wraps(f)
        def wrapper(*args, **kwargs):
            ### BEGIN SOLUTION
            for a, t in zip(args, types):
                if not isinstance(a, t):
                    raise TypeError()
            return f(*args, **kwargs)
            ### END SOLUTION

        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):
    ### BEGIN SOLUTION
    a, g = x, y
    while True:
        yield a, g
        a, g = (a + g) / 2, (a * g) ** 0.5
    ### END SOLUTION

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

Challenge¶

The following function computes the integer square root $\lfloor \sqrt{n}\rfloor$ of its non-negative integer argument $n$ using the idea of bisection as suggested by one student in class.

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:

if input('Execute? [y/N]').lower() == 'y':
    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
    ### BEGIN SOLUTION
        if n < c ** 2:
            b = c
        else:
            a = c
    return a
    ### END SOLUTION

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:
        ### BEGIN SOLUTION
        if k == 0:
            output.append(set())
        else:
            output.extend(combination(n - 1, k))
            output.extend({*s, n - 1} for s in combination(n - 1, k - 1))
        ### END SOLUTION
    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])

Solution to Exercise 18

Yes. combination(4, 2) calls combination(3, 1) and combination(3, 2), both of which calls combination(2, 1) that returns [{0}, {1}].

Exercise 19 (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.
    """
    ### BEGIN SOLUTION
    return lambda n: (
        i
        for r in range(k)
        for c in range(0, n, 2 * (k - 1))
        for i in ((c+r, c+2 * (k - 1) - r) if 0 < r < k - 1 else (c+r,))
        if 0 <= i < n
    )
    ### END SOLUTION

# 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 20 (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)]
    ### BEGIN SOLUTION
    y = [*range(k), *range(k - 2, 0, -1)]
    for i in range(n):
        arr[y[i % len(y)]][i] = plaintext[i]
    ### END SOLUTION
    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