Due by 11:59pm on Monday, 3/6

## Instructions

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. Check that you have successfully submitted your code on okpy.org. See Lab 0 for more 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:

## 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
"""
``````

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
"""
``````

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"
``````

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

def size(w):
"""Select the size of a weight."""

def is_weight(w):
"""Whether w is a weight, not a mobile."""
``````

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
"""
``````

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]
"""
``````

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
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)

``````

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)
"""

def make_interval(self, low, high):
"""Returns a centered interval whose bounds are LOW and HIGH."""

def center(self):
"""The center of SELF.
>>> centered_interval(5, 1).center()
5.0
>>> centered_interval(interval(4, 6)).center()
5.0
"""

def tolerance(self):
"""The tolerance of SELF.
>>> centered_interval(5, 1).tolerance()
1.0
>>> centered_interval(interval(4, 6)).tolerance()
1.0
"""

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
"""

def __repr__(self):
"""A string represention of a Python expression that will produce SELF.
>>> centered_interval(5, 1)
centered_interval(5.0, 1.0)
"""
``````

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 'YOUR_EXPRESSION_HERE'
``````

Use OK to test your code:

``python3 ok -q make_anonymous_factorial``