# Homework 8

*Due by 11:59pm on Monday, 7/27*

## Instructions

Download hw08.zip. Inside the archive, you will find a file called hw08.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 1 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

### Question 1

Implement `__contains__`

for the `Link`

class, which allows us to use the `in`

operator to check if a `value`

is contained in a linked list.

```
class Link:
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __contains__(self, value):
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q contains`

### Generating natural numbers

The following questions use the `naturals`

generator function, which yields
an infinite sequence of integers starting at 1.

```
def naturals():
"""A generator function that yields the infinite sequence of natural
numbers, starting at 1.
>>> m = naturals()
>>> type(m)
<class 'generator'>
>>> [next(m) for _ in range(10)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
"""
i = 1
while True:
yield i
i += 1
```

### Question 2

Implement an iterator class called `ScaleIterator`

that scales elements in an
iterable `s`

by a number `k`

.

```
class ScaleIterator:
"""An iterator the scales elements of the iterable s by a number k.
>>> s = ScaleIterator([1, 5, 2], 5)
>>> list(s)
[5, 25, 10]
>>> m = ScaleIterator(naturals(), 2)
>>> [next(m) for _ in range(5)]
[2, 4, 6, 8, 10]
"""
def __init__(self, s, k):
"*** YOUR CODE HERE ***"
def __iter__(self):
return self
def __next__(self):
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q ScaleIterator`

### Question 3

Implement the generator function `scale(s, k)`

, which yields elements of the
given iterable `s`

, scaled by `k`

.

```
def scale(s, k):
"""Yield elements of the iterable s scaled by a number k.
>>> s = scale([1, 5, 2], 5)
>>> type(s)
<class 'generator'>
>>> list(s)
[5, 25, 10]
>>> m = scale(naturals(), 2)
>>> [next(m) for _ in range(5)]
[2, 4, 6, 8, 10]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q scale`

### Question 4

Implement `merge(s1, s2)`

, which takes two iterables `s1`

and `s2`

whose
elements are ordered. `merge`

yields elements from `s1`

and `s2`

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

and `s1`

themselves do not
contain repeats. **You may also assume s0 and s1 represent infinite
sequences; that is, their iterators never raise StopIteration**.

See the doctests for example 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.
>>> twos = scale(naturals(), 2)
>>> threes = scale(naturals(), 3)
>>> m = merge(twos, threes)
>>> type(m)
<class 'generator'>
>>> [next(m) for _ in range(10)]
[2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
"""
i0, i1 = iter(s0), iter(s1)
e0, e1 = next(i0), next(i1)
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q merge`

### Question 5

A famous problem, first raised by Richard Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. These are called regular numbers. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement.

As an alternative, we can write a generator function of such numbers. Let us
call the sequence of numbers `s`

and notice the following facts about it.

`s`

begins with`1`

.- The elements of
`scale(s, 2)`

are also elements of`s`

. - The same is true for
`scale(s, 3)`

and`scale(s, 5)`

. - These are all of the elements of
`s`

.

Now all we have to do is combine elements from these sources. Use the `merge`

function you defined previously to fill in the definition of `make_s`

:

```
def make_s():
"""A generator function that yields all positive integers with only factors
2, 3, and 5.
>>> s = make_s()
>>> type(s)
<class 'generator'>
>>> [next(s) for _ in range(20)]
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q make_s`