Lab 14: Final Review

Starter Files

Download lab14.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Linked Lists

Question 1: Remove All

Implement a function remove_all that takes a Link, and a value, and remove any list node containing that value. You can assume the list already has at least one node containing value and the first element is never removed. Notice that you are not returning anything, so you should mutate the list.

def remove_all(link , value):
    """Remove all the nodes containing value. Assume there exists some
    nodes to be removed and the first element is never removed.

    >>> l1 = Link(0, Link(2, Link(2, Link(3, Link(1, Link(2, Link(3)))))))
    >>> print_link(l1)
    <0 2 2 3 1 2 3>
    >>> remove_all(l1, 2)
    >>> print_link(l1)
    <0 3 1 3>
    >>> remove_all(l1, 3)
    >>> print_link(l1)
    <0 1>
    """

    "*** YOUR CODE HERE ***"

    if link is Link.empty or link.rest is Link.empty:
        return
    if link.rest.first == value:
        link.rest = link.rest.rest
        remove_all(link, value)
    else:
        remove_all(link.rest, value)

    # alternate solution
    if link is not Link.empty and link.rest is not Link.empty:
        remove_all(link.rest, value)
        if link.rest.first == value:
            link.rest = link.rest.rest

Use OK to test your code:

python3 ok -q remove_all

Trees

Question 2: Reverse Other

Write a function reverse_other that mutates the tree such that every other (odd_indexed) level of the tree's entries are all reversed. For example Tree(1,[Tree(2), Tree(3)]) becomes Tree(1,[Tree(3), Tree(2)])

def reverse_other(t):
    """Reverse the entries of every other level of the tree using mutation.

    >>> t = Tree(1, [Tree(2), Tree(3), Tree(4)])
    >>> reverse_other(t)
    >>> t
    Tree(1, [Tree(4), Tree(3), Tree(2)])
    >>> t = Tree(1, [Tree(2, [Tree(5, [Tree(7), Tree(8)]), Tree(6)]), Tree(3)])
    >>> reverse_other(t)
    >>> t
    Tree(1, [Tree(3, [Tree(5, [Tree(8), Tree(7)]), Tree(6)]), Tree(2)])
    """

    "*** YOUR CODE HERE ***"

    def reverse_helper(t, need_reverse):
        if t.is_leaf():
            return
        new_labs = [child.root for child in t.branches][::-1]
        for i in range(len(t.branches)):
            child = t.branches[i]
            reverse_helper(child, not need_reverse)
            if need_reverse:
                child.root = new_labs[i]
    reverse_helper(t, True)

Use OK to test your code:

python3 ok -q reverse_other

Object-Oriented Programming

Question 3: Mint

Complete the Mint and Coin classes so that the coins created by a mint have the correct year and worth.

  • Each Mint instance has a year stamp. The update method sets the year stamp to the current_year class attribute of the Mint class.
  • The create method takes a subclass of Coin and returns an instance of that class stamped with the mint's year (which may be different from Mint.current_year if it has not been updated.)
  • A Coin's worth method returns the cents value of the coin plus one extra cent for each year of age beyond 50. A coin's age can be determined by subtracting the coin's year from the current_year class attribute of the Mint class.
