Due by 11:59pm on Wednesday, 3/9

## Instructions

Download hw04.zip. Inside the archive, you will find a file called hw04.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:

# Objects

### Question 1: Vending Machine

Create a class called `VendingMachine` that represents a vending machine for some product. A `VendingMachine` object returns strings describing its interactions. See the doctest below for examples:

``````class VendingMachine:
"""A vending machine that vends some product for some price.

>>> v = VendingMachine('candy', 10)
>>> v.vend()
'Machine is out of stock.'
>>> v.restock(2)
'Current candy stock: 2'
>>> v.vend()
'You must deposit \$10 more.'
>>> v.deposit(7)
'Current balance: \$7'
>>> v.vend()
'You must deposit \$3 more.'
>>> v.deposit(5)
'Current balance: \$12'
>>> v.vend()
'Here is your candy and \$2 change.'
>>> v.deposit(10)
'Current balance: \$10'
>>> v.vend()
>>> v.deposit(15)
'Machine is out of stock. Here is your \$15.'

>>> w = VendingMachine('soda', 2)
>>> w.restock(3)
'Current soda stock: 3'
>>> w.deposit(2)
'Current balance: \$2'
>>> w.vend()
"""
``````

Use OK to test your code:

``python3 ok -q VendingMachine``

### Question 2: Intervals

Acknowledgements. This interval arithmetic example is adapted from a classic problem from Structure and Interpretation of Computer Programs, Section 2.1.4.

Introduction. Alyssa P. Hacker is designing a system to help people solve engineering problems. One feature she wants to provide in her system is the ability to manipulate inexact quantities (such as measured parameters of physical devices) with known precision, so that when computations are done with such approximate quantities the results will be numbers of known precision.

Alyssa's idea is to implement interval arithmetic as a set of arithmetic operations for combining "intervals" (objects that represent the range of possible values of an inexact quantity). The result of adding, subracting, multiplying, or dividing two intervals is itself an interval, representing the range of possible results when the operation is applied to one value selected from the first of the two interval operands and one value selected from the second.

Alyssa postulates the existence of an abstract object called an "interval" that has two endpoints: a lower bound and an upper bound. She intends to allow clients to construct intervals from their endpoints, print them, and perform arithmetic on them, as indicated in the following use cases:

``````>>> a = interval(1, 4)
>>> a
interval(1, 4)
>>> print(a)
(1, 4)
>>> a.low
1
>>> a.high
4
>>> a.low = 3    # .low and .high are read-only
Traceback (most recent call last):
...
AttributeError: can't set attribute
>>> a.width
3
>>> a.width = 4
Traceback (most recent call last):
...
AttributeError: can't set attribute
>>> b = interval(2, -2)  # Order doesn't matter
>>> print(b, b.low, b.high)
(-2, 2) -2 2
>>> a + b
interval(-1, 6)
>>> a - b
interval(-1, 6)
>>> a * b
interval(-8, 8)
>>> b / a
interval(-2, 2)
>>> a / b
Traceback (most recent call last):
...
ValueError: division by interval containing 0
>>> -a
interval(-4, -1)``````

Implement an `interval` class that has this behavior. In order to get attributes like `.low` to work, you will need to use properties, as described in lecture.

Use OK to test your code:

``python3 ok -q interval``

### Question 3: Miss Manners

Create a class called `MissManners` that promotes politeness among our objects. A `MissManners` object takes another object on construction. It has one method, called `ask`. It responds by calling methods on the object it contains, but only if the caller said please first.

Hint: Your implementation will need to use the `*args` notation that allows functions to take a flexible number of arguments.

Hint: Use `getattr` and `hasattr` to manipulate attributes using strings.

``````class MissManners:
"""A container class that only forward messages that say please.

>>> v = VendingMachine('teaspoon', 10)
>>> v.restock(2)
'Current teaspoon stock: 2'

>>> m = MissManners(v)
'You must learn to say please first.'
'You must deposit \$10 more.'
'Current balance: \$20'
'You must learn to say please first.'
'Thanks for asking, but I know not how to hand over a teaspoon.'
'Here is your teaspoon and \$10 change.'

>>> really_fussy = MissManners(m)
'You must learn to say please first.'
'Thanks for asking, but I know not how to deposit.'
'Current balance: \$10'
"""
``````

Use OK to test your code:

``python3 ok -q MissManners``

### Question 4: Iterative Linked List

The `Link` class is supposed to provide a linked-list type, as shown in lecture. In contrast to the lecture version, do not use recursion to implement it. In doctests, we've used the `ints_list` method to supply very long lists that will cause a recursive function to hit too large a stack depth.

``````# ints_list is used to test that a method does not use recursion by making
# sure that a very long list does not cause a large recursion depth.
def ints_list(k):
"""A linked list containing the numbers 1 to K."""
if k < 1:
for i in range(2, k + 1):
p = p.rest
return result``````

Implement the basic methods `__len__` and `__getitem__` and `_get_link`. The method `_get_link` is intended for internal use. Once you implement it, `__getitem__` should be very short, and it is useful for later methods as well.

``````class Link:
"""
>>> s
>>> len(s)
3
>>> s[2]
3
>>> len(s)
0
"""
empty = ()

