Contents

Review (optional)

Topic 8

Exercise (Concatenate two dictionaries with precedence)

Define a function concat_two_dicts that accepts two arguments of type dict such that concat_two_dicts(a, b) will return

  • a new dictionary containing all the items in a, and

  • the items in b that have different keys than those in a.

The input dictionaries should not be mutated.

Hint

  • {**dict1,**dict2} creates a new dictionary by unpacking the dictionaries dict1 and dict2.

  • By default, dict2 overwrites dict1 if they have identical keys.

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

Exercise (Count characters)

Define a function count_characters which

  • accepts a string as an argument, and

  • returns a dictionary that stores counts of each character appearing in the string.

Hint

  • Create an empty dictionary counts.

  • Use a for loop to iterate over each character of string to count their numbers of occurrences.

  • The get method of dict can initialize the count of a new character before incrementing it.

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

Exercise (Count non-Fibonacci numbers)

Define a function count_non_fibs that

  • accepts a container as an argument, and

  • returns the number of items in the container that are not fibonacci numbers.

Hint

  • Create a set of Fibonacci numbers up to the maximum of the items in the container.

  • Use difference_update method of set to create a set of items in the container but not in the set of Fibonacci numbers.

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 (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 (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"}

Exercise (Fuzzy search a set) Define a function search_fuzzy that accepts two arguments myset and word such that

  • myset is a set of strs;

  • word is a str; and

  • search_fuzzy(myset, word) returns True if word is in myset by changing at most one character in word, and returns False otherwise.

Hint

  • Iterate over each word in myset.

  • Check whether the length of the word is the same as that of the word in the arguments.

  • If the above check passes, use a list comprehension to check if the words differ by at most one character.

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

Exercise (Get keys by value)

Define a function get_keys_by_value that accepts two arguments d and value where d is a dictionary, and returns a set containing all the keys in d that have value as its value. If no key has the query value value, then return an empty set.

Hint

Use set comprehension to create the set of keys whose associated values is value.

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

Exercise (Count letters and digits)

Define a function count_letters_and_digits which

  • take a string as an argument,

  • returns a dictionary that stores the number of letters and digits in the string using the keys ‘LETTERS’ and ‘DIGITS’ respectively.

Hint

Use the class method fromkeys of dict to initial the dictionary of counts.

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

Exercise (Binary addition)

Define a function add_binary that

  • accepts two arguments of type str which represent two non-negative binary numbers, and

  • returns the binary number in str equal to the sum of the two given binary numbers.

Hint

  • Use comprehension to convert the binary numbers to decimal numbers.

  • Use comprehension to convert the sum of the decimal numbers to a binary number.

  • Alternatively, perform bitwise addition using a recursion or iteration.

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"

Exercise (Even-digit numbers)

Define a function even_digit_numbers, which finds all numbers between lower_bound and upper_bound such that each digit of the number is an even number. Return the numbers as a list.

Hint

  • Use list comprehension to generate numbers between the bounds, and

  • use recursion to check if a number contains only even digits.

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 (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}\}, \]

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. \]

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

Exercise (Enforce input types)

Define a function input_types that takes a variable number of arguments stored in types and returns a decorator that ensures the argument at position i of a function has type types[i]. More precisely, the decorator calls raise TypeError() if an argument at any position i does not have type[i].

Hint

Complete the definition of wrapper:

  • Use a for loop and the zip function to iterate through items of args and types.

  • Check whether an item in args is of the corresponding type in types. Raise TypeError if not.

  • Return f evaluated at the same arguments passed to wrapper.

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

Exercise (Arithmetic geometric mean)

Define a function arithmetic_geometric_mean_sequence which

  • takes two floating point numbers x and y and

  • returns a generator that generates the tuple \((a_n, g_n)\) where

\[\begin{split} \begin{aligned} a_0 &= x, g_0 = y \\ a_n &= \frac{a_{n-1} + g_{n-1}}2 \quad \text{for }n>0\\ g_n &= \sqrt{a_{n-1} g_{n-1}} \end{aligned} \end{split}\]

Hint

Use the yield expression to return each tuple of \((a_n,g_n)\) efficiently without redundant computations.

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

Exercise (Integer square root)

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, e.g., with

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

Rewrite the code to use iteration (not recursion) to avoid the above error.

Hint

Complete the following code so that the value of c is assigned to either b or c depending on whether n < c**2.

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

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

Exercise

For integers n and k, complete the following function such that combination(n, k) returns a list of all k-subsets (k-combinations) of items in range(n).

Hint

A \(k\)-subset of items from a non-empty sequence a can be obtained either

  • as a \(k\)-subset of items from a[:-1], or

  • by adding a[-1] to a \(k-1\)-subset of items from a[:-1].

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

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

Exercise

In the above recursion, is caching by lru_cache useful in avoiding duplicate recursive calls with same arguments? Give an example of how the redundant computer is avoided.

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

Exercise

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

Complete the function rf_demo that returns the string that demonstrate 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

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