# Homework 4 Solutions

## Solution Files

You can find the solutions in hw04.py.

## Vitamins

### Question 1: Counter

Define a function `make_counter`

that returns a `counter`

function, which takes
a string and returns the number of times that the function has been called on
that string.

```
def make_counter():
"""Return a counter function.
>>> c = make_counter()
>>> c('a')
1
>>> c('a')
2
>>> c('b')
1
>>> c('a')
3
>>> c2 = make_counter()
>>> c2('b')
1
>>> c2('b')
2
>>> c('b') + c2('b')
5
"""
totals = {}
def counter(key):
totals[key] = totals.get(key, 0) + 1
return totals[key]
return counter
```

Use OK to test your code:

`python3 ok -q make_counter`

### Question 2: Next Fibonacci

Write a function `make_fib`

that returns a function that returns the
next Fibonacci number each time it is called. (The Fibonacci sequence begins with 0
and then 1, after which each element is the sum of the preceding two.)
Use a `nonlocal`

statement!

```
def make_fib():
"""Returns a function that returns the next Fibonacci number
every time it is called.
>>> fib = make_fib()
>>> fib()
0
>>> fib()
1
>>> fib()
1
>>> fib()
2
>>> fib()
3
>>> fib2 = make_fib()
>>> fib() + sum([fib2() for _ in range(5)])
12
"""
cur, next = 0, 1
def fib():
nonlocal cur, next
result = cur
cur, next = next, cur + next
return result
return fib
```

Use OK to test your code:

`python3 ok -q make_fib`

## Required questions

You may choose to work with a partner on homework
questions, but you must submit your own solution. That is, *try to share ideas
rather than code.*

## Recursion

### Question 3: Towers of Hanoi

A classic puzzle called the Towers of Hanoi is a game that consists of three
rods, and a number of disks of different sizes which can slide onto any rod.
The puzzle starts with `n`

disks in a neat stack in ascending order of size on
a `start`

rod, the smallest at the top, forming a conical shape.

The objective of the puzzle is to move the entire stack to an `end`

rod,
obeying the following rules:

- Only one disk may be moved at a time.
- Each move consists of taking the top (smallest) disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
- No disk may be placed on top of a smaller disk.

Complete the definition of `move_stack`

, which prints out the steps required to
move `n`

disks from the `start`

rod to the `end`

rod without violating the
rules.

```
def print_move(origin, destination):
"""Print instructions to move a disk."""
print("Move the top disk from rod", origin, "to rod", destination)
def move_stack(n, start, end):
"""Print the moves required to move n disks on the start pole to the end
pole without violating the rules of Towers of Hanoi.
n -- number of disks
start -- a pole position, either 1, 2, or 3
end -- a pole position, either 1, 2, or 3
There are exactly three poles, and start and end must be different. Assume
that the start pole has at least n disks of increasing size, and the end
pole is either empty or has a top disk larger than the top n start disks.
>>> move_stack(1, 1, 3)
Move the top disk from rod 1 to rod 3
>>> move_stack(2, 1, 3)
Move the top disk from rod 1 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 3
>>> move_stack(3, 1, 3)
Move the top disk from rod 1 to rod 3
Move the top disk from rod 1 to rod 2
Move the top disk from rod 3 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 1
Move the top disk from rod 2 to rod 3
Move the top disk from rod 1 to rod 3
"""
assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
if n == 1:
print_move(start, end)
else:
other = 6 - start - end
move_stack(n-1, start, other)
print_move(start, end)
move_stack(n-1, other, end)
```

Use OK to test your code:

`python3 ok -q move_stack`

## Mobiles

**Acknowledgements.** This mobile example is based on
a classic problem from Structure and Interpretation of Computer Programs,
Section 2.2.2.

A mobile is a type of hanging sculpture. A binary mobile consists of two sides. Each side is a rod of a certain length, from which hangs either a weight or another mobile.

We will represent a binary mobile using the data abstractions below, which use
the `tree`

data abstraction for their representation.

- A
`mobile`

has a left side (index 0) and a right side (index 1). - A
`side`

has a length and a structure, which is either a`mobile`

or`weight`

. - A
`weight`

has a size, which is a positive number.

### Question 4: Weights

Implement the `weight`

data abstraction by completing the `weight`

constructor,
the `size`

selector, and the `is_weight`

predicate so that a weight is
represented using a tree. The `total_weight`

example is provided to demonstrate
use of the mobile, side, and weight abstractions.

