Homework 4: Iterators, Generators, Efficiency
Due by 11:59pm on Thursday, July 18
Instructions
Download hw04.zip. Inside the archive, you will find a file called
hw04.py, along with a copy of the ok
autograder.
Submission: When you are done, submit the assignment by uploading all code files you've edited to Gradescope. 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 Gradescope. 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:
Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. This homework is out of 2 points.
Required Questions
Getting Started Videos
These videos may provide some helpful direction for tackling the coding problems on this assignment.
To see these videos, you should be logged into your berkeley.edu email.
Generators
Q1: Infinite Hailstone
Write a generator function that yields the elements of the hailstone sequence starting at number n
.
After reaching the end of the hailstone sequence, the generator should yield the value 1 indefinitely.
Here's a quick reminder of how the hailstone sequence is defined:
- Pick a positive integer
n
as the start. - If
n
is even, divide it by 2. - If
n
is odd, multiply it by 3 and add 1. - Continue this process until
n
is 1.
Try to write this generator function recursively. If you're stuck, you can first try writing it iteratively and then seeing how you can turn that implementation into a recursive one.
Hint: Since
hailstone
returns a generator, you canyield from
a call tohailstone
!
def hailstone(n):
"""Q1: Yields the elements of the hailstone sequence starting at n.
At the end of the sequence, yield 1 infinitely.
>>> hail_gen = hailstone(10)
>>> [next(hail_gen) for _ in range(10)]
[10, 5, 16, 8, 4, 2, 1, 1, 1, 1]
>>> next(hail_gen)
1
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q hailstone
Q2: Merge
Write a generator function merge
that takes in two infinite generators a
and b
that are in increasing order without duplicates and returns a generator that has all the elements of both generators, in increasing order, without duplicates.
def merge(a, b):
"""Q2:
>>> def sequence(start, step):
... while True:
... yield start
... start += step
>>> a = sequence(2, 3) # 2, 5, 8, 11, 14, ...
>>> b = sequence(3, 2) # 3, 5, 7, 9, 11, 13, 15, ...
>>> result = merge(a, b) # 2, 3, 5, 7, 8, 9, 11, 13, 14, 15
>>> [next(result) for _ in range(10)]
[2, 3, 5, 7, 8, 9, 11, 13, 14, 15]
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q merge
Q3: Generate Permutations
Given a sequence of unique elements, a permutation of the sequence is a list
containing the elements of the sequence in some arbitrary order. For example,
[2, 1, 3]
, [1, 3, 2]
, and [3, 2, 1]
are some of the permutations of the
sequence [1, 2, 3]
.
Implement perms
, a generator function that takes in a sequence seq
and returns a generator that yields all permutations of seq
. For this question,
assume that seq
will not be empty.
Permutations may be yielded in any order. Note that the doctests test whether
you are yielding all possible permutations, but not in any particular order.
The built-in sorted
function takes in an iterable object and returns a list
containing the elements of the iterable in non-decreasing order.
Hint: If you had the permutations of all but one of the elements in
seq
, how could you use that to generate the permutations of the fullseq
? For example, you can useperms([1,2])
to generate permutations forperms([1,2,3])
:
Try drawing a similar diagram for
perms([1,2,3,4])
.
Hint: Remember, it's possible to loop over generator objects because generators are iterators!
def perms(seq):
"""Q3: Generates all permutations of the given sequence. Each permutation is a
list of the elements in SEQ in a different order. The permutations may be
yielded in any order.
>>> p = perms([100])
>>> type(p)
<class 'generator'>
>>> next(p)
[100]
>>> try: # Prints "No more permutations!" if calling next would cause an error
... next(p)
... except StopIteration:
... print('No more permutations!')
No more permutations!
>>> sorted(perms([1, 2, 3])) # Returns a sorted list containing elements of the generator
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>>> sorted(perms((10, 20, 30)))
[[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
>>> sorted(perms("ab"))
[['a', 'b'], ['b', 'a']]
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q perms
Q4: Yield Paths
Define a generator function yield_paths
which takes in a tree t
, a value
value
, and returns a generator object which yields each path from the root
of t
to a node that has label value
.
Each path should be represented as a list of the labels along that path in the tree. You may yield the paths in any order.
def yield_paths(t, value):
"""Q4: Yields all possible paths from the root of t to a node with the label
value as a list.
>>> t1 = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
>>> print_tree(t1)
1
2
3
4
6
5
5
>>> next(yield_paths(t1, 6))
[1, 2, 4, 6]
>>> path_to_5 = yield_paths(t1, 5)
>>> sorted(list(path_to_5))
[[1, 2, 5], [1, 5]]
>>> t2 = tree(0, [tree(2, [t1])])
>>> print_tree(t2)
0
2
1
2
3
4
6
5
5
>>> path_to_2 = yield_paths(t2, 2)
>>> sorted(list(path_to_2))
[[0, 2], [0, 2, 1, 2]]
"""
if label(t) == value:
yield ____
for b in branches(t):
for ____ in ____:
yield ____
Hint: If you're having trouble getting started, think about how you'd approach this problem if it wasn't a generator function. What would your recursive calls be? With a generator function, what happens if you make a "recursive call" within its body?
Hint: Try coming up with a few simple cases of your own! How should this function work when
t
is a leaf node?
Hint: Remember, it's possible to loop over generator objects because generators are iterators!
Note: Remember that this problem should yield paths -- do not return a list of paths!
Use Ok to test your code:
python3 ok -q yield_paths
OOP
Q5: Minty
A mint is a place where coins are made. In this question, you'll implement a Minty
class that can output a Coin
with the correct year and worth.
- Each
Minty
instance has ayear
stamp. Theupdate
method sets theyear
stamp to thepresent_year
class attribute of theMinty
class. - The
create
method inMinty
returns an instance ofCoin
stamped with theMinty
instance's year (which may be different fromMinty.present_year
if the stamp has not been updated.) - The
Coin
constructor should ensure that each coin has the correct year and denomination value (cents
), specific to the type of coin (in our case, just 'Dime' or 'Nickel'). - A
Coin
'sworth
method returns itscents
value plus an additional cent for each year of age beyond 50 years. A coin's age can be determined by subtracting the coin's year from thepresent_year
class attribute of theMinty
class.
Note: The getting started video for this problem covers a version that includes inheritance, but this problem does not involve inheritance.
class Minty:
"""A mint creates coins by stamping on years. The update method sets the mint's stamp to Minty.present_year.
>>> mint = Minty()
>>> mint.year
2021
>>> dime = mint.create('Dime')
>>> dime.year
2021
>>> Minty.present_year = 2101 # Time passes
>>> nickel = mint.create('Nickel')
>>> nickel.year # The mint has not updated its stamp yet
2021
>>> nickel.worth() # 5 cents + (80 - 50 years)
35
>>> mint.update() # The mint's year is updated to 2101
>>> Minty.present_year = 2176 # More time passes
>>> mint.create('Dime').worth() # 10 cents + (75 - 50 years)
35
>>> Minty().create('Dime').worth() # A new mint has the current year
10
>>> dime.worth() # 10 cents + (155 - 50 years)
115
"""
present_year = 2021
def __init__(self):
self.update()
def create(self, type):
"*** YOUR CODE HERE ***"
def update(self):
"*** YOUR CODE HERE ***"
class Coin:
cents = 50
def __init__(self, year, type):
"*** YOUR CODE HERE ***"
def worth(self):
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q Minty
Q6: Vending Machine
In this question you'll create a vending machine that sells a single product and provides change when needed.
Create a class called VendingMachine
that represents a vending
machine for some product. A VendingMachine
object returns strings
describing its interactions. Make sure your output exactly matches the strings in the doctests including punctuation and spacing!
You may find Python's formatted string literals, or f-strings useful. A quick example:
>>> feeling = 'love' >>> course = '61A!' >>> f'I {feeling} {course}' 'I love 61A!'
Fill in the VendingMachine
class, adding attributes and methods as appropriate, such that its behavior matches the following doctests:
class VendingMachine:
"""A vending machine that vends some product for some price.
>>> v = VendingMachine('candy', 10)
>>> v.vend()
'Nothing left to vend. Please restock.'
>>> v.add_funds(15)
'Nothing left to vend. Please restock. Here is your $15.'
>>> v.restock(2)
'Current candy stock: 2'
>>> v.vend()
'Please add $10 more funds.'
>>> v.add_funds(7)
'Current balance: $7'
>>> v.vend()
'Please add $3 more funds.'
>>> v.add_funds(5)
'Current balance: $12'
>>> v.vend()
'Here is your candy and $2 change.'
>>> v.add_funds(10)
'Current balance: $10'
>>> v.vend()
'Here is your candy.'
>>> v.add_funds(15)
'Nothing left to vend. Please restock. Here is your $15.'
>>> w = VendingMachine('soda', 2)
>>> w.restock(3)
'Current soda stock: 3'
>>> w.restock(3)
'Current soda stock: 6'
>>> w.add_funds(2)
'Current balance: $2'
>>> w.vend()
'Here is your soda.'
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q VendingMachine
Check Your Score Locally
You can locally check your score on each question of this assignment by running
python3 ok --score
This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.
Submit Assignment
Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.
Exam Practice
Homework assignments will also contain prior exam-level questions for you to take a look at. These questions have no submission component; feel free to attempt them if you'd like a challenge!
Generators
- Summer 2018 Final Q7a,b: Streams and Jennyrators
- Spring 2019 Final Q1: Iterators are inevitable
- Spring 2021 MT2 Q8: The Tree of L-I-F-E
- Summer 2016 Final Q8: Zhen-erators Produce Power
- Spring 2018 Final Q4a: Apply Yourself
Object-Oriented Programming
- Spring 2022 MT2 Q8: CS61A Presents The Game of Hoop.
- Fall 2020 MT2 Q3: Sparse Lists