# Homework 5 Solutions

## Solution Files

You can find the solutions in the hw05.py file.

# Vitamins

### Question 1: Countdown

Write both a generator function and an iterator (that is not a generator) that count down to 0.

```
def countdown(n):
"""
A generator that counts down from N to 0.
>>> for number in countdown(5):
... print(number)
...
5
4
3
2
1
0
>>> for number in countdown(2):
... print(number)
...
2
1
0
"""
while n >= 0:
yield n
n = n - 1
```

```
class Countdown:
"""
An iterator that counts down from N to 0.
>>> for number in Countdown(5):
... print(number)
...
5
4
3
2
1
0
>>> for number in Countdown(2):
... print(number)
...
2
1
0
"""
def __init__(self, cur):
self.cur = cur
def __next__(self):
if self.cur < 0:
raise StopIteration
self.cur -= 1
return self.cur + 1
def __iter__(self):
"""So that we can use this iterator as an iterable."""
return self
```

Use OK to test your code:

```
python3 ok -q countdown
python3 ok -q Countdown
```

# Required Questions

## Simplifying Expressions

### Question 2

In lecture, you saw that one use of trees is in representing expressions
(such as arithmetic expressions). So, for example, the expression
`2 * (3 + x)`

can be represented as the tree

That is, each operand is a child of the operator that applies to it.
In lecture, we looked at evaluating an expression that contains only numbers
and operators. For this problem, we'll work at *simplifying* an expression
that may contain variables without necessarily evaluating it. For example,
`2 * (x + 0) + y * 0`

could be simplified to `2 * x`

.

For this problem, the only operators are `*`

, `+`

, and `-`

(as strings), and
the labels of leaves
will either be numbers or strings containing variable names. Thus, our first
example would be represented with

` Tree('*', [Tree(2), Tree('+', [Tree(3), Tree('x')])])`

To help you, we've defined a few useful things that may come in handy:

```
# Alternative names of parts of an expression tree.
class Expr(Tree):
num_exprs = 0
def __init__(self, op, *branches):
"""For convenience, an Expr may be constructed as Expr(op, [c1, ...])
or Expr(op, c1, ...)."""
Expr.num_exprs += 1
if len(branches) == 1 and type(branches[0]) is list:
super().__init__(op, branches[0])
else:
super().__init__(op, list(branches))
# The following methods allow you to write E.oper, E[k] for the label
# and kth child of E, in keeping with the usual language for dealing with
# expressions. The class inherits from Tree, to == is also defined.
@property
def oper(self):
return self.label
def __getitem__(self, k):
return self.branches[k]
def __setitem__(self, k, v):
self.branches[k] = v
def arity(self):
"""The number of operands in this expression."""
return len(self.branches)
# Useful constants:
ZERO = Expr(0)
ONE = Expr(1)
def postfix_to_expr(postfix_expr):
"""Return an expression tree equivalent to POSTFIX_EXPR, a string
in postfix ("reverse Polish") notation. In postfix, one writes
E1 OP E2 (where E1 and E2 are expressions and OP is an operator) as
E1' E2' OP, where E1' and E2' are the postfix versions of E1 and E2. For
example, '2*(3+x)' is written '2 3 x + *' and '2*3+x' is `2 3 * x +'.
>>> print_tree(postfix_to_expr("2 3 x + *"))
*
2
+
3
x
"""
def expr_to_infix(expr):
"""A string containing a standard infix denotation of the expression
tree EXPR"""
```

Implement the function `simplify`

on these trees. Given an expression tree
`expr`

, this function returns a new expression tree, simplified from `expr`

by
applying the following rules:

- the expressions
`E * 0`

and`0 * E`

, where`E`

here can be any expression tree, are replaced by`0`

. - the expressions
`E * 1`

and`1 * E`

are replaced by`E`

. - the expressions
`E + 0`

,`0 + E`

, and`E - 0`

are replaced by`E`

. - the expression
`E - E`

(where the two operands are identical trees) is replaced by`0`

.

These simplifications may cause a cascade, as in `y * (x - (0 + x))`

which
simplifies to `y * (x - x)`

, then to `y * 0`

, and then to `0`

. In order for
that to work, you must be careful to simplify operands *before* simplifying the
whole expression. Your solution must be *nondestructive*.

```
def simplify(expr):
"""EXPR must be an expression tree involving the operators
'+', '*', and '-' in inner nodes; numbers and strings (standing for
variable names) in leaves. Returns an equivalent, simplified version
of EXPR.
>>> def simp(postfix_expr):
... v0 = postfix_to_expr(postfix_expr)
... v1 = postfix_to_expr(postfix_expr)
... r = expr_to_infix(simplify(v0))
... assert v0 == v1, "Input was modified by simplify"
... return r
>>> simp("x y + 0 *")
'0'
>>> simp("0 x y + *")
'0'
>>> simp("x y + 0 +")
'(x + y)'
>>> simp("0 x y + +")
'(x + y)'
>>> simp("x y + 1 *")
'(x + y)'
>>> simp("1 x y + *")
'(x + y)'
>>> simp("x y + x y + -")
'0'
>>> simp("x y y - + x - a b * *")
'0'
>>> simp("x y 3 * -")
'(x - (y * 3))'
>>> simp("x y 0 + 3 * -")
'(x - (y * 3))'
"""
if expr.is_leaf():
return expr
op = expr.oper
left = simplify(expr[0])
right = simplify(expr[1])
if op == '*':
if left == ZERO or right == ZERO:
return ZERO
elif left == ONE:
return right
elif right == ONE:
return left
elif op == '+':
if left == ZERO:
return right
elif right == ZERO:
return left
elif op == '-':
if right == ZERO:
return left
elif left == right:
return ZERO
return Expr(op, left, right)
```

Use OK to test your code:

`python3 ok -q simplify`

### Question 3

Implement the method `dsimplify`

, which is supposed to produce the same result as
`simplify`

, but *destructively* and without creating any new tree nodes.

```
def dsimplify(expr):
"""EXPR must be an expression tree involving the operators
'+', '*', and '-' in inner nodes; numbers and strings (standing for
variable names) in leaves. Returns an equivalent, simplified version
of EXPR.
>>> def simp(postfix_expr):
... expr = postfix_to_expr(postfix_expr)
... cnt0 = Expr.num_exprs
... v = expr_to_infix(dsimplify(expr))
... assert cnt0 == Expr.num_exprs, "New expression trees created."
... return v
>>> simp("x y + 0 *")
'0'
>>> simp("0 x y + *")
'0'
>>> simp("x y + 0 +")
'(x + y)'
>>> simp("0 x y + +")
'(x + y)'
>>> simp("x y + 1 *")
'(x + y)'
>>> simp("1 x y + *")
'(x + y)'
>>> simp("x y + x y + -")
'0'
>>> simp("x y y - + x - a b * *")
'0'
>>> simp("x y 3 * -")
'(x - (y * 3))'
>>> simp("x y 0 + 3 * -")
'(x - (y * 3))'
"""
if expr.is_leaf():
return expr
op = expr.oper
left = expr[0] = dsimplify(expr[0])
right = expr[1] = dsimplify(expr[1])
if op == '*':
if left == ZERO or right == ZERO:
return ZERO
elif left == ONE:
return right
elif right == ONE:
return left
elif op == '+':
if left == ZERO:
return right
elif right == ZERO:
return left
elif op == '-':
if right == ZERO:
return left
elif left == right:
return ZERO
return expr
```

Use OK to test your code:

`python3 ok -q dsimplify`

### Question 4: 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.'
"""
def __init__(self, product, price):
self.product = product
self.price = price
self.stock = 0
self.balance = 0
def restock(self, n):
self.stock += n
return 'Current {0} stock: {1}'.format(self.product, self.stock)
def deposit(self, n):
if self.stock == 0:
return 'Machine is out of stock. Here is your ${0}.'.format(n)
self.balance += n
return 'Current balance: ${0}'.format(self.balance)
def vend(self):
if self.stock == 0:
return 'Machine is out of stock.'
difference = self.price - self.balance
if difference > 0:
return 'You must deposit ${0} more.'.format(difference)
message = 'Here is your {0}'.format(self.product)
if difference != 0:
message += ' and ${0} change'.format(-difference)
self.balance = 0
self.stock -= 1
return message + '.'
```

Use OK to test your code:

`python3 ok -q VendingMachine`

### Question 5: Merge

Implement `merge(s0, s1)`

, which takes two iterables `s0`

and `s1`

whose
elements are ordered. `merge`

yields elements from `s0`

and `s1`

in sorted
order, eliminating repetition. You may assume `s0`

and `s1`

themselves do not
contain repeats, and that none of the elements of either are `None`

.
You may **not** assume that the iterables are finite; either may produce an infinite
stream of results.

You will probably find it helpful to use the two-argument version of the built-in
`next`

function: `next(s, v)`

is the same as `next(s)`

, except that instead of
raising `StopIteration`

when `s`

runs out of elements, it returns `v`

.

See the doctest for examples of behavior.

```
def merge(s0, s1):
"""Yield the elements of strictly increasing iterables s0 and s1, removing
repeats. Assume that s0 and s1 have no repeats. You can also assume that s0
and s1 represent infinite sequences.
>>> m = merge([0, 2, 4, 6, 8, 10, 12, 14], [0, 3, 6, 9, 12, 15])
>>> type(m)
<class 'generator'>
>>> list(m)
[0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
>>> def big(n):
... k = 0
... while True: yield k; k += n
>>> m = merge(big(2), big(3))
>>> [next(m) for _ in range(11)]
[0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
"""
i0, i1 = iter(s0), iter(s1)
e0, e1 = next(i0, None), next(i1, None)
while True:
if e0 is None and e1 is None:
return
elif e0 is None:
yield e1
e1 = next(i1, None)
elif e1 is None:
yield e0
e0 = next(i0, None)
else:
yield min(e0, e1)
if e0 < e1:
e0 = next(i0, None)
elif e1 < e0:
e1 = next(i1, None)
else:
e0, e1 = next(i0, None), next(i1, None)
```

Use OK to test your code:

`python3 ok -q merge`

# Extra Questions

Extra questions are not worth extra credit and are entirely optional. They are designed to challenge you to think creatively!

### Question 6: Zip generator

For this problem, we will be writing `zip_generator`

, which yields a
series of lists, each containing the nth items of each iterable.
It should stop when the smallest iterable runs out of elements.

```
def zip(*iterables):
"""
Takes in any number of iterables and zips them together.
Returns a generator that outputs a series of lists, each
containing the nth items of each iterable.
>>> z = zip([1, 2, 3], [4, 5, 6], [7, 8])
>>> for i in z:
... print(i)
...
[1, 4, 7]
[2, 5, 8]
"""
iterators = [iter(iterable) for iterable in iterables]
while True:
yield [next(iterator) for iterator in iterators]
```

Use OK to test your code:

`python3 ok -q zip`