```
def mobile(left, right):
"""Construct a mobile from a left side and a right side."""
return tree(None, [left, right])
def sides(m):
"""Select the sides of a mobile."""
return branches(m)
```

```
def side(length, mobile_or_weight):
"""Construct a side: a length of rod with a mobile or weight at the end."""
return tree(length, [mobile_or_weight])
def length(s):
"""Select the length of a side."""
return label(s)
def end(s):
"""Select the mobile or weight hanging at the end of a side."""
return branches(s)[0]
```

```
def weight(size):
"""Construct a weight of some size."""
assert size > 0
return tree(size)
def size(w):
"""Select the size of a weight."""
return label(w)
def is_weight(w):
"""Whether w is a weight, not a mobile."""
return is_leaf(w)
```

Use OK to test your code:

`python3 ok -q total_weight`

### Question 5: Balanced

Implement the `balanced`

function, which returns whether `m`

is a balanced
mobile. A mobile is said to be balanced if the torque applied by its left
side is equal to that applied by its right side (that is, if the length
of the left rod multiplied by the total weight hanging from that rod is equal
to the corresponding product for the right side) and if each of the submobiles
hanging off its sides is balanced.

```
def balanced(m):
"""Return whether m is balanced.
>>> t, u, v = examples()
>>> balanced(t)
True
>>> balanced(v)
True
>>> w = mobile(side(3, t), side(2, u))
>>> balanced(w)
False
>>> balanced(mobile(side(1, v), side(1, w)))
False
>>> balanced(mobile(side(1, w), side(1, v)))
False
"""
if is_weight(m):
return True
else:
left, right = sides(m)
left_s, right_s = end(left), end(right)
torque_left = length(left) * total_weight(left_s)
torque_right = length(right) * total_weight(right_s)
return balanced(left_s) and balanced(right_s) and torque_left == torque_right
```

Use OK to test your code:

`python3 ok -q balanced`

### Question 6: Totals

Implement the `with_totals`

function, which takes a `mobile`

and returns a tree
representation of that same mobile in which the root label of each mobile tree
is the total weight of the mobile it represents (instead of `None`

).

*Note*: This function needs to assume that a mobile is represented as a tree.

```
def with_totals(m):
"""Return a mobile with total weights stored as the label of each mobile.
>>> t, _, v = examples()
>>> label(with_totals(t))
3
>>> print(label(t)) # t should not change
None
>>> label(with_totals(v))
9
>>> [label(end(s)) for s in sides(with_totals(v))]
[3, 6]
>>> [label(end(s)) for s in sides(v)] # v should not change
[None, None]
"""
if is_weight(m):
return m
ends = [with_totals(end(s)) for s in sides(m)]
total = sum([label(s) for s in ends])
return tree(total, [side(length(s), t) for s, t in zip(sides(m), ends)])
```

Use OK to test your code:

`python3 ok -q with_totals`

### Question 7: 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:

```
class interval:
"""A range of floating-point values.
>>> a = interval(1, 4)
>>> a
interval(1, 4)
>>> print(a)
(1, 4)
>>> a.low()
1
>>> a.high()
4
>>> a.width()
3
>>> 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.0, 2.0)
>>> a / b
ValueError
>>> -a
interval(-4, -1)
>>> c = interval(2, 8)
>>> c + c
interval(4, 16)
>>> c - c
interval(-6, 6)
>>> c / c
interval(0.25, 4.0)
"""
# In all methods below, use the following method to create new intervals.
# For example, if a method must return interval(x, y), have it
# return self.makeinterval(x, y) instead.
def make_interval(self, low, high):
"""Returns an interval of the same type as SELF with bounds LOW
and HIGH. Thus, if SELF is an interval, returns interval(LOW, HIGH)."""
return interval(low, high)
def __init__(self, low, high):
if low < high:
self._low, self._high = low, high
else:
self._low, self._high = high, low
def low(self):
return self._low
def high(self):
return self._high
def width(self):
return self._high - self._low
def __add__(self, x):
return self.make_interval(self._low + x._low, self._high + x._high)
def __sub__(self, x):
return self.make_interval(self._low - x._high, self._high - x._low)
def __mul__(self, x):
a = self._low * x._low
b = self._high * x._high
c = self._low * x._high
d = self._high * x._low
return self.make_interval(min(a, b, c, d), max(a, b, c, d))
def __neg__(self):
return self.make_interval(-self._low, -self._high)
def __truediv__(self, x):
if x._low <= 0 <= x._high:
raise ValueError("division by interval containing 0")
return self * self.make_interval(1.0 / x._low, 1.0 / x._high)
def __repr__(self):
return "interval({}, {})".format(self._low, self._high)
def __str__(self):
return "({}, {})".format(self._low, self._high)
```

