Lab 10: Interfaces

Due at 11:59pm on 07/23/2015.

Starter Files

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

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded.

To receive credit for this lab, you must complete Questions 1, 2, 3, 4, 5, and 6 in lab10.py and submit through OK.
Questions 7 is extra practice. It can be found in the lab10_extra.py file. It is recommended that you complete this problem on your own time.

Interfaces

In computer science, an interface is a shared set of attributes, along with a specification of the attributes' behavior. For example, an interface for vehicles might consist of the following methods:

def drive(self): Drives the vehicle if it has stopped.
def stop(self): Stops the vehicle if it is driving.

Data types can implement the same interface in different ways. For example, a Car class and a Train can both implement the interface described above, but the Car probably has a different mechanism for drive than the Train.

The power of interfaces is that other programs don't have to know how each data type implements the interface — only that they have implemented the interface. The following travel function can work with both Cars and Trains:

def travel(vehicle):
    while not at_destination():
        vehicle.drive()
    vehicle.stop()

QueueVendingMachines

QueueVendingMachine is an interface for vending machines that have a queue of items. Users have no choice in what they buy, they simply get the next item in the queue. This interface contains the methods dispense and collect_money. See the doctests below for details.

def dispense():
    """
    Returns the next item queued in the vending machine, or None if there is no item left.
    """

def collect_money(item):
    """
    Collects money earned from item and returns total money earned by the machine.
    """

Here is one class that implements QueueVendingMachine called SnacksVendor. It dispenses snacks with a set price.

class SnacksVendor(object):

    def __init__(self, snacks, prices):
        """ snacks is a list of all the snacks (strings) for sale, and can 
            contain multiple instances of the same snack type. prices is a 
            dictionary that maps each snack type (string) to its price (number)
            .
        """
        self.inventory = snacks
        self.prices = prices
        self.revenue = 0

    def dispense(self):
        """ Removes and dispenses the last snack from the inventory.

        >>> vendor = SnacksVendor(['candy', 'chips', 'chips'], 
        ...                       {'candy': 1, 'chips': 3})
        >>> vendor.dispense()
        'chips'
        >>> vendor.dispense()
        'chips'     
        >>> vendor.dispense()
        'candy'     
        >>> no_snack_left = vendor.dispense()
        >>> no_snack_left is None
        True
        """
        if self.inventory:
            return self.inventory.pop()

    def collect_money(self, item):
        """ Adds the price of snack to total revenue and returns the total 
            revenue.

        >>> vendor = SnacksVendor(['candy', 'chips'], {'candy': 1, 'chips': 3})
        >>> snack = vendor.dispense()
        >>> vendor.collect_money(snack)
        3
        >>> vendor.collect_money(vendor.dispense())
        4
        """
        self.revenue += self.prices[item]
        return self.revenue

Question 1: MixedJuiceVendor

Now fill in another class, MixedJuiceVendor, that also implements QueueVendingMachine. MixedJuiceVendor keeps an instance attribute self.fruits, a list of fruits, and creates and dispenses a drink made with the first two fruits in the inventory. It also keeps an inventory of self.cups, and each drink takes one cup to produce.

Write the dispense and collect_money methods. MixedJuiceVendor is a waste-free vending machine, so do not perform any operations that create new lists of fruits (i.e. use mutation!). See the doctests for details.

class MixedJuiceVendor(object):
    """ A QueueVendingMachine that vends mixed juices. 

    >>> vendor = MixedJuiceVendor(['kiwi', 'mango', 'apple', 'guava'], 3)
    >>> juice = vendor.dispense()
    >>> juice
    'kiwi-mango'
    >>> vendor.collect_money(juice)
    9
    >>> juice = vendor.dispense()
    >>> juice
    'apple-guava'
    >>> vendor.collect_money(juice)
    19
    >>> vendor.cups
    1
    >>> juice = vendor.dispense() # no fruits left!
    >>> print(juice)
    None

    >>> vendor2 = MixedJuiceVendor(['guava', 'mango'], 0)
    >>> juice = vendor2.dispense() # no cups!
    >>> print(juice)
    None

    >>> vendor3 = MixedJuiceVendor(['lemon'], 1)
    >>> juice = vendor3.dispense() # only one fruit!
    >>> print(juice)
    None
    """

    def __init__(self, fruits, cups):
        """ fruits is a list of fruits in the inventory. cups is the number of 
            cups left to put juice in. 
        """
        self.fruits = fruits
        self.cups = cups
        self.revenue = 0

    def dispense(self):
        """ Dispenses a mixed juice combining the first two fruits in the 
            fruit inventory. Juices can only be created if there are at least 
            two fruits left and there is at least one cup left. 
        """
        "*** YOUR CODE HERE ***"
        if len(self.fruits) >= 2 and self.cups:
            self.cups -= 1
            return self.fruits.pop(0) + "-" + self.fruits.pop(0)
    def collect_money(self, item):
        """ Each juice is priced based on how many letters make up its two 
            fruits.
        """
        "*** YOUR CODE HERE ***"
        self.revenue = self.revenue + len(item) - 1
        return self.revenue

