Instructions

In this homework, you are required to complete the problems described in section 2. The starter code for these problems is provided in hw05.py.

Submission: As instructed before, you need to submit your work with Ok by python ok --submit. You may submit more than once before the deadline, and your score of this assignment will be the highest one of all your submissions.

Readings: You might find the following references to the textbook useful:

• Section 2.4
• Section 4.2

Required Problems

In this section, you are required to complete the problems below and submit your code to OJ website.

Remember, you can use ok to test your code:

$ python ok  # test all functions
$ python ok -q <func>  # test single function

Problem 1: Password Protected Account (100pts)

In the lecture, we learned how to use functions to create mutable objects. Below is a function make_withdraw which produces a function that can withdraw money from an account:

def make_withdraw(balance):
    """Return a withdraw function with BALANCE as its starting balance.
    >>> withdraw = make_withdraw(1000)
    >>> withdraw(100)
    900
    >>> withdraw(100)
    800
    >>> withdraw(900)
    'Insufficient funds'
    """
    def withdraw(amount):
        nonlocal balance
        if amount > balance:
           return 'Insufficient funds'
        balance = balance - amount
        return balance
    return withdraw

Write a version of the make_withdraw function that returns password-protected withdraw functions. That is, make_withdraw should take a password argument (a string) in addition to an initial balance. The returned function should take two arguments: an amount to withdraw and a password.

A password-protected withdraw function should only process withdrawals when input password is correct. Upon receiving an incorrect password, the function should:

1. Store that incorrect password in a list, and
2. Return the string 'Incorrect password'.

If a withdraw function has been called three times with incorrect passwords <p1>, <p2>, and <p3>, then it is locked. All subsequent calls to the function should return:

"Your account is locked. Attempts: [<p1>, <p2>, <p3>]"

The incorrect passwords may be identical or different:

def make_withdraw(balance, password):
    """Return a password-protected withdraw function.

    >>> w = make_withdraw(100, 'hax0r')
    >>> w(25, 'hax0r')
    75
    >>> error = w(90, 'hax0r')
    >>> error
    'Insufficient funds'
    >>> error = w(25, 'hwat')
    >>> error
    'Incorrect password'
    >>> new_bal = w(25, 'hax0r')
    >>> new_bal
    50
    >>> w(75, 'a')
    'Incorrect password'
    >>> w(10, 'hax0r')
    40
    >>> w(20, 'n00b')
    'Incorrect password'
    >>> w(10, 'hax0r')
    "Your account is locked. Attempts: ['hwat', 'a', 'n00b']"
    >>> w(10, 'l33t')
    "Your account is locked. Attempts: ['hwat', 'a', 'n00b']"
    >>> type(w(10, 'l33t')) == str
    True
    """
    "*** YOUR CODE HERE ***"

You may find Python string formatting syntax useful. A quick example:

>>> ten, twenty, thirty = 10, 'twenty', [30]
>>> '{0} plus {1} is {2}'.format(ten, twenty, thirty)
'10 plus twenty is [30]'

Problem 2: Joint Account (100pts)

Suppose that our banking system requires the ability to make joint accounts, which enables an additional password for for original account. Please help to define the function make_joint that takes three arguments.

1. A password-protected withdraw function, like the one generated by make_withdraw.
2. Any registered password for withdraw function.
3. The additional password you want to enable to access the original account.

If the old password is incorrect or the account is already locked, make_joint should propagate the error. Otherwise, it returns a withdraw function that provides additional access to the original account using either the new or old password. Both functions draw from the same balance. Incorrect passwords provided to either function will be stored and cause the functions to be locked after three wrong attempts.

Hint1: The solution is short (less than 10 lines) and contains no string literals! The key is to call withdraw with the right password and amount, then interpret the result. You may assume that all failed attempts to withdraw will return some string (for incorrect passwords, locked accounts, or insufficient funds), while successful withdrawals will return a number.

Hint2: You can use type(value) == str to test if some value is a string.

def make_joint(withdraw, old_pass, new_pass):
    """Return a password-protected withdraw function that has joint access to
    the balance of withdraw.

    >>> w = make_withdraw(100, 'hax0r')
    >>> w(25, 'hax0r')
    75
    >>> make_joint(w, 'my', 'secret')
    'Incorrect password'
    >>> j = make_joint(w, 'hax0r', 'secret')
    >>> w(25, 'secret')
    'Incorrect password'
    >>> j(25, 'secret')
    50
    >>> j(25, 'hax0r')
    25
    >>> j(100, 'secret')
    'Insufficient funds'

    >>> j2 = make_joint(j, 'secret', 'code')
    >>> j2(5, 'code')
    20
    >>> j2(5, 'secret')
    15
    >>> j2(5, 'hax0r')
    10

    >>> j2(25, 'password')
    'Incorrect password'
    >>> j2(5, 'secret')
    "Your account is locked. Attempts: ['my', 'secret', 'password']"
    >>> j(5, 'secret')
    "Your account is locked. Attempts: ['my', 'secret', 'password']"
    >>> w(5, 'hax0r')
    "Your account is locked. Attempts: ['my', 'secret', 'password']"
    >>> make_joint(w, 'hax0r', 'hello')
    "Your account is locked. Attempts: ['my', 'secret', 'password']"
    """
    "*** YOUR CODE HERE ***"

