*Due by 11:59 PM on (that is, the end of) Saturday, 8/4*

**This homework must be submitted online.** We do not
require a paper copy. If you would like a reader to give you written
feedback on your homework, submit a paper copy to the homework box.

**To turn in the electronic copy**, submit all of your
answers in files named `hw13.py`. Follow the instructions here to submit the
electronic copy.

If you would like, you can use the template files `hw13.py`

.
To copy this file to your lab account you can run the command:

cp ~cs61a/lib/hw/hw13/hw13.py .

to copy it into your current directory.

This homework makes use of the `Stream`
class and related functions, which can be found in `stream.py`

.
If you are on an instructional machine, you **should not**
need to copy this file to your account. However, if you would like to
copy it to your account you can use the command:

cp ~cs61a/lib/python_modules/stream.py .

to copy it into your current directory.

In homeworks, we have three different categories of questions:

**Core Questions**— Questions that we believe test a core concept of the course and should be your highest priority when attempting the homework.**Reinforcement Questions**— Questions that we believe have material that is either covered by other questions in this homework or in past homeworks, and can therefore be considered second priority after the core questions have been completed.**Extra for Experts**— As in earlier homeworks, these problems are*completely optional*. You are encouraged to try these questions once you have completed questions from the other two categories. However, these are questions that we consider either more difficult than what we would ask you on an exam or that focus on ideas we are not concerned with in this course, so please do not be discouraged if you do not solve them.

It is our hope that these categories will help guide you in deciding how to divide your time when working on the homeworks.

**Contest**

If you and your project 4 partner would like to submit something for
the contest, fill out the templates `featherweight.scm`

and `heavyweight.scm`

with code to generate a
recursively defined image using STk's built-in drawing functions. To
enter your submission(s) to the contest, run the command:

submit proj4-contest

on a school computer. **If you do not submit it through
proj4-contest, your entry will not be considered for voting! Do NOT
submit it as part of Homework 13.**

**To start drawing when using STk**, first call the
function `cs` with no arguments like
so:

STk> (cs)

This should open up a graphical window for your drawing to be shown in.

For a summary of drawing commands and a description of the contest rules, see the contest section of the project 4 specifications. You should be able to see a listing of the drawing commands in the project files (specifically scheme_primitives.py).

**EDIT!** We updated the contest files to load another
file of definitions to allow you to use most of the commands you'd
normally be able to use in your project for turtle. The file is `stk-turtle-stuff.scm`

. Please feel
free to use this to get the contest going in STk. The two words for the
load command (which were added) and the words in the additional file will
not count against you.

Also, you should include an image for each of your submissions to the contest. If you do not, it is very likely that we won't be able to include an image of the final result on the voting website! Please name each image as something sensible (like featherweight.jpg and heavyweight.jpg). Please avoid LARGE (extremely high resolution) images, since this can cause us problems with space on the instructor account.

**Core Questions**

**Q1.** Define a function `scale_stream` that returns a stream over each element of an
input stream, scaled by a constant k.

**Q2.** Given the `Stream`
class and related functions found in `stream.py`

, produce a
function `uniq` that takes a stream and
returns a stream in which duplicates of any value are filtered out. This
should work for infinite streams as well as finite ones.

**Q3.** Augment the `IterableStream` class, a subclass of `Stream`, with an `__iter__`
method that returns a generator over the elements of the stream.

*Hint:* You might have a locally defined generator function
inside your definition of `__iter__`.

**Reinforcement Questions**

**Q4.** Write the function `make_stream_of_streams`, which returns an infinite stream,
where the element at position `i`,
counting from 1, is *also* an infinite stream of integers that
start from `i`.

def make_stream_of_streams(): """ >>> stream_of_streams = make_stream_of_streams() >>> stream_of_streams Stream(Stream(1, <compute_rest>), <compute_rest>) >>> stream_of_streams.first Stream(1, <compute_rest>) >>> stream_of_streams.rest.rest.rest.first Stream(4, <compute_rest>) >>> stream_of_streams.rest.first.rest.first 3 >>> show_stream(stream_of_streams, count=3) "'1, 2, 3, ...', '2, 3, 4, ...', '3, 4, 5, ...', ..." """

**Q5.** Write the function `make_generators_generator`, which takes a generator function
`g` and defines a generator which yields
generators which for the `i`th generator
will generate items 1 through `i`
generated by the generator returned by `g`.

def make_generators_generator(g): """Generates all the "sub"-generators of the generator returned by the generator function g. >>> def ints_to(n): ... for i in range(1, n + 1): ... yield i ... >>> def ints_to_5(): ... for item in ints_to(5): ... yield item ... >>> for gen in make_generators_generator(ints_to_5): ... print("Next Generator:") ... for item in gen: ... print(item) ... Next Generator: 1 Next Generator: 1 2 Next Generator: 1 2 3 Next Generator: 1 2 3 4 Next Generator: 1 2 3 4 5 """

**Q6.** Write the function `decimal_rep` that takes in the numerator and denominator of a
rational number and returns an infinite stream of the decimal
representation of the rational number. The first element of the stream is
always the number before the decimal point.

def decimal_rep(num, denom): """ >>> one_third = decimal_rep(1, 3) >>> show_stream(one_third) '0, 3, 3, 3, 3, 3, 3, 3, 3, 3, ...' >>> ten_thirds = decimal_rep(10, 3) >>> show_stream(ten_thirds) '3, 3, 3, 3, 3, 3, 3, 3, 3, 3, ...' >>> one_half = decimal_rep(1, 2) >>> show_stream(one_half) '0, 5, 0, 0, 0, 0, 0, 0, 0, 0, ...' """

**Q7.** A famous problem, first raised by R. Hamming, is
to enumerate, in ascending order with no repetitions, all positive
integers with no prime factors other than 2, 3, or 5. 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.

However, this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, we can build a stream of such numbers. Let us call the required stream of numbers s and notice the following facts about it:

- s begins with 1.
- The elements of
`scale_stream(s, 2)`are also elements of s. - The same is true for
`scale_stream(s, 3)`and`scale-stream(s, 5).` - These are all of the elements of s.

Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions.

Fill in the definitions of `merge` and
`make_s`:

def merge(s0, s1): """Return a stream over the elements of s0 and s1, removing repeats. >>> ints = integers_starting_from(1) >>> twos = scale_stream(ints, 2) >>> threes = scale_stream(ints, 3) >>> m = merge(twos, threes) >>> show_stream(m) '2, 3, 4, 6, 8, 9, 10, 12, 14, 15, ...' """ def make_s(): """Return a stream over all positive integers with only factors 2, 3, & 5. >>> s = make_s() >>> show_stream(s, 15) '1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, ...'

**Q8.** *Run-length encoding* is a very simple
data compression technique, whereby *runs* of data are compressed
and stored as a single value. A run is defined to be a contiguous sequence
of the same number. For example, in the (finite) sequence

1, 1, 1, 1, 1, 6, 6, 6, 6, 2, 5, 5, 5

there are four runs: one each of 1, 6, 2, and 5. We can represent the same sequence as a sequence of tuples:

(5, 1), (4, 6), (1, 2), (3, 5)

Notice that the first element of each tuple is the number of times a particular number appears in a run, and the second element is the number in the run.

We will extend this idea to (possibly infinite) streams. Write a
function called `rle` that takes in a
stream of data, and returns a corresponding stream of tuples, which
represents the run-length encoded version of the stream. It will also
take in the maximum size of any given run (default 10) to prevent having
to compress infinite runs.

**Extra for Experts**

**Q9.** Extend the idea of `make_stream_of_streams` to handle streams of any provided
depth. A (flat) stream of integers is of depth 1, while an infinite stream
of infinite streams is of depth 2.

def make_deep_infinite_stream(n): """ >>> show_stream(make_deep_infinite_stream(1)) '1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...' >>> show_stream(make_deep_infinite_stream(2), 3) "'1, 2, 3, ...', '2, 3, 4, ...', '3, 4, 5, ...', ..." >>> show_stream(make_deep_infinite_stream(3), 2) "''1, 2, ...', '2, 3, ...', ...', ''2, 3, ...', '3, 4, ...', ...', ..." """