def __init__(self, first, rest=empty):
self.first = first
self.rest = rest

def __repr__(self):
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''

def __len__(self):
""" Return the number of items in the linked list.

>>> len(s)
3
>>> len(s)
0
>>> len(ints_list(100000)) # Check for iterative solution
100000
"""

# The following method may be useful for implementation of the
# __getitem__ and insert methods.
"""An internal utility method that returns the Ith Link after
self (I == 0 returns self, I == 1 returns self.rest, etc.).  Returns
empty if I is len(self).  Raises IndexError unless 0 <= I <= len(self).
()
Traceback (most recent call last):
...
IndexError: list index out of range
Traceback (most recent call last):
...
IndexError: list index out of range
2
"""
if i < 0:
raise IndexError("list index out of range")

def __getitem__(self, i):
"""Returns the element found at index I.

>>> s[1]
2
>>> s[2]
3
>>> (ints_list(100000))[1]  # Check for iterative solution
2
"""
if i < 0:
i = len(self) + i
``````

Use OK to test your code:

``python3 ok -q Link``

Implement the special "underscore" method `__add__` for our `Link` class, which allows us to use the built-in `+` operator on two `Link`s.

``````class Link:
# previous stuff here

"""Returns the result of non-destructively appending LST to the
end of the sequence starting with self.
"""
``````

Fill in the `add` function as well.

``````def add(L0, L1):
"""Return the list formed by non-destructively appending the items in L1
to the end of those in L0.

>>> s   # Non-destructive
>>> s = ints_list(100000) + Link(100001)  # Check for iterative solution
"""
else:
return L0 + L1``````

Use OK to test your code:

``python3 ok -q add``

### Question 6: Insert

Fill in the `insert` method of `Link` to destructively insert into a linked list at a given index.

``````class Link:
# previous stuff here

def insert(self, k, val):
"""Destructively insert VAL into the list headed by SELF at index
K, moving the previous item K and later items right.  Returns the
resulting linked list.  Assumes 0 <= K <= len(self).
"""
``````

Also complete the `insert` function.

``````def insert(L, k, val):
"""Destructively insert VAL into L at position K, returning the
resulting list.  Assumes 0 <= K <= len(L).

>>> L.insert(1, 5)
>>> L
>>> L.insert(4, 6)  # Insert off the end.
>>> L.insert(0, 7)  # Insert at front
>>> L  # New element is "left of" L
>>> L.insert(6, 8)
IndexError
>>> insert((), 0, 3)
"""
else:
return L.insert(k, val)``````

Use OK to test your code:

``python3 ok -q insert``

# Trees

Just like Linked Lists, we can also represent Trees as objects.

``````class Tree:
def __init__(self, label, children=()):
self.label = label
for branch in children:
assert isinstance(branch, Tree)
self.children = list(children)

def __repr__(self):
if self.children:
children_str = ', ' + repr(self.children)
else:
children_str = ''
return 'Tree({0}{1})'.format(self.label, children_str)

def is_leaf(self):
return not self.children``````

### Question 7: Same Shape

Write a function `same_shape` that returns `True` if two `Tree`s have the same shape. Two trees have the same shape iff they have the same number of children and each pair of corresponding children have the same shape.

``````def same_shape(t1, t2):
"""Returns whether two Trees t1, t2 have the same shape. Two trees have the
same shape iff they have the same number of children and each pair
of corresponding children have the same shape.

>>> t, s = Tree(1), Tree(3)
>>> same_shape(t, t)
True
>>> same_shape(t, s)
True
>>> t = Tree(1, [Tree(2), Tree(3)])
>>> same_shape(t, s)
False
>>> s = Tree(4, [Tree(3, [Tree(2, [Tree(1)])])])
>>> same_shape(t, s)
False
"""

class Tree:
def __init__(self, label, children=()):
self.label = label
for branch in children:
assert isinstance(branch, Tree)
self.children = list(children)

def __repr__(self):
if self.children:
children_str = ', ' + repr(self.children)
else:
children_str = ''
return 'Tree({0}{1})'.format(self.label, children_str)

def is_leaf(self):
return not self.children``````

Use OK to test your code:

``python3 ok -q same_shape``

### Question 8: Long Paths

Implement `long_paths`, which returns a list of all paths in a tree with length at least `n`. A path in a tree is a linked list of node values that starts with the root and ends at a leaf. Each subsequent element must be from a child of the previous value's node. The length of a path is the number of edges in the path (i.e. one less than the number of nodes in the path). Paths are listed in order from left to right.

``````def long_paths(tree, n):
"""Return a list all paths in tree with length at least n.

>>> t = Tree(3, [Tree(4), Tree(4), Tree(5)])
>>> left = Tree(1, [Tree(2), t])
>>> mid = Tree(6, [Tree(7, [Tree(8)]), Tree(9)])
>>> right = Tree(11, [Tree(12)])
>>> whole = Tree(0, [left, Tree(13), mid, right])
>>> for path in long_paths(whole, 2):
...     print(path)
...
>>> for path in long_paths(whole, 3):
...     print(path)
...
``python3 ok -q long_paths``