Due by 11:59pm on Tuesday, 8/9

Instructions

Download hw10.zip. Inside the archive, you will find a file called hw10.py, along with a copy of the OK autograder.

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. See Lab 0 for instructions on submitting assignments.

Using OK: If you have any questions about using OK, please refer to this guide.

Readings: You might find the following references useful:

Generators

The following problem will be used as part of the AutoStyle study, which you can find more information about on Piazza. Participation in this study will be rewarded with extra credit.

Question 1: Generate Permutations

Given a list of unique elements, a permutation of the list is a reordering of the elements. For example, [2, 1, 3], [1, 3, 2], and [3, 2, 1] are all permutations of the list [1, 2, 3].

Implement permutations, a generator function that takes in a lst and outputs all permutations of lst, each as a list (see doctest for an example).

def permutations(lst):
    """Generates all permutations of sequence LST.  Each permutation is a
    list of the elements in LST in a different order.

    >>> sorted(permutations([1, 2, 3]))
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    >>> type(permutations([1, 2, 3]))
    <class 'generator'>
    >>> 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']]
    """
    if not lst:
        yield []
        return
    "*** YOUR CODE HERE ***"

The order in which you generate permutations is irrelevant. Hint: This problem yields to recursion. If you had the permutations of a subsequence of a that was missing one element, how could generate from it the permutations of the full sequence?

Use OK to test your code:

python3 ok -q permutations

Now you have the chance to improve your coding style for this question. Once you have passed all the tests, invoke AutoStyle by running the command python3 ok --style -q permutations. AutoStyle will provide to you hints that improve the style of your code.

When running AutoStyle please don't place any print statements into your code. If you want to test your code with print statements, try running it locally on your machine!

If you are having issues, please send an email to auto.style@berkeley.edu with a picture of the error as well as your code.

Review

Question 2: Nearest Power of Two

Implement the function nearest_two, which takes as input a positive number x and returns the power of two (..., 1/8, 1/4, 1/2, 1, 2, 4, 8, ...) that is nearest to x. If x is exactly between two powers of two, return the larger.

You may change the starter implementation if you wish.

def nearest_two(x):
    """Return the power of two that is nearest to x.

    >>> nearest_two(8)    # 2 * 2 * 2 is 8
    8.0
    >>> nearest_two(11.5) # 11.5 is closer to 8 than 16
    8.0
    >>> nearest_two(14)   # 14 is closer to 16 than 8
    16.0
    >>> nearest_two(2015)
    2048.0
    >>> nearest_two(.1)
    0.125
    >>> nearest_two(0.75) # Tie between 1/2 and 1
    1.0
    >>> nearest_two(1.5)  # Tie between 1 and 2
    2.0

    """
    power_of_two = 1.0
    "*** YOUR CODE HERE ***"
    return power_of_two

Use OK to test your code:

python3 ok -q nearest_two

Question 3: Smoothing

The idea of smoothing a function is a concept used in signal processing among other things. If f is a one-argument function and dx is some small number, then the smoothed version of f is the function whose value at a point x is the average of f(x - dx), f(x), and f(x + dx). Write a function smooth that takes as input a function f and a value to use for dx and returns a function that computes the smoothed version of f. Do not use any def statements inside of smooth; use lambda expressions instead.

def smooth(f, dx):
    """Returns the smoothed version of f, g where

    g(x) = (f(x - dx) + f(x) + f(x + dx)) / 3

    >>> square = lambda x: x ** 2
    >>> round(smooth(square, 1)(0), 3)
    0.667
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q smooth

It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtain the n-fold smoothed function. Show how to generate the n-fold smoothed function, n_fold_smooth, of any given function using your smooth function and repeated function:

def repeated(f, n):
    """Returns a single-argument function that takes a value, x, and applies
    the single-argument function F to x N times.
    >>> repeated(lambda x: x*x, 3)(2)
    256
    """
    def h(x):
        for k in range(n):
            x = f(x)
        return x
    return h

As with smooth, use lambda expressions rather than def statements in the body of n_fold_smooth.

def n_fold_smooth(f, dx, n):
    """Returns the n-fold smoothed version of f

    >>> square = lambda x: x ** 2
    >>> round(n_fold_smooth(square, 1, 3)(0), 3)
    2.0
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q n_fold_smooth

Question 4: Advanced Counter

Complete the definition of make_advanced_counter_maker, which creates a function that creates counters. These counters can not only update their personal count, but also a shared count for all counters. They can also reset either count.

