<jupyter_start><jupyter_text>Warming Up> Easy and not so easy exercises<jupyter_code># uncomment this to install nbdev
# !pip install nbdev
    
from timeit import timeit
from fastcore.test import test_eq
from typing import Any, Callable, List, NewType, Tuple<jupyter_output><empty_output><jupyter_text>The utility function `run` runs the testees given by `fs` against `test`, and that `n` times.It is called once for each exercise and tests all alternative implementations.It should silently go through, returning only the execution times for each testee.The number `n` is generally chosen such that waiting times are around one second or below.We use fastai's test library.<jupyter_code>def run(test, n, *fs):
    """
    :param test: a testdriver
    :n: number of repetitions
    :fs: the testees 
    :return: None
    """
    for f in fs:
        print(f"{f.__qualname__:<12} | {timeit(lambda: test(f), number=n):.4f}")<jupyter_output><empty_output><jupyter_text>Two Very Short Functions Using Logarithms Problem 01: Write a function `power_of2(n: int) -> bool` which returns true iff n is a power of 2.The following test defines what `power_of2`is supposed to do.<jupyter_code>def test_01(f: Callable[[int], bool]):
    test_eq(f(0), True)
    test_eq(f(1), True)
    test_eq(f(7), False)
    test_eq(f(8), True)
    test_eq(f(2**30), True)
    test_eq(f(2**30 + 1), False)<jupyter_output><empty_output><jupyter_text>Idea: A power of 2, say 8, is a 1 followed by 0s: 0b1000. Subtracting 1 changes the leading 1 to 0 and the 0s to 1: 8 - 1 = 7 = 0b111.So, a bitwise AND of n and n - 1 should do. No log, no exp.<jupyter_code>#collapse
def power_of2(n: int) -> bool:
    """
    :param n: an integer > = 1
    :return: true if n is a power of two
    """
    return not n & (n - 1)
run(test_01, 1000,  power_of2)<jupyter_output>power_of2    | 0.0771<jupyter_text>Problem 02: Write a function `log2(n: int) -> int` which returns the number of binary digits of n minus 1.<jupyter_code>def test_02(f: Callable[[int], int]) -> None:
    test_eq(f(1), 0)
    test_eq(f(2), 1)
    test_eq(f(7), 2)
    test_eq(f(8), 3)
    test_eq(f(2**30), 30)<jupyter_output><empty_output><jupyter_text>Idea: Shift `n` bitwise right while `n > 0`<jupyter_code>#collapse
def log2(n: int) -> int:
    """
    :param n: an integer >= 0
    :return: (number of binary digits of n) - 1
    """
    if n < 1:
        raise ValueError
    result = -1
    while n > 0:
        n >>= 1
        result += 1
    return result<jupyter_output><empty_output><jupyter_text>Python's math.log2 is slightly faster.<jupyter_code>#collapse
import math
def mlog2(n: int) -> int:
    """
    :param n: an integer >= 0
    :return: (number of binary digits of n) - 1
    """
    return int(math.log2(n))
run(test_02, 1000,  log2, mlog2)<jupyter_output>log2         | 0.0625
mlog2        | 0.0684<jupyter_text>Greatest Common Divisor (GCD) Problem 03: Write a function `gcd(a: int, b: int) -> int` which returns the greatest common divisor of a and b.<jupyter_code>def test_03(f: Callable[[int, int], int]) -> None:
    test_eq(f(0, 0), 0)
    test_eq(f(7, 0), 7)
    test_eq(f(-7, 0), -7)
    test_eq(f(0, 7), 7)
    test_eq(f(0, -7), -7)
    test_eq(f(20, 14), 2)
    a = 2 * 3 * 5 * 7 * 11 * 13 * 17
    b =                 11 * 13 * 17 * 19 * 23 * 29 * 31
    test_eq(f(a, b), 11 * 13 * 17)<jupyter_output><empty_output><jupyter_text>We apply the Euclidean algorithm: compute the remainder c of a and b, replace a with b and b with c.<jupyter_code>#collapse