Problem 3: Generate Permutations (200pts)

Given a sequence of unique elements, a permutation of the sequence is a list containing the elements of the sequence in arbitrary order. For example, [2, 1, 3], [1, 3, 2], and [3, 2, 1] are some of the permutations of the sequence [1, 2, 3]. [] is the only permutation of [].

Implement permutations, a generator function that takes in a sequence seq and returns a generator that yields all permutations of seq.

Permutations may be yielded in any order. Note that the doctests test whether you are yielding all possible permutations, but not the order. The built-in sorted function takes in an iterable object and returns a list containing the elements of the iterable in non-decreasing order.

Hint1: If you had the permutations of all the elements in seq not including the first element, how could you use that to generate the permutations of the full seq?

Hint2: There is no need to use some advanced non-recursive algorithms, which you may find on the Internet. Combination of yield and recursion is sufficient.

def permutations(seq):
    """Generates all permutations of the given sequence. Each permutation is a
    list of all elements in seq. The permutations could be yielded in any order.

    >>> perms = permutations([100])
    >>> type(perms)
    <class 'generator'>
    >>> next(perms)
    [100]
    >>> try: #this piece of code prints "No more permutations!" if calling next would cause an error
    ...     next(perms)
    ... except StopIteration:
    ...     print('No more permutations!')
    No more permutations!
    >>> sorted(permutations([1, 2, 3])) # Returns a sorted list containing elements of the generator
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    >>> sorted(permutations((10, 20, 30)))
    [[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
    >>> sorted(permutations("ab"))
    [['a', 'b'], ['b', 'a']]
    """
    "*** YOUR CODE HERE ***"

Problem 4: Two Sum (100pts)

Hugh wants to solve the famous difficult problem: two sum. This problem asks whether there exists two different items in a list whose sum is equal to a given target number. For example, if the list is [1, 2, 3, 4, 5] and the given target number is 7, then the answer is True because 2 + 5 = 7. If the given target number is 2, then the answer is False because no two items sum to 2.

He knows he can solve the problem by enumerating every possible element pairs. He has written a function two_sum_pairs to check if there is a pair in a list of pairs having summation equal to target. Could you please help to write a function pairs that returns the search space of all pairs for input list? You can yield a pair (i, j) with yield i, j, and pattern match a pair with (i, j) = pair.

def two_sum_pairs(target, pairs):
    """Return True if there is a pair in pairs that sum to target."""
    for i, j in pairs:
        if i + j == target:
            return True
    return False

def pairs(lst):
    """Yield the search space for two_sum_pairs.

    >>> two_sum_pairs(1, pairs([1, 3, 3, 4, 4]))
    False
    >>> two_sum_pairs(8, pairs([1, 3, 3, 4, 4]))
    True
    >>> lst = [1, 3, 3, 4, 4]
    >>> plst = pairs(lst)
    >>> n, pn = len(lst), len(list(plst))
    >>> n * (n - 1) / 2 == pn
    True
    """
    "*** YOUR CODE HERE ***"

Suddenly, Hugh got the inspiration that he only needs to visit each element once, because there is a fact that for a given target number target, an element v is a possible candidate for the solution if and only if there exists another element t equals to target - v. Hugh may design a quicker algorithm by utilizing this condition. Could you help him complete the following function? As a reminder, you can check whether an element elem is in a list lst with elem in lst.

def two_sum_list(target, lst):
    """Return True if there are two different elements in lst that sum to target.

    >>> two_sum_list(1, [1, 3, 3, 4, 4])
    False
    >>> two_sum_list(8, [1, 3, 3, 4, 4])
    True
    """
    visited = []
    for val in lst:
        "*** YOUR CODE HERE ***"

    return False

After you finished, try to register and submit your solution to leetcode too :)

Is Hugh's final solution quicker?

Problem 5: Trictionary or Treat (200pts)

A trictionary is a pair of tree k and v. They have identical structure: each node in k has a corresponding node in v. The labels in k are called keys. Each key may be the label for multiple nodes in k, and the values for that key are the labels of all the corresponding nodes in v.