Hint: use the pop(i) method on a list to remove and retrieve the element at index i.
>>> lst = [1, 2, 3, 4]
>>> lst.pop()
4
>>> lst.pop(1)
2
>>> lst
[1, 3]

Use OK to test your code:

python3 ok -q MixedJuiceVendor

Question 2: Total Revenue

A budding entrepreneur finds out about QueueVendingMachines, and, predicting that they're the next big thing in our increasingly automated society, wants to invest in them. However, he simply wants to find the one machine that generates the most revenue, and buy 1000 of them. He hires you to write a function total_revenue that takes in a QueueVendingMachine and return the total revenue it generates if it sells all its products.

def total_revenue(qvm):
    """ Returns total possible revenue generated from qvm.

    >>> juices = MixedJuiceVendor(['orange', 'mango', 'banana', 'guava'], 10)
    >>> total_revenue(juices)
    22
    >>> snacks = SnacksVendor(['chips', 'ramen', 'pretzels', 'chips'], 
    ...                       {'chips': 4, 'pretzels': 7, 'ramen': 10})
    >>> total_revenue(snacks)
    25
    """
    "*** YOUR CODE HERE ***"
    total = 0
    item = qvm.dispense()
    while item:
        total = qvm.collect_money(item)
        item = qvm.dispense()
    return total

Use OK to test your code:

python3 ok -q total_revenue

Question 3: Max Revenue

Now write a function max_revenue that takes in a list of QueueVendingMachines and returns the one with the highest total possible revenue. Use the function total_revenue that you just wrote.

def max_revenue(lst_of_qvm):
    """ Returns the QueueVendingMachine from lst_of_qvm that has the greatest 
        total possible revenue, or the first in the list if their total 
        revenues are equal.

    >>> juices = MixedJuiceVendor(['orange', 'mango', 'banana', 'guava'], 10)
    >>> snacks = SnacksVendor(['chips', 'ramen', 'pretzels', 'chips'], 
    ...     {'chips': 4, 'pretzels': 7, 'ramen': 10})
    >>> best = max_revenue([juices, snacks])
    >>> best is snacks
    True
    """
    "*** YOUR CODE HERE ***"
    best, max_rev = None, -1
    for qvm in lst_of_qvm:
        total_rev = total_revenue(qvm)
        if total_rev > max_rev:
            max_rev, best = total_rev, qvm
    return best

#Alternate solution
def max_revenue(lst_of_qvm):
    return max(lst_of_qvm, key=lambda qvm : total_revenue(qvm))

Use OK to test your code:

python3 ok -q max_revenue

Magic Methods

Python defines many interfaces that can interact with built-in operators. These interfaces contain magic methods, which can be implemented by user-defined classes. Magic methods are surround by two underscores.

The interface for arithmetic includes the following methods:

def __add__(self, other): Allows objects to do self + other.
def __sub__(self, other): Allows objects to do self - other.
def __mul__(self, other): Allows objects to do self * other.

In addition, the sequence interface is defined by the following magic methods:

def __len__(self): Allows objects to do len(self).
def __getitem__(self, index): Allows objects to do self[i].

Two built-in data types that implement the sequence interface are lists and dictionaries.

In lecture, you saw the sequence interface being implemented for a user-defined data type, Linked Lists.