def gcd(a: int, b: int) -> int:
    """
    :param a: integer
    :param b: integer
    :return: greatest common divisor of a and b
    """
    while b != 0:
        a, b = b, a % b
    return a<jupyter_output><empty_output><jupyter_text>The recursive solution is more elegant and slightly faster.<jupyter_code>#collapse
def gcd1(a: int, b: int) -> int:
    """
    :param a: integer
    :param b: integer
    :return: greatest common divisor of a and b
    """
    return a if b == 0 else gcd1(b, a % b)
run(test_03, 1000, gcd, gcd1)<jupyter_output>gcd          | 0.0878
gcd1         | 0.0880<jupyter_text>Intersection of Intervals We consider half-open intervals such as u = [a, b) given as a tuple `(a, b)`.Problem 04: Write a function `intersection(u: (int, int), v: (int, int)) -> (int, int)`which returns the intersection `u` and `v`. Hint: This is a one-liner, no ifs, no elses.Main question: How do you manage the empty interval?Our choice: An interval is empty iff lower bound $\geq$ upper bound, so (0, -1), (0, 0), (3, 2) all represent the same and unique empty interval. This makes our program so simple.<jupyter_code># we introduce a new type
Interval = NewType('Interval', Tuple[int, int])

def test_04(f: Callable[[Interval, Interval], Interval]) -> None:
    test_eq(f((0, 8), (4, 10)), (4, 8))
    test_eq(f((0, 8), (8, 10)), (8, 8))    # empty interval
    test_eq(f((0, 8), (9, 10)), (9, 8))    # empty interval
    test_eq(f((0, 10), (4, 8)), (4, 8))
#collapse
def intersection(u: (int, int), v: (int, int)) -> (int, int):
    """
    :param u: half open interval (u0, u1)
    :param v: half open interval (v0, v1)
    :return: intersection of u and v
    """
    return max(u[0], v[0]), min(u[1], v[1])
run(test_04, 1000,  intersection)<jupyter_output>intersection | 0.1444<jupyter_text>Faculty Problem 05: Write a function `faculty(n: int) -> int` which returns n!.<jupyter_code>def test_05(f: Callable[[int], int]) -> None:
    test_eq(f(0), 1)
    test_eq(f(1), 1)
    test_eq(f(2), 2)
    test_eq(f(8), 40320)<jupyter_output><empty_output><jupyter_text>Idea: Multiply all integers from 2 through n<jupyter_code>#collapse
def faculty(n: int) -> int:
    """
    :param n: integer
    :return:  nth-faculty
    """
    if n < 0:
        raise ValueError
    else:
        result = 1
        for i in range(1, n + 1):
            result *= i
        return result<jupyter_output><empty_output><jupyter_text>The recursive solution is more elegant and slightly faster. The call stack is $O(n)$, but as $n!$ can only be computed for small $n$, this is no problem.<jupyter_code>#collapse
def faculty1(n: int) -> int:
    """
    :param n: integer
    :return:  nth-faculty
    """
    if n < 0:
        raise ValueError
    elif n <= 1:
        return 1
    else:
        return n * faculty1(n - 1)
run(test_05, 1000, faculty, faculty1)<jupyter_output>faculty      | 0.0438
faculty1     | 0.0466<jupyter_text>Fibonacci Problem: We write a function `fibo(n: int) -> int` which returns the n-th fibonacci number<jupyter_code>def test_05(f: Callable[[int], int]) -> None:
    test_eq(f(0), 0)
    test_eq(f(1), 1)
    test_eq(f(2), 1)
    test_eq(f(20), 6765)
#collapse
def fibo(n: int) -> int:
    """
    :param n: integer >= 0
    :return: n-th Fibonacci number
    """
    if n < 0:
        raise ValueError
    elif n == 0:
        return 0
    else:
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b<jupyter_output><empty_output><jupyter_text>The recursive solution represents exactly the definition of the fibonacci series.This is clear and concise but inthat case extremely slow.<jupyter_code>#collapse
def fibo1(n: int) -> int:
    """
    :param n: integer >= 0
    :return: n-th Fibonacci number
    """
    # recursive programming, cool but slow
    if n < 0:
        raise ValueError
    elif n <= 1:
        return n
    else:
        return fibo1(n - 2) + fibo1(n - 1)
