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:
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 ith 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:
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, ...', ...', ..."
"""