class Mint:
    """A mint creates coins by stamping on years.

    The update method sets the mint's stamp to Mint.current_year.

    >>> mint = Mint()
    >>> mint.year
    2017
    >>> dime = mint.create(Dime)
    >>> dime.year
    2017
    >>> Mint.current_year = 2100  # Time passes
    >>> nickel = mint.create(Nickel)
    >>> nickel.year     # The mint has not updated its stamp yet
    2017
    >>> nickel.worth()  # 5 cents + (85 - 50 years)
    38
    >>> mint.update()   # The mint's year is updated to 2100
    >>> Mint.current_year = 2175     # More time passes
    >>> mint.create(Dime).worth()    # 10 cents + (75 - 50 years)
    35
    >>> Mint().create(Dime).worth()  # A new mint has the current year
    10
    >>> dime.worth()     # 10 cents + (160 - 50 years)
    118
    >>> Dime.cents = 20  # Upgrade all dimes!
    >>> dime.worth()     # 20 cents + (160 - 50 years)
    128


    >>> m = Mint()
    >>> n = m.create(Nickel)
    >>> n.worth()
    5
    >>> n.year = 2017
    >>> n.worth()
    113

    """
    current_year = 2017

    def __init__(self):
        self.update()

    def create(self, kind):

        "*** YOUR CODE HERE ***"

        return kind(self.year)

    def update(self):

        "*** YOUR CODE HERE ***"

        self.year = Mint.current_year

class Coin:
    def __init__(self, year):
        self.year = year

    def worth(self):

        "*** YOUR CODE HERE ***"

        return self.cents + max(0, Mint.current_year - self.year - 50)

class Nickel(Coin):
    cents = 5

class Dime(Coin):
    cents = 10

Use OK to test your code:

python3 ok -q Mint

Scheme

Scheme questions are to be done in lab14.scm.

Question 4: Accumulate

Fill in the definition for the procedure accumulate, which combines the first n natural numbers according to the following parameters:

  1. combiner: a function of two arguments
  2. start: a number with which to start combining
  3. n: the number of natural numbers to combine
  4. term: a function of one argument that computes the nth term of a sequence

For example, we can find the product of all the numbers from 1 to 5 by using the multiplication operator as the combiner, and starting our product at 1:

scm> (define (identity x) x)
scm> (accumulate * 1 5 identity)  ; 1 * 1 * 2 * 3 * 4 * 5
120

We can also find the sum of the squares of the same numbers by using the addition operator as the combiner and square as the term:

scm> (define (square x) (* x x))
scm> (accumulate + 0 5 square)  ; 0 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
55
(define (accumulate combiner start n term)
  (if (= n 0)
      start

      'YOUR-CODE-HERE

      (combiner (accumulate combiner
                            start
                            (- n 1)
                            term)
                (term n))
  )
)

;;; Tests
(define (identity x) x)
(accumulate * 1 5 identity)
; expect 120

(define (square x) (* x x))
(accumulate + 0 5 square)
; expect 55

Use OK to test your code:

python3 ok -q accumulate

Question 5: How Many Dots?

Implement how-many-dots, which takes in a nested scheme list s and returns the number of dots that appear when it is displayed by the interpreter (not counting decimal points). You may assume that s is a nested list that contains only numbers.

Hints: A dot appears when the second element of a pair is not a well formed list. The procedures pair?, null?, and number? test whether a value is a pair, nil, or a number, respectively.

(define (how-many-dots s)

  'YOUR-CODE-HERE

  (if (not (pair? s))
    0
    (+ (if (and (not (pair? (cdr s)))
                (not (null? (cdr s))))
         1
         0)
       (how-many-dots (car s))
       (how-many-dots (cdr s))))
)

;;; Tests