Implement an `interval`

class that has this behavior.

Use OK to test your code:

`python3 ok -q interval`

### Question 8: Centered Interval

After debugging her program, Alyssa shows it to a potential user, who
complains that her program solves the wrong problem. He wants a program
that can deal with numbers represented as a center value and an
additive tolerance; for example, he wants to work with intervals such
as `3.5 +/- 0.15`

rather than `3.35`

to `3.65`

. Alyssa returns to her
desk and fixes this problem by supplying a second interval class called
`centered_interval`

that inherits from `interval`

, has a different
constructor, different string representations, and two extra selectors:

```
class centered_interval(interval):
def __init__(self, c, tol = None):
"""Initialize SELF to C +- TOL. TOL is None, then C is assumed to be
an interval, and SELF will be set to have the same bounds.
>>> a = centered_interval(1, 2)
>>> a.low()
-1
>>> a.high()
3
>>> a.width()
4
>>> b = centered_interval(3, 1)
>>> a + b
centered_interval(4.0, 3.0)
>>> a * b
centered_interval(4.0, 8.0)
>>> -a
centered_interval(-1.0, 2.0)
"""
if tol is None:
super().__init__(c.low(), c.high())
else:
super().__init__(c - tol, c + tol)
def make_interval(self, low, high):
"""Returns a centered interval whose bounds are LOW and HIGH."""
return centered_interval(interval(low, high))
def center(self):
"""The center of SELF.
>>> centered_interval(5, 1).center()
5.0
>>> centered_interval(interval(4, 6)).center()
5.0
"""
return (self.low() + self.high()) / 2
def tolerance(self):
"""The tolerance of SELF.
>>> centered_interval(5, 1).tolerance()
1.0
>>> centered_interval(interval(4, 6)).tolerance()
1.0
"""
return (self.high() - self.low()) / 2
def __str__(self):
"""A string representation of SELF as center +/- tolerance.
>>> print(centered_interval(5, 1))
5.0 +/- 1.0
>>> print(centered_interval(interval(4, 6)))
5.0 +/- 1.0
"""
return "{} +/- {}".format(self.center(), self.tolerance())
def __repr__(self):
"""A string represention of a Python expression that will produce SELF.
>>> centered_interval(5, 1)
centered_interval(5.0, 1.0)
"""
return "centered_interval({}, {})".format(self.center(), self.tolerance())
```

She does *not* override any of the `__...__`

methods of `interval`

other than `__str__`

,
`__repr__`

, and `__init__`

, so there is a slight problem, as these methods
were defined to construct `intervals`

rather than
`centered_intervals`

. You'll have to figure out how to use the method
`make_interval`

so that this all works properly.

Use OK to test your code:

```
python3 ok -q centered_interval.__init__
python3 ok -q centered_interval.center
python3 ok -q centered_interval.tolerance
python3 ok -q centered_interval.__str__
python3 ok -q centered_interval.__repr__
```

## Extra questions

Extra questions are not worth extra credit and are entirely optional.

### Question 9: Anonymous factorial

The recursive factorial function can be written as a single expression by using a conditional expression.

```
>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
>>> fact(5)
120
```

However, this implementation relies on the fact (no pun intended) that
`fact`

has a name, to which we refer in the body of `fact`

. To write a
recursive function, we have always given it a name using a `def`

or
assignment statement so that we can refer to the function within its
own body. In this question, your job is to define fact recursively
without giving it a name!

Write an expression that computes `n`

factorial using only call
expressions, conditional expressions, and lambda expressions (no
assignment or def statements). *Note in particular that you are not
allowed to use make_anonymous_factorial in your return expression.*
The

`sub`

and `mul`

functions from the `operator`

module are the only
built-in functions required to solve this problem:```
from operator import sub, mul
def make_anonymous_factorial():
"""Return the value of an expression that computes factorial.
>>> make_anonymous_factorial()(5)
120
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'make_anonymous_factorial', ['Assign', 'AugAssign', 'FunctionDef', 'Recursion'])
True
"""
return (lambda f: lambda k: f(f, k))(lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1))))
```

Use OK to test your code:

`python3 ok -q make_anonymous_factorial`