def make_advanced_counter_maker():
    """Makes a function that makes counters that understands the
    messages "count", "global-count", "reset", and "global-reset".
    See the examples below:

    >>> make_counter = make_advanced_counter_maker()
    >>> tom_counter = make_counter()
    >>> tom_counter('count')
    1
    >>> tom_counter('count')
    2
    >>> tom_counter('global-count')
    1
    >>> jon_counter = make_counter()
    >>> jon_counter('global-count')
    2
    >>> jon_counter('count')
    1
    >>> jon_counter('reset')
    >>> jon_counter('count')
    1
    >>> tom_counter('count')
    3
    >>> jon_counter('global-count')
    3
    >>> jon_counter('global-reset')
    >>> tom_counter('global-count')
    1
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q make_advanced_counter_maker

Question 5: Deck of cards

Write a list comprehension that will create a deck of cards, given a list of suits and a list of ranks. Each element in the list will be a card, which is represented by a 2-element list of the form [suit, rank].

def deck(suits, ranks):
    """Creates a deck of cards (a list of 2-element lists) with the given
    suits and ranks. Each element in the returned list should be of the form
    [suit, rank].

    >>> deck(['S', 'C'], [1, 2, 3])
    [['S', 1], ['S', 2], ['S', 3], ['C', 1], ['C', 2], ['C', 3]]
    >>> deck(['S', 'C'], [3, 2, 1])
    [['S', 3], ['S', 2], ['S', 1], ['C', 3], ['C', 2], ['C', 1]]
    >>> deck([], [3, 2, 1])
    []
    >>> deck(['S', 'C'], [])
    []
    """
    "*** YOUR CODE HERE ***"
    return ______

Use OK to test your code:

python3 ok -q deck

Question 6: Riffle Shuffle

The familiar riffle shuffle of a deck of cards (or in our case, of a sequence of things) results in a new configuration of cards in which the original top card is followed by the original middle card, then by the original second card, then the card after the middle, and so forth. Assuming the deck (sequence) contains an even number of cards, write a list comprehension that produces the shuffled sequence.

Hint: To write this as a single comprehension, you may find the expression k%2, which evaluates to 0 on even numbers and 1 on odd numbers, to be useful.

def riffle(deck):
    """Produces a single, perfect riffle shuffle of DECK, consisting of
    DECK[0], DECK[M], DECK[1], DECK[M+1], ... where M is position of the
    second half of the deck.  Assume that len(DECK) is even.
    >>> riffle([3, 4, 5, 6])
    [3, 5, 4, 6]
    >>> riffle(range(20))
    [0, 10, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19]
    """
    "*** YOUR CODE HERE ***"
    return _______

Use OK to test your code:

python3 ok -q riffle

Question 7: Graph Cycles

A graph in computer science refers to a structure such as this:

graph

The circles are called vertices (singular vertex) and the lines joining vertices are called edges. The letters in the vertices are vertex labels.

This particular graph is directed, meaning that the edges have a direction (shown by the arrows). We say that a directed graph is cyclic if there is a path constructed from edges that leads from some vertex back to itself. For example, the sample graph is cyclic because, among other examples, one can follow edges from A->B->C->F->G->A.

If we identify the vertices of a graph by their labels, then we can represent a graph as a dictionary mapping each vertex label L to a list successor vertices' labels (vertices at the other ends of arrows pointing out of L). Thus, the sample graph would be:

G = { 'A': ['B', 'D'], 'B': ['C'], 'C': ['F'], 'D': ['E'], 
      'E': ['F'], 'F': ['G'], 'G': ['A'] }

Dag Hacker has developed the following program to determine if a graph represented in this fashion is circular:

def is_circular(G):
    """Return true iff G represents a circular directed graph."""
    for v in G:
        if reaches_circularity(G, v):
            return True
    return False

def reaches_circularity(G, v0):
    """Returns true if there is a circularity in G in some path
    starting from vertex V0."""
    def is_path_to_cycle(v1):
        for w in G[v1]:
            if v0 == w:
                return True
            if is_path_to_cycle(w):
                return True
        return False
    return is_path_to_cycle(v0)

Unfortunately, his reaches_circularity function does not always work. It gives correct answers on acyclic graphs (graphs that are not cyclic), but often goes into infinite loops on cyclic ones. Fill in the program below to fix Dag's problem:

def reaches_circularity(G, v0):
    """Returns true if there is a circularity in G in some path
    starting from vertex V0.
    >>> G = { 'A': ['B', 'D'], 'B': ['C'], 'C': ['F'], 'D': ['E'], 
    ...       'E': ['F'], 'F': ['G'], 'G': ['A'] }
    >>> is_circular(G)
    True
    >>> G['F'] = []
    >>> is_circular(G)
    False
    """
    "*** YOUR CODE HERE ***"

Hint: The problem has to do with what happens if there is a cycle in a path that starts at vertex v, but does not include v itself.

Use OK to test your code:

python3 ok -q reaches_circularity

Question 8: Find Intersection

Implement intersection, which takes two linked lists, xs and ys, and finds the Link at which the two linked list begin to intersect (or overlap). You may assume that xs and ys are normal, non-circular linked lists, so that they will always overlap at Link.empty (at least).

For the two linked lists below, z1 should be the start of the linked list that you return. You are not simply looking to see if the Links in the overlapping part have the same first fields; you are trying to find the first Link object that is part of both lists.

See if you can find a way to do this in θ(n) time (where n is the sum of the lengths of xs and ys), and with constant additional space (i.e., without introducing any Python lists, or creating new Links; just using a few integer or Link-valued local variables.)

xs:       x1 -> z1 -> z2 -> z3 -> ...
                 ^
                 |
ys:  y1 -> y2 -> y3

Hint: How would you do this given two lists of the same length?

def intersection(xs, ys):
    """
    >>> a = Link(1)
    >>> intersection(a, Link.empty) is Link.empty
    True

    >>> b = a
    >>> intersection(a, b).first # intersection begins at a
    1

    >>> looks_like_a = Link(1)
    >>> intersection(a, looks_like_a) is Link.empty # no intersection! (identity vs value)
    True

    >>> b = Link(1, Link(2, Link(3, a)))
    >>> a.first = 5
    >>> intersection(a, b).first # intersection begins at a
    5

    >>> c = Link(3, b)
    >>> intersection(b, c).first # intersection begins at b
    1
    >>> intersection(c, b).first # intersection begins at b
    1

    >>> intersection(a, c).first # intersection begins at a
    5
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q intersection