# 61A Homework 7

Due by 5pm on Friday, 10/19

Submission. See the online submission instructions. We have provided a starter file for the questions below.

Readings. Sections 2.7 and 3.2 of the online lecture notes.

Q1. Write a data-directed apply function that computes the area or perimeter of either a square or a rectangle. Use a dictionary to store the implementations of each function for each type:

```class Square(object):
def __init__(self, side):
self.side = side

class Rect(object):
def __init__(self, width, height):
self.width = width
self.height = height

def type_tag(s):
return type_tag.tags[type(s)]

type_tag.tags = {Square: 's', Rect: 'r'}

def apply(operator_name, shape):
"""Apply operator to shape.

>>> apply('area', Square(10))
100
>>> apply('perimeter', Square(5))
20
>>> apply('area', Rect(5, 10))
50
>>> apply('perimeter', Rect(2, 4))
12
"""
```

Q2. A mathematical function G on positive integers is defined by two cases:

G(n) = n,                                       if n <= 3

G(n) = G(n - 1) + 2 * G(n - 2) + 3 * G(n - 3),  if n > 3

Write a recursive function g that computes G(n). Then, write an iterative function g_iter that computes G(n):

```def g(n):
"""Return the value of G(n), computed recursively.

>>> g(1)
1
>>> g(2)
2
>>> g(3)
3
>>> g(4)
10
>>> g(5)
22
"""

def g_iter(n):
"""Return the value of G(n), computed iteratively.
>>> g_iter(1)
1
>>> g_iter(2)
2
>>> g_iter(3)
3
>>> g_iter(4)
10
>>> g_iter(5)
22
"""
```

Q3. The number of partitions of a positive integer n is the number of ways in which n can be expressed as the sum of positive integers in increasing order. For example, the number 5 has 7 partitions.

5 = 5

5 = 1 + 4

5 = 2 + 3

5 = 1 + 1 + 3

5 = 1 + 2 + 2

5 = 1 + 1 + 1 + 2

5 = 1 + 1 + 1 + 1 + 1

Write a tree-recursive function part(n) that returns the number of partitions of n.

Hint: Introduce a locally defined function that computes partitions of n using only a subset of the integers less than or equal to n. Once you have done so, you can use very similar logic to the count_change function from the lecture notes:

```def part(n):
"""Return the number of partitions of positive integer n.

>>> part(5)
7
>>> part(10)
42
>>> part(15)
176
>>> part(20)
627
"""
```

Q4. (Extra for experts) 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 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). The sub and mul functons from the operator module are the only built-in function required to solve this problem. Return the expression from the function below:

```from operator import sub, mul

def make_anonymous_factorial():
"""Return the value of an expression that computes factorial.

>>> make_anonymous_factorial()(5)
120
"""
return YOUR_EXPRESSION_HERE
```

Q5. (Extra for experts) The Rlist class can represent lists with cycles. That is, a list may contain itself as a sublist.

```>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> s.rest.rest.rest = s
>>> s
3
```
This question has two parts:
1. Write a function has_cycle that returns True if and only if its argument, an Rlist instance, contains a cycle.
2. Write a function has_cycle_constant that has the same behavior as has_cycle but requires only a constant amount of space.

Hint: The solution to B is short (~10 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around:

```def has_cycle(s):
"""Return whether Rlist s contains a cycle.

>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> s.rest.rest.rest = s
>>> has_cycle(s)
True
>>> t = Rlist(1, Rlist(2, Rlist(3)))
>>> has_cycle(t)
False
"""

def has_cycle_constant(s):
"""Return whether Rlist s contains a cycle.

>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> s.rest.rest.rest = s
>>> has_cycle_constant(s)
True
>>> t = Rlist(1, Rlist(2, Rlist(3)))
>>> has_cycle_constant(t)
False
"""

class Rlist(object):
"""A recursive list consisting of a first element and the rest."""
class EmptyList(object):
def __len__(self):
return 0

empty = EmptyList()

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

def __repr__(self):
args = repr(self.first)
if self.rest is not Rlist.empty:
args += ', {0}'.format(repr(self.rest))
return 'Rlist({0})'.format(args)

def __len__(self):
return 1 + len(self.rest)

def __getitem__(self, i):
if i == 0:
return self.first
return self.rest[i-1]
```