run(test_05, 1000, fibo, fibo1)<jupyter_output>fibo         | 0.0414
fibo1        | 2.8304<jupyter_text>Reversing Lists in And out of Place Problem 06: Write a function `reverse_(xs: list) -> None` which reverses the list `xs` in place.We compare our solution to the builtin function `list.reverse`.Please not the difference between reversing in place (the list itself is reversed) and reversing not in place(a new list is produced).<jupyter_code>from random import randrange

def test_06(r: Callable[[List[Any]], None]) -> None:
    xs, ys = [], []
    r(xs)
    test_eq(xs, ys)

    xs, ys = [1], [1]
    r(xs)
    test_eq(xs, ys)

    xs, ys = [1, 2], [2, 1]
    r(xs)
    test_eq(xs, ys)

    xs, ys = [1, 2, 3, 4], [4, 3, 2, 1]
    r(xs)
    test_eq(xs, ys)

    xs = [randrange(100) for _ in range(1000)]
    ys = xs.copy()
    r(xs)
    r(xs)
    test_eq(xs, ys)<jupyter_output><empty_output><jupyter_text>A comment on the last testcase: `xs` is a list of a thousand random integers between 0 and 99.This testcase documents the fact that reversing a list twice restores the original list: reverse equals its inverse. Note that `ys` is a copy of `xs`, rather than an alias.Idea: Swap the first and the last element, then the second and the last but one and so on. Stop in the middle.<jupyter_code>#collapse
def reverse_(xs: list) -> None:
    """
    :param xs: a list
    :return: None
    Side effect: This function reverses the order of xs
    """
    m = len(xs) // 2
    for i in range(m):
        xs[i], xs[-1 - i] = xs[-1 - i], xs[i]
run(test_06, 10, reverse_, list.reverse)<jupyter_output>reverse_     | 0.0982
list.reverse | 0.0988<jupyter_text>Problem 07: Write a function `reverse(xs: List) -> List` which returns the list `xs`in reversed order.<jupyter_code>def test_07(r: Callable[[List[Any]], List[Any]]) -> None:
    test_eq(r([]), [])
    test_eq(r([1]), [1])
    test_eq(r([1, 2]), [2, 1])
    test_eq(r([1, 2, 3, 4]), [4, 3, 2, 1])
    
    xs = [randrange(100) for _ in range(1000)]
    ys = xs.copy()
    test_eq(r(r(xs)), ys)<jupyter_output><empty_output><jupyter_text>Idea as above: Swap the first and the last element,then call `reverse` recursively on the not yet swapped subset from the second to the last but first element.<jupyter_code>#collapse
def reverse(xs: list) -> list:
    """
    :param xs: a list
    :return: a new list containing xs in reversed order
    same as reverse0, recursive solution
    This produces O(n) new lists!
    """
    return xs.copy() if len(xs) <= 1 else [xs[-1]] + reverse(xs[1: -1]) + [xs[0]]
run(test_07, 10, reverse)<jupyter_output>reverse      | 0.1523<jupyter_text>Palindromes A palindrom is a string which can be read in both directions such as "xx" or "Mad Zeus, no live devil, lived evil on Suez dam". Punctuation marks are ignored, lower and upper case letters are considered equal. So, we need a function `normstring(s: str) -> str` which removes all non-letter characters and converts the string to lowercase.<jupyter_code>import string

#collapse
def normstring(s: str) -> list:
    """
    :param s: a string
    :return: keeps ascii letters only and converts s to lower case
    """
    return [str.lower(c) for c in s if c in string.ascii_letters]<jupyter_output><empty_output><jupyter_text>Problem 08: Write a function `palindrome1(s: str) -> bool` which returns true iff the string s is a palindrome.<jupyter_code>def test_08(p: Callable[[str], bool]) -> None:
    test_eq(p(""), True)
    test_eq(p("x"), True)
    test_eq(p("xx"), True)
    test_eq(p("xy"), False)
    test_eq(p("Reittier"), True)
    test_eq(p("Reliefpfeiler"), True)
    test_eq(p("Risotto, Sir?"), True)
    test_eq(p("Madam, I'm Adam"), True)
    test_eq(p("Liese, tu Gutes, eil!"), True)
    test_eq(p("Grub Nero nie in Orenburg?"), True)
    test_eq(p("O Genie, der Herr ehre dein Ego!"), True)
    test_eq(p("Lewd I did live, & evil did I dwel?"), True)
    test_eq(p("Eine treue Familie bei Lima feuerte nie"), True)
    test_eq(p("Mad Zeus, no live devil, lived evil on Suez dam"), True)
    test_eq(p("Straw? No, too stupid a fad. I put soot on warts."), True)<jupyter_output><empty_output><jupyter_text>The non-recursive solution resembles the reverse function:Normalize the input first. Then compare the first and the last letter.If they coincide proceed to the next pair, if not return False.<jupyter_code>#collapse