A lookup function returns one of the values for a key. Specifically, a lookup function for a node in k is a function that takes v as an argument and returns the label for the corresponding node in v.

Implement the generator function lookups, which takes as input a tree k and a key. It yields all lookup functions for nodes in k that have key as their label, the functions could be yielded in any order.

def lookups(k, key):
    """Yield one lookup function for each node of k that has the label key.
    >>> k = tree(5, [tree(7, [tree(2)]), tree(8, [tree(3), tree(4)]), tree(5, [tree(4), tree(2)])])
    >>> v = tree('Go', [tree('C', [tree('C')]), tree('A', [tree('S'), tree(6)]), tree('L', [tree(1), tree('A')])])
    >>> type(lookups(k, 4))
    <class 'generator'>
    >>> sorted([f(v) for f in lookups(k, 2)])
    ['A', 'C']
    >>> sorted([f(v) for f in lookups(k, 3)])
    ['S']
    >>> [f(v) for f in lookups(k, 6)]
    []
    """
    "*** YOUR CODE HERE ***"

Just for fun Problems

This section is out of scope for our course, so the problems below is optional. That is, the problems in this section don't count for your final score and don't have any deadline. Do it at any time if you want an extra challenge or some practice with higher order function and abstraction!

To check the correctness of your answer, you can submit your code to Contest 'Just for fun'.

Problem 6: Remainder Generator (0pts)

Like functions, generators can also be higher-order. For this problem, we will be writing remainders_generator, which yields a series of generator objects.

remainders_generator takes in an integer m, and yields m different generators. The first generator is a generator of multiples of m, i.e. numbers where the remainder is 0. The second is a generator of natural numbers with remainder 1 when divided by m. The last generator yields natural numbers with remainder m - 1 when divided by m. Note that different generators should not influence each other.

Hint: Consider defining an inner generator function. Each yielded generator varies only in that the elements of each generator have a particular remainder when divided by m. What does that tell you about the argument(s) that the inner function should take in?

def remainders_generator(m):
    """Yields m generators. The ith yielded generator yields natural numbers whose
    remainder is i when divided by m.

    >>> import types
    >>> [isinstance(gen, types.GeneratorType) for gen in remainders_generator(5)]
    [True, True, True, True, True]
    >>> remainders_four = remainders_generator(4)
    >>> for i in range(4):
    ...     print("First 3 natural numbers with remainder {0} when divided by 4:".format(i))
    ...     gen = next(remainders_four)
    ...     for _ in range(3):
    ...         print(next(gen))
    First 3 natural numbers with remainder 0 when divided by 4:
    0
    4
    8
    First 3 natural numbers with remainder 1 when divided by 4:
    1
    5
    9
    First 3 natural numbers with remainder 2 when divided by 4:
    2
    6
    10
    First 3 natural numbers with remainder 3 when divided by 4:
    3
    7
    11
    """
    "*** YOUR CODE HERE ***"

Note that if you have implemented this correctly, each of the generators yielded by remainder_generator will be infinite - you can keep calling next on them forever without running into a StopIteration exception.

Problem 7: Primes

Bernard: What if the Prime Minister insists we help them?

Humphrey: Then we follow the four-stage strategy...

A prime number is a number that can only be divided by itself and 1 without remainders. A classic algorithm to obtain prime numbers is the sieve method, which is performed as follows:

1. We start from 2, as 1 is not a prime number
2. Take the smallest number p (initially 2), p must be a prime number
3. Sieve out all the numbers that can be divided by p, these cannot be primes
4. Goto step 1

Hint: You may want to use filter and recursion.

def starting_from(start):
    """Yields natural numbers starting from start.

    >>> sf = starting_from(0)
    >>> [next(sf) for _ in range(10)] == list(range(10))
    True
    """
    "*** YOUR CODE HERE ***"


def sieve(t):
    """Suppose the smallest number from t is p, sieves out all the
    numbers that can be divided by p (except p itself) and recursively
    sieves out all the multiples of the next smallest number from the
    reset of of the sequence.

    >>> list(sieve(iter([3, 4, 5, 6, 7, 8, 9])))
    [3, 4, 5, 7]
    >>> list(sieve(iter([2, 3, 4, 5, 6, 7, 8])))
    [2, 3, 5, 7]
    >>> list(sieve(iter([1, 2, 3, 4, 5])))
    [1]
    """
    "*** YOUR CODE HERE ***"


def primes():
    """Yields all the prime numbers.

    >>> p = primes()
    >>> [next(p) for _ in range(10)]
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """
    "*** YOUR CODE HERE ***"