Solutions: You can find the file with solutions for all questions here.

Required questions

Question 1: Coordinates

Implement a function coords, which takes a function, a sequence, and an upper and lower bound on output of the function. coords then returns a list of x, y coordinate pairs (lists) such that:

  • Each pair contains [x, fn(x)]
  • The x coordinates are the elements in the sequence
  • Only pairs whose y coordinate is within the upper and lower bounds (inclusive)

See the doctests for examples.

One other thing: your answer can only be one line long. You should make use of list comprehensions!

def coords(fn, seq, lower, upper):
    """
    >>> seq = [-4, -2, 0, 1, 3]
    >>> def fn(x):
    ...     return x**2
    >>> coords(fn, seq, 1, 9)
    [[-2, 4], [1, 1], [3, 9]]
    """
    return [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]

Use OK to test your code:

python3 ok -q coords --local

Question 2: Repeated

Implement repeated(f, n):

  • f is a one-argument function that takes a number and returns another number.
  • n is a positive integer

repeated returns another function that, when given an argument x, will compute f(f(....(f(x))....)) (apply f a total n times). For example, repeated(square, 3)(42) evaluates to square(square(square(42))).

def repeated(f, n):
    """Return the function that computes the nth application of f.
    >>> def increment(x):
    ...     return x + 1
    >>> def square(x):
    ...     return x**2
    >>> def triple(x):
    ...     return x*3
    >>> add_three = repeated(increment, 3)
    >>> add_three(5)
    8
    >>> repeated(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
    243
    >>> repeated(square, 2)(5) # square(square(5))
    625
    >>> repeated(square, 4)(5) # square(square(square(square(5))))
    152587890625
    """
    g = f
    while n > 1:
        g = compose1(f, g)
        n = n - 1
    return g

# Alternates

def repeated2(f, n):
    def h(x):
        k = 0
        while k < n:
            x, k = f(x), k + 1
        return x
    return h

def repeated3(f, n):
    return accumulate(compose1, f, n-1, lambda k: f)

Hint: You may find it convenient to use compose1 from the textbook:

def compose1(f, g):
    """Return a function h, such that h(x) = f(g(x))."""
    def h(x):
        return f(g(x))
    return h

Use OK to test your code:

python3 ok -q repeated --local

There are many correct ways to implement repeated. The first solution above creates a new function in every iteration of the while statement (via compose1). The second solution shows that it is also possible to implement repeated by creating only a single new function. That function repeatedly applies f.

repeated can also be implemented compactly using accumulate, the third solution.

Question 3: Double

Using repeated define a function double that takes a function of one argument as an argument and returns a function that applies the original function twice. For example, if inc is a function that returns 1 more than its argument, then double(inc) should be a function that returns two more:

def double(f):
    """ Return a function that applies f twice.

    f -- a function that takes one argument

    >>> def square(x):
    ...     return x**2
    >>> double(square)(2)
    16
    """
    return repeated(f, 2)

Use OK to test your code:

python3 ok -q double --local

Note that using compose1 from class, the body of double can also be written as return compose1(f, f).

Question 4: Count van Count

Consider the following implementations of count_factors and count_primes:

def count_factors(n):
    """Return the number of positive factors that n has."""
    i, count = 1, 0
    while i <= n:
        if n % i == 0:
            count += 1
        i += 1
    return count

def count_primes(n):
    """Return the number of prime numbers up to and including n."""
    i, count = 1, 0
    while i <= n:
        if is_prime(i):
            count += 1
        i += 1
    return count

def is_prime(n):
    return count_factors(n) == 2 # only factors are 1 and n

The implementations look quite similar! Generalize this logic by writing a function count_cond, which takes in a two-argument predicate function condition(n, i). count_cond returns a count of all the numbers from 1 to n that satisfy condition.

Note: A predicate function is a function that returns a boolean (True or False).

def count_cond(condition, n):
    """
    >>> def divisible(n, i):
    ...     return n % i == 0
    >>> count_cond(divisible, 2) # 1, 2
    2
    >>> count_cond(divisible, 4) # 1, 2, 4
    3
    >>> count_cond(divisible, 12) # 1, 2, 3, 4, 6, 12
    6

    >>> def is_prime(n, i):
    ...     return count_cond(divisible, i) == 2
    >>> count_cond(is_prime, 2) # 2
    1
    >>> count_cond(is_prime, 3) # 2, 3
    2
    >>> count_cond(is_prime, 4) # 2, 3
    2
    >>> count_cond(is_prime, 5) # 2, 3, 5
    3
    >>> count_cond(is_prime, 20) # 2, 3, 5, 7, 11, 13, 17, 19
    8
    """
    i, count = 1, 0
    while i <= n:
        if condition(n, i):
            count += 1
        i += 1
    return count

Use OK to test your code:

python3 ok -q count_cond --local

Question 5: Match and Apply

Sometimes when we are given a dataset, we need to alter it for specific values. For example, say we have a table with one column being people's names and the other being the price they have to pay.

We can use a list of pairs for this:

[["Jessica", 5], ["Andrew", 9], ["Alex", 2], ["Amir", 11], ["John", 3], ["Ting", 2]]

The first value in each pair is the name, the second is the price.

Now, let's say we want to give a discount to specific people. We have a discount function that we want to apply to the person's price. Now, we need a function that will only apply the discount function to specific people.

Implement match_and_apply(pairs, function):

  • pairs is a list of pairs.
  • function is some function

match_and_apply returns a function such that when the function is given an input that matches the first of a pair, returns the result of applying function to the second value in the pair.

def match_and_apply(pairs, function):
    """
    >>> pairs = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 0]]
    >>> def square(num):
    ...     return num**2
    >>> func = match_and_apply(pairs, square)
    >>> result = func(3)
    >>> result
    16
    >>> result = func(1)
    >>> result
    4
    >>> result = func(7)
    >>> result
    64
    >>> result = func(15)
    >>> print(result)
    None

    """
    def foo(num):
        for pair in pairs:
            if pair[0] == num:
                return function(pair[1])
        return None
    return foo

Use OK to test your code:

python3 ok -q match_and_apply --local