(how-many-dots '(1 2 3))
; expect 0
(how-many-dots '(1 2 . 3))
; expect 1
(how-many-dots '((1 . 2) 3 . 4))
; expect 2
(how-many-dots '((((((1 . 2) . 3) . 4) . 5) . 6) . 7))
; expect 6
(how-many-dots '(1 . (2 . (3 . (4 . (5 . (6 . (7))))))))
; expect 0

Use OK to test your code:

python3 ok -q how-many-dots

Question 6: Swap

Write a tail-recursive function swap, which takes in a Scheme list s and returns a new Scheme list where every two elements in s are swapped.

(define (swap s)

  'YOUR-CODE-HERE

  (define (helper sofar rest)
    (cond ((null? rest) sofar)
          ((null? (cdr rest)) (append sofar (list (car rest))))
          (else (helper (append sofar (list (car (cdr rest)) (car rest)))
                        (cdr (cdr rest))))))
  (helper () s)
)

;;; Tests

(swap (list 1 2 3 4))
; expect (2 1 4 3)
(swap (list 1 2 3 4 5))
; expect (2 1 4 3 5)

Use OK to test your code:

python3 ok -q swap

Interpreters

Question 7: Eval/Apply

This question is from the final review.

With your Project 4 implementation, how many total calls to scheme_eval and scheme_apply would be made when evaluating the following two expressions? Assume that you are not using the tail call optimized scheme_eval_optimized function.

(define (square x) (* x x))
(+ (square 3) (- 3 2))
14 eval calls, 4 apply calls

Iterators and Generators

Question 8: Str

Write an iterator that takes a string as input and outputs the letters in order when iterated over.

class Str:
    def __init__(self, str):
        self.str = str
    def __iter__(self):
        return iter(self.str)

That works (why?), but just kidding.

class Str:
    """
    >>> s = Str("hello")
    >>> for char in s:
    ...     print(char)
    ...
    h
    e
    l
    l
    o
    >>> for char in s:    # a standard iterator does not restart
    ...     print(char)
    """

    "*** YOUR CODE HERE ***"

    def __init__(self, str):
        self.str = str
        self.i = -1

    def __iter__(self):
        return self

    def __next__(self):
        self.i += 1
        if self.i >= len(self.str):
            raise StopIteration
        return self.str[self.i]

Use OK to test your code:

python3 ok -q Str

Question 9: List-Dictionary Iterator

Create an ListDictIter iterator class that is initialized with a list and dictionary. Calling next on an instance of the class will return x. x is the dictionary value of the next item of the list, or, if the item is not a key in the dictionary, x is just the item.

Hint: you can use the get method of a dictionary to specify a default value if a key is not in the dictionary, e.g. dct.get("dog", "cat") will return either the value that "dog" is a key for in dct, or "cat" if "dog" is not a key.

class ListDictIter:
    """ Returns an iterator that yields either the corresponding 
    dictionary value of the next element in the list or the element
    itself if it is not a key in the dictionary.

    >>> sounds = {'cat': 'meow', 'cow': 'moo','ghost': 'boo'}
    >>> things = ['cat', 'moo', 'ghost', 'pikachu']
    >>> x = ListDictIter(things, sounds)
    >>> list(x)
    ['meow', 'moo', 'boo', 'pikachu']
    >>> y = ListDictIter(things, sounds)
    >>> next(y)
    'meow'
    >>> next(y)
    'moo'
    """

    def __init__(self, lst, dct):

        "*** YOUR CODE HERE ***"

        self.lst = lst
        self.dct = dct
        self.index = 0

    def __iter__(self):
        return self

    def __next__(self):

        "*** YOUR CODE HERE ***"

        if self.index >= len(self.lst):
            raise StopIteration
        else:
            m = self.index
            self.index += 1 
            return self.dct.get(self.lst[m], self.lst[m])

Use OK to test your code:

python3 ok -q ListDictIter

Question 10: Pairs (generator)

Write a generator function pairs that takes a list and yields all the possible pairs of elements from that list.

def pairs(lst):
    """
    >>> type(pairs([3, 4, 5]))
    <class 'generator'>
    >>> for x, y in pairs([3, 4, 5]):
    ...     print(x, y)
    ...
    3 3
    3 4
    3 5
    4 3
    4 4
    4 5
    5 3
    5 4
    5 5
    """

    "*** YOUR CODE HERE ***"

    for i in lst:
        for j in lst:
            yield i, j

Use OK to test your code:

python3 ok -q pairs

Question 11: Pairs (iterator)

Now write an iterator that does the same thing. You are only allowed to use a linear amount of space - so computing a list of all of the possible pairs is not a valid answer. Notice how much harder it is - this is why generators are useful.

class PairsIterator:
    """
    >>> for x, y in PairsIterator([3, 4, 5]):
    ...     print(x, y)
    ...
    3 3
    3 4
    3 5
    4 3
    4 4
    4 5
    5 3
    5 4
    5 5
    """
    def __init__(self, lst):

        "*** YOUR CODE HERE ***"

        self.lst = lst
        self.i = 0
        self.j = 0

    def __next__(self):

        "*** YOUR CODE HERE ***"

        if self.i == len(self.lst):
            raise StopIteration
        result = (self.lst[self.i], self.lst[self.j])
        if self.j == len(self.lst) - 1:
            self.i += 1
            self.j = 0
        else:
            self.j += 1
        return result

    def __iter__(self):

        "*** YOUR CODE HERE ***"

        return self

Use OK to test your code:

python3 ok -q PairsIterator

Streams

Question 12: Cycle

Define a function cycle which takes in as input an ordinary Python list and returns a stream which just repeats that list over and over For example, cycle(['a', 'b', 'c']) is the stream containing elements ['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', ...]. If the input list is empty, output the empty stream; otherwise, the output stream should be infinite.

def cycle(list):
    """
    Returns a Stream that cycles through each entry of the list.
    >>> s = cycle(['a', 'b', 'c'])
    >>> s.first
    'a'
    >>> s.rest.first
    'b'
    >>> s.rest.rest.rest.rest.first
    'b'
    >>> t = cycle([])
    >>> t is Stream.empty
    True
    >>> isinstance(s, Stream)
    True
    >>> isinstance(s.rest.rest, Stream)
    True
    """

    "*** YOUR CODE HERE ***"

    if list == []:
    	return Stream.empty
    return Stream(list[0], lambda: cycle(list[1:] + list[:1]))

Use OK to test your code:

python3 ok -q cycle

Question 13: Run-Length Encoding

Run-length encoding is a very simple data compression technique, whereby runs of data are compressed and stored as a single value. A run is defined to be a contiguous sequence of the same number. For example, in the (finite) sequence

1, 1, 1, 1, 1, 6, 6, 6, 6, 2, 5, 5, 5

there are four runs: one each of 1, 6, 2, and 5. We can represent the same sequence as a sequence of tuples:

(5, 1), (4, 6), (1, 2), (3, 5)

Notice that the first element of each tuple is the number of times a particular number appears in a run, and the second element is the number in the run.

We will extend this idea to (possibly infinite) streams. Write a function called rle that takes in a stream of data, and returns a corresponding stream of tuples, which represents the run-length encoded version of the stream. It will also take in the maximum size of any given run (default 10) to prevent having to compress infinite runs.

def rle(s, max_run_length=10):
    """
    >>> example_stream = lst_to_stream([1, 1, 1, 2, 3, 3])
    >>> encoded_example = rle(example_stream)
    >>> stream_to_list(encoded_example, 3)
    [(3, 1), (1, 2), (2, 3)]
    >>> shorter_encoded_example = rle(example_stream, 2)
    >>> stream_to_list(shorter_encoded_example, 4)
    [(2, 1), (1, 1), (1, 2), (2, 3)]
    >>> ints = Stream(1, lambda: increment_stream(ints))
    >>> encoded_naturals = rle(ints)
    >>> stream_to_list(encoded_naturals, 3)
    [(1, 1), (1, 2), (1, 3)]
    >>> ones = Stream(1, lambda: ones)
    >>> encoded_ones = rle(ones, max_run_length=3)
    >>> stream_to_list(encoded_ones, 3)
    [(3, 1), (3, 1), (3, 1)]
    """

    "*** YOUR CODE HERE ***"

    if s == Stream.empty:
        return s
    first, s, count = s.first, s.rest, 1
    while s != Stream.empty and s.first == first and count < max_run_length:
        s, count = s.rest, count+1
    return Stream((count, first), lambda: rle(s, max_run_length))

Use OK to test your code:

python3 ok -q rle