def palindrome(xs: str) -> bool:
    """
    :param xs: string
    :return: true if xs is a palindrome
    """
    ys = normstring(xs)
    m = len(ys) // 2
    for i in range(m):
        if ys[i] != ys[-1 - i]:
            return False
    return True<jupyter_output><empty_output><jupyter_text>The recursive solution needs a local helper function if `normstring` is to be called only once.<jupyter_code>#collapse
def palindrome1(xs: str) -> bool:
    """
    :param xs: string
    :return: true if xs is a palindrome
    """
    def pal(ys):
        return True if len(ys) <= 1 else ys[0] == ys[-1] and pal(ys[1:-1])

    return pal(normstring(xs))<jupyter_output><empty_output><jupyter_text>The shortest and fastest solution uses the builtin method `list.reverse`<jupyter_code>#collapse
def palindrome2(xs: str) -> bool:
    """
    :param xs: string
    :return: true if xs is a palindrome
    """
    ys = list(normstring(xs))
    zs = list(ys)
    zs.reverse()
    return ys == zs
run(test_08, 1000, palindrome, palindrome1, palindrome2)<jupyter_output>palindrome   | 0.2305
palindrome1  | 0.2392
palindrome2  | 0.2010<jupyter_text>Roman Numbers Problem 09: Write a function `romans() -> List[str]`which returns the list of all roman numbers from 1 to 4999, the element at zero being " ".<jupyter_code>def test_09(r: Callable[[], List[str]]) -> None:
    rs = r()
    test_eq(len(rs), 5000)
    test_eq(rs[0], '')
    test_eq(rs[1], 'I')
    test_eq(rs[9], 'IX')
    test_eq(rs[4999], 'MMMMCMXCIX' )<jupyter_output><empty_output><jupyter_text>Idea: We keep four lists of Roman digits: the ones from 'I' to 'IX', the tens from 'X' to 'XC',and the hundreds from 'C' to 'CM' and the thousands from 'M' to 'MMMM'.The largest Roman number is 'MMMMCMXCIX' (4999).For technical reasons each list is prepended with the empty character. The algorithm is a simple fourfold loop.<jupyter_code>#collapse
def romans() -> List[str]:
    """
    :return: romans numbers from 1 to 4999
    """
    digits0 = ['', 'M', 'MM', 'MMM', 'MMMM']
    digits1 = ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']
    digits2 = ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
    digits3 = ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']
   
    result = []
    for d0 in digits0:
        for d1 in digits1:
            for d2 in digits2:
                for d3 in digits3:
                    result.append(d0 + d1 + d2 + d3)
    return result<jupyter_output><empty_output><jupyter_text>The following implementation is slightly more elegant. It is the starting point of the conjoin pattern (see xxx).This pattern is helpful if you don't know the number of nested loops or when the loop criteria depend on the statestored in a single variable, here `number`.<jupyter_code>#collapse
def romans1() -> List[str]:
    """
    :return: romans numbers from 1 to 4999
    """
    digits0 = ['', 'M', 'MM', 'MMM', 'MMMM']
    digits1 = ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']
    digits2 = ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
    digits3 = ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']
   
    result = []
    number = 4 * [None]
    for number[0] in digits0:
        for number[1] in digits1:
            for number[2] in digits2:
                for number[3] in digits3:
                    result.append(''.join(number))
    return result
run(test_09, 100, romans, romans1)<jupyter_output>romans       | 0.1124
romans1      | 0.1038<jupyter_text>Converting to and from Roman numbers is easiest and fastest done by means of two dictionaries.Problem 10: We write a function which returns two other functions `to_roman` and `from_roman`.It generates the list of Roman numbers and a dictionary which maps Roman numbers back to integers.<jupyter_code>def test_10(r: Callable[[], Tuple[Callable[[int], str], Callable[[str], int]]]) -> None:
    to_roman, from_roman = r()
    test_eq(to_roman(0), '')
    test_eq(to_roman(1), 'I')
    test_eq(to_roman(9), 'IX')
    test_eq(to_roman(4999), 'MMMMCMXCIX' )

    test_eq(from_roman(''), 0)
    test_eq(from_roman('I'), 1)
    test_eq(from_roman('IX'), 9)
    test_eq(from_roman('MMMMCMXCIX'), 4999)

    xs = [randrange(4999) for _ in range(1000)]
    rs = [to_roman(x) for x in xs]
    ys = [from_roman(r) for r in rs]
    test_eq(xs, ys)
# collapse
def roman_trafos() -> Tuple[Callable[[int], str], Callable[[str], int]]:
    """
    :return: functions to_roman, from_roman
    to_roman_list and from_roman_map are computed once.
    They are contained in the closure of to_roman and from_roman
    """
    to_roman_list = romans()
    from_roman_map = dict((to_roman_list[n], n) for n in range(5000))

    def to_roman(n):
        return to_roman_list[n]

    def from_roman(r):
        return from_roman_map[r]

    return to_roman, from_roman
run(test_10, 10, roman_trafos)<jupyter_output>roman_trafos | 0.1108<jupyter_text>Pascal's Triangle, Binomial Coefficients Problem 11: Write a function `bico(n: int) -> List[int]` which returns the binomial coefficients of $(a + b)^n$<jupyter_code>def test_11(b: Callable[[int], List[str]]) -> None:
    test_eq(b(0), [1])
    test_eq(b(1), [1, 1])
    test_eq(b(2), [1, 2, 1])
    test_eq(b(5), [1, 5, 10, 10, 5, 1])<jupyter_output><empty_output><jupyter_text>Idea: We apply the defining rule of Pascals triangle:The first and last element of each row is 1; the topmost row is just 1.Every coefficient is the sum of the two coefficients above.<jupyter_code>#collapse
def bico(n: int) -> List[int]:
    """
    :param n: an integer >= 0
    :return: coefficients of (a + b) ** n
    """
    triangle = [[1]]  # that's all for n = 0
    for k in range(1, n + 1):
        triangle.append([1])  # append a new line starting with 1
        for i in range(k - 1):  # apply the rule for computing the pascal triangle
            triangle[k].append(triangle[k - 1][i] + triangle[k - 1][i + 1])
        triangle[k].append(1)  # append final 1

    return triangle[n]  # return last line<jupyter_output><empty_output><jupyter_text>The recursive solution follows the same idea. The loop is replaced with the recursive call.<jupyter_code>#collapse
def bico1(n: int) -> List[int]:
    """
    :param n: an integer >= 0
    :return: coefficients of (a + b) ** n
    recursive implementation
    """
    if n == 0:
        return [1]
    else:
        previous_line = bico1(n - 1)
        this_line = [1]  # set first coefficient = 1
        for i in range(n - 1):  # apply the rule for computing the pascal triangle
            this_line.append(previous_line[i] + previous_line[i + 1])
        this_line.append(1)  # append last coefficient = 1

    return this_line
run(test_11, 100, bico, bico1)<jupyter_output>bico         | 0.0136
bico1        | 0.0134
{'fraction_non_alphanumeric': 0.13738943982846422, 'fraction_numerical': 0.03473599571160547, 'mean_word_length': 3.3660191902644514, 'pattern_counts': {'":': 0, '<': 127, '<?xml version=': 0, '>': 173, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '32', 'dir': 'jupyter-structured-clean-dedup', 'id': '641591', 'license': 'Apache-2.0', 'n_tokens_mistral': 7242, 'n_tokens_neox': 6700, 'n_words': 2185, 'path': 'nbs/01_warmingup.ipynb', 'repo_name': 'johsieders/fttp', 'size': '18655'}