# Homework 4

*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:

## Required Questions

# 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()
'Here is your candy.'
>>> 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()
'Here is your soda.'
"""
"*** YOUR CODE HERE ***"
```

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)
>>> m.ask('vend')
'You must learn to say please first.'
>>> m.ask('please vend')
'You must deposit $10 more.'
>>> m.ask('please deposit', 20)
'Current balance: $20'
>>> m.ask('now will you vend?')
'You must learn to say please first.'
>>> m.ask('please hand over a teaspoon')
'Thanks for asking, but I know not how to hand over a teaspoon.'
>>> m.ask('please vend')
'Here is your teaspoon and $10 change.'
>>> really_fussy = MissManners(m)
>>> really_fussy.ask('deposit', 10)
'You must learn to say please first.'
>>> really_fussy.ask('please deposit', 10)
'Thanks for asking, but I know not how to deposit.'
>>> really_fussy.ask('please please deposit', 10)
'Thanks for asking, but I know not how to please deposit.'
>>> really_fussy.ask('please ask', 'please deposit', 10)
'Current balance: $10'
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q MissManners`

# Linked Lists

### 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:
return Link.empty
p = result = Link(1)
for i in range(2, k + 1):
p.rest = Link(i)
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 = Link(1, Link(2, Link(3)))
>>> s
Link(1, Link(2, Link(3)))
>>> len(s)
3
>>> s[2]
3
>>> s = Link.empty
>>> len(s)
0
"""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
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)
def __len__(self):
""" Return the number of items in the linked list.
>>> s = Link(1, Link(2, Link(3)))
>>> len(s)
3
>>> s = Link.empty
>>> len(s)
0
>>> len(ints_list(100000)) # Check for iterative solution
100000
"""
"*** YOUR CODE HERE ***"
# The following method may be useful for implementation of the
# __getitem__ and insert methods.
def _get_link(self, i):
"""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).
>>> L = Link(1, Link(2, Link(3)))
>>> L._get_link(0)
Link(1, Link(2, Link(3)))
>>> L._get_link(1)
Link(2, Link(3))
>>> L._get_link(2)
Link(3)
>>> L._get_link(3)
()
>>> L._get_link(4)
Traceback (most recent call last):
...
IndexError: list index out of range
>>> L._get_link(-1)
Traceback (most recent call last):
...
IndexError: list index out of range
>>> (ints_list(100000))._get_link(1).first
2
"""
if i < 0:
raise IndexError("list index out of range")
"*** YOUR CODE HERE ***"
def __getitem__(self, i):
"""Returns the element found at index I.
>>> s = Link(1, Link(2, Link(3)))
>>> s[1]
2
>>> s[2]
3
>>> (ints_list(100000))[1] # Check for iterative solution
2
"""
if i < 0:
i = len(self) + i
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q Link`

### Question 5: add and __add__

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
def __add__(self, lst):
"""Returns the result of non-destructively appending LST to the
end of the sequence starting with self.
"""
"*** YOUR CODE HERE ***"
```

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 = Link(1, Link(2))
>>> s + Link.empty
Link(1, Link(2))
>>> s + Link(3, Link(4))
Link(1, Link(2, Link(3, Link(4))))
>>> s # Non-destructive
Link(1, Link(2))
>>> add(Link.empty, s)
Link(1, Link(2))
>>> s = ints_list(100000) + Link(100001) # Check for iterative solution
"""
if L0 is Link.empty:
"*** YOUR CODE HERE ***"
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).
"""
"*** YOUR CODE HERE ***"
```

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 = Link(1, Link(2, Link(3)))
>>> L.insert(1, 5)
Link(1, Link(5, Link(2, Link(3))))
>>> L
Link(1, Link(5, Link(2, Link(3))))
>>> L.insert(4, 6) # Insert off the end.
Link(1, Link(5, Link(2, Link(3, Link(6)))))
>>> L.insert(0, 7) # Insert at front
Link(7, Link(1, Link(5, Link(2, Link(3, Link(6))))))
>>> L # New element is "left of" L
Link(1, Link(5, Link(2, Link(3, Link(6)))))
>>> L.insert(6, 8)
IndexError
>>> insert((), 0, 3)
Link(3)
"""
if L is Link.empty:
"*** YOUR CODE HERE ***"
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
"""
"*** YOUR CODE HERE ***"
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)
...
Link(0, Link(1, Link(2)))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(5))))
Link(0, Link(6, Link(7, Link(8))))
Link(0, Link(6, Link(9)))
Link(0, Link(11, Link(12)))
>>> for path in long_paths(whole, 3):
... print(path)
...
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(5))))
Link(0, Link(6, Link(7, Link(8))))
>>> long_paths(whole, 4)
[]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q long_paths`