class Link:
    """A linked list.

    >>> s = Link(1, Link(2, Link(3, Link(4))))
    >>> len(s)
    4
    >>> s[2]
    3
    >>> s
    Link(1, Link(2, Link(3, Link(4))))
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __len__(self):
        return 1 + len(self.rest)

    def __getitem__(self, i):
        if i == 0:
            return self.first
        else:
            return self.rest[i-1]

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_str = ', ' + repr(self.rest)
        else:
            rest_str = ''
        return 'Link({0}{1})'.format(repr(self.first), rest_str)

Question 4: is_palindrome

Write the function is_palindrome such that it works for any data type that implements the sequence interface.

def is_palindrome(seq):
    """ Returns True if the sequence is a palindrome. A palindrome is a sequence 
    that reads the same forwards as backwards
    >>> is_palindrome(Link("l", Link("i", Link("n", Link("k")))))
    False
    >>> is_palindrome(["l", "i", "n", "k"])
    False
    >>> is_palindrome("link")
    False
    >>> is_palindrome(Link.empty)
    True
    >>> is_palindrome([])
    True
    >>> is_palindrome("")
    True
    >>> is_palindrome(Link("a", Link("v", Link("a"))))
    True
    >>> is_palindrome(["a", "v", "a"])
    True
    >>> is_palindrome("ava")
    True
    """
    "*** YOUR CODE HERE ***"
    for i in range(len(seq)//2):
        if seq[i] != seq[len(seq) - 1 - i]:
          return False
    return True

Use OK to test your code:

python3 ok -q is_palindrome

Question 5: mul

Let's implement __mul__ for our Link class, which allows us to scalar multiply a Linked List. Look to the doctest for its behavior.

class Link:
    # Link implementation hidden for space

    def __mul__(self, c):
        """ Scalar multiplies self by c. Raise AssertionError if c is not a 
            number.
        >>> (Link.empty * 3) is Link.empty
        True
        >>> a = Link(1, Link(5))
        >>> b = a * 1
        >>> b
        Link(1, Link(5))
        >>> b is not a
        True
        >>> b = a * 3
        >>> b
        Link(1, Link(5, Link(1, Link(5, Link(1, Link(5))))))
        >>> a is not b
        True
        >>> (a * 0) is Link.empty
        True
        >>> a * Link(3)
        AssertionError
        """
        "*** YOUR CODE HERE ***"
        assert type(c) is int
        def helper(lst, count):
            if count == 0:
                return Link.empty
            if lst is Link.empty:
                return helper(self, count - 1)
            return Link(lst.first, helper(lst.rest, count))
        return helper(self, c)

    # Alternate Solution
    def __mul__(self, c):
        assert type(c) == int
        if c == 0:
            return Link.empty

        rest = self * (c - 1)
        new, self = Link(self.first), self.rest
        end = new
        while self is not Link.empty:
            end.rest, self = Link(self.first), self.rest
            end = end.rest
        end.rest = rest
        return new

Use OK to test your code:

python3 ok -q mul

Exceptions

You've learned how to raise exceptions, but it's also important to catch exceptions when necessary. Instead of letting the exception propogate back to the user, we can catch it using a try...except block and allow the program to continue.

try:
    <try suite>
except Exception as e:
    <except suite>

We put the code that might raise an exception in the <try suite>. If an exception of type Exception is raised, then the program will skip the rest of that suite and execute the <except suite>. Generally, we want to be specify exactly which Exception we want to handle, such as TypeError or ZeroDivisionError.

Notice that we can catch the exception as e. This assigns the exception object to the variable e. This can be helpful when we want to use information about the exception that was raised.

>>> try:
...     1/0
...     raise ValueError     # this line is not executed!
... except ZeroDivisionError as e:
...     print('The try block raised a ' + str(e) + ' error.')
The try block raised a division by zero error.

Question 6: No KeyErrors Allowed

If we try to look up a key that does not exist in a dictionary, then Python will raise a KeyError. Write the function avoid_keyerror which returns returns the value mapped to key in the dictionary. If key does not exist, print 'Avoid Exception' and map key to the string 'no value'.

def avoid_keyerror(dictionary, key):
    """ Returns the value associated with key in dictionary. If key 
    does not exist in the dictionary, print out 'Avoid Exception' and
    map it to the string 'no value'.

    >>> d = {1: 'one', 3: 'three', 5: 'five'}
    >>> avoid_keyerror(d, 3)
    'three'
    >>> avoid_keyerror(d, 4)
    Avoid Exception
    >>> d[4]
    'no value'
    """
    "*** YOUR CODE HERE ***"
    try:
        return dictionary[key]
    except KeyError as e:
        print("Avoid Exception")
        dictionary[key] = 'no value'

Use OK to test your code:

python3 ok -q avoid_keyerror

Extra Questions

The following question is for extra practice — it can be found in the the lab10_extra.py file. It is recommended that you complete this problem on your own time.

Question 7: delitem

Implement __delitem__ for our Link class, which allows us to delete an index from a Link using this syntax: del lst[i].

class Link:
    # Link implementation hidden for space

    def __delitem__(self, index):
        """ Deletes value at given index from the Link. Raise a ValueError if the 
        length of the Linked List is 1. Raise an IndexError if the index is out
        of bounds.

        >>> s = Link(2, Link(4, Link(6, Link(8))))
        >>> del s[3]
        >>> s
        Link(2, Link(4, Link(6)))        
        >>> del s[4]
        Traceback (most recent call last):
             ...
        IndexError
        >>> del s[0]
        >>> s
        Link(4, Link(6))
        >>> del s[0]
        >>> s
        Link(6)
        >>> del s[0]
        Traceback (most recent call last):
             ...
        ValueError
        """
        "*** YOUR CODE HERE ***"
        if len(self) == 1:
            raise ValueError
        if len(self) <= index:
            raise IndexError
        if index == 0:
            self.first, self.rest= self.rest.first, self.rest.rest
        elif index == 1:
            self.rest = self.rest.rest
        else:
            del self.rest[index - 1]

Use OK to test your code:

python3 ok -q __delitem__

Starter Files

Submission

Interfaces

QueueVendingMachines

Question 1: MixedJuiceVendor

Question 2: Total Revenue

Question 3: Max Revenue

Magic Methods

Question 4: is_palindrome

Question 5: __mul__

Exceptions

Question 6: No KeyErrors Allowed

Extra Questions

Question 7: __delitem__

Question 5: mul

Question 7: delitem