Midterm 2 Walkthrough
1. A Bug’s Life
Wasp
Richard is trying to write a generator function that maps a given iterable using a oneargument function. Here’s what he comes up with:
def map_gen(fn, iterable):
for it in iterable:
yield from fn(it)
i. (0.5 pt) Richard tests out his function by running the code below. He expected to see [2, 4, 6, 8]
but instead gets an error when he runs these lines in an interpreter:
>>> data = [1, 2, 3, 4]
>>> fn = lambda x: x * 2
>>> list(map_gen(fn, data))
Which line of code in the function caused the code to break?
ii. (0.5 pt) Rewrite the buggy line of code you identified above to fix the error.
Walkthrough
Remember that yield from
keyword only expects an iterable expression next to it. The other way to think about it:
yield from itr
# code above is equivalent to the code below
for e in itr:
yield e
This means that we can rewrite Richard’s function as:
def map_gen(fn, iterable):
for it in iterable:
for e in fn(it):
yield e
From this, we can conclude that fn(it)
has to be an iterable. However, the test code that Richard is using defines fn
as lambda function that multiplies the argument by 2, which is unlikely to produce an iterable. In map_gen
, the function fn
is used with it
, which represents the contents of iterable
argument. In the test code, iterable
is a list data
, so it
is just a number that gets fed into fn
function. Therefore, fn(it)
would never result in an iterable, causing an error for yield from
that actually expects an iterable.
A quick fix would be to not use yield from
at all and yield the elements of iterable
after applying fn
on them:
def map_gen(fn, iterable):
for it in iterable:
yield fn(it)
Moth
Melanie is trying to write some code to represent a cylinder in Python. This is her code:
class Cylinder:
def __init__(self, radius, height):
self.radius = radius
self.height = height
def volume(self):
volume = 3.14 * self.radius ** 2 * self.height
return volume
def percent_filled(self, volume_of_water):
return (volume_of_water / self.volume) * 100
i. (0.5 pt) Melanie runs the following code expecting to see it return 50.0, since 392.5 is a halfempty cyl (or is it halffull?).
>>> cyl = Cylinder(5, 10)
>>> cyl.percent_filled(392.5)
Unfortunately, the code results in this error instead:
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/Users/melanie/cylinder.py", line 11, in percent_filled
return (volume_of_water / self.volume) * 100
TypeError: unsupported operand type(s) for /: 'int' and 'method'
According to this traceback, which method contains an error?
ii. (1.0 pt) Rewrite the buggy line of code from the method that you identified above to fix the error.
Walkthrough
Reading through the traceback, we could see that we got the TypeError
on the line 11, which corresponds to the method percent_filled
.
Continuing to read the error message closely, we see that the code attempted to divide the argument volume_of_water
(which is a number) by self.volume
(which has a function type, since volume
is defined as a method of Cylinder
class). We can fix this code by actually using the result of volume
method, which means we would have to call it.
def percent_filled(self, volume_of_water):
return (volume_of_water / self.volume()) * 100
# Now volume_of_water is divided by the result of self.volume(), which is also a number
Bumblebee
Amritansh steps up with a challenge of his own. He’s writing some code to flatten lists, but he seems to be running into some errors. Here’s his code:
def flatten(lst):
res = []
for el in lst:
if isinstance(el, list):
res += [res.extend(flatten(el))]
else:
res += [el]
return res
i. (1.0 pt) He runs this on a nested list, as below:
>>> my_data = ["Mialy", ["Daphne", "Jordan"]]
>>> flatten(my_data)
The result he expects is ["Mialy", "Daphne", "Jordan"]
. What is the actual result?
ii. (0.5 pt) What line number causes the unexpected output to appear?
iii. (1.0 pt) Rewrite the buggy line you identified above so that Amritansh gets the expected output.
Walkthrough
my_data
is a list of two elements: "Mialy"
and ["Daphne", "Jordan"]
. It means that the forloop in the body of flatten
(line 3) will perform 2 iterations. On the first iteration, el
refers to a string "Mialy"
. It is not an instance of a list, so it just gets added to res
. For now, res
looks like ["Mialy"]
.
However, on the next iteration, el
refers to ["Daphne", "Jordan"]
, forcing the code to enter the ifcondition body. There, we are executing the line res += [res.extend(flatten(el))]
. Let’s break this line down:
Before adding a list on the right hand side to res
with +=
, we have to know what that list is. It contains a single element, which is a result of evaluating res.extend(flatten(["Daphne", "Jordan"]))
.
The argument of extend
is a function call flatten(["Daphne", "Jordan"])
, which would return a list ["Daphne", "Jordan"]
back because there is nothing to flatten there (try executing Amritansh’s code to convince yourself).
So now we are evaluating res.extend(["Daphne", "Jordan"])
. extend
mutates the list by adding the contents of its argument. res
that was ["Mialy"]
turns into ["Mialy", "Daphne", "Jordan"]
. However, after completing its job, a call to extend
evaluates to None
, turning the list on the right hand side into [None]
. Here is a link to PythonTutor which can help you to visualize the changes.
So even though we’ve added two elements to res
, we still have to perform +=
with the right hand side, adding an additional 4th element to res
.
At the end, res
looks like ["Mialy", "Daphne", "Jordan", None]
because the evaluation result of extend
was added to res
. Fixing the behavior should focus on line 5 because that is where we are calling extend
but also using its evaluation result. Getting rid of +=
like this: res.extend(flatten(el))
or completely avoiding the use of extend
like: res += flatten(el)
will do the job.
2. What Would Python Display?
Question
Assume the following code has been run (you may find a boxandpointer diagram useful):
>>> lst1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> number_one = lst1.remove(1)
>>> some_number = lst1.pop()
>>> lst2 = lst1
>>> lst3 = lst2[:]
>>> lst1.insert(4, lst3)
>>> lst3.extend([lst1.pop() for _ in range(3)])
>>> lst2.append(lst1.remove(lst3))
For each part below, write the output of running the given code. Assume that none of the lines below will error.
(a) >>> lst1[4:] + [number_one, some_number]
(b) >>> lst3[5:9]
(c) >>> next(reversed(lst3[:5]))
(d) >>> lst1 is lst2
Walkthrough
This is a question which is much easier to answer if you draw out the state of the list at each stage, similar to the visualization offered by PythonTutor. Thus, for the walkthrough, we'll go through the steps shown in PythonTutor.
Here is the link to Python tutor with the code from this question. The bullet points below describe what happens after each step of the environment diagram. After reaching the final step, you will have the correct state of all variables and ready to answer the parts (a)(d).
Environment diagram steps:
 Step 1: Create a list
lst1
with numbers from 110.  Step 2:
remove
method modifies the list by removing the first occurrence of the argument (1
in this case), going left to right. So1
gets removed fromlst1
. However, the call toremove
will evaluate toNone
and that is the final value ofnumber_one
variable.  Step 3:
pop
deletes the last element of the list and also returns that last element, settingsome_number
variable to10
. Afterremove(1)
, followed bypop()
,lst1
has numbers from 2 to 9.  Step 4: we create variable
lst2
which just points to the same list object aslst1
.  Step 5: we are creating a copy of
lst2
with slicing and sincelst2
refers tolst1
, we copy its contents to form a new list object.lst3
will point to that object.  Step 6:
insert
method sticks in the second argument as a new element into the position specified by the first argument. In this case, for the4
th index of the list, we add a box and add a pointer to the listlst3
. When we add a list as a single object, we add a pointer to it.  Steps 713: we are going to call
lst3.extend()
with list comprehension expression as an argument. Let’s evaluate it first. The list comprehension essentially “pop”s 3 elements fromlst1
and populates the list with them. The last three elements (counting from backwards sincepop
deletes the last element every time it gets called) fromlst1
form the list that looks like[9, 8, 7]
. Now our original call looks likelst3.extend([9, 8, 7])
. We extend thelst3
(which still has its “own” 7, 8, 9 numbers, since it was copied fromlst1
in the past). Therefore,lst1
loses three elements and looks like[2, 3, 4, 5, lst3, 6]
, whilelst3
gains three elements and now is[2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7]
.  Step 14:
append
adds its argument as a single element intolst2
. What is the argument? The result of evaluatinglst1.remove(lst3))
. From step 2, we know thatremove
will just delete the first occurrence oflst3
, which is at index4
oflst1
. After deleting that element, the remove method returnsNone
. Solst1
loses one more element, but gainsNone
since we are executinglst2.append(None)
(lst1
andlst2
are referring to the same object).
Congrats, you have the final state of the environment! Let’s answer the questions:
Blank (a)
The expression lst1[4:] + [number_one, some_number]
first takes a slice of all elements of lst1
starting from index 4
. This would be equal to [6, None]
. The second operand in our expression is [number_one, some_number]
, which would evaluate to [None, 10]
. Adding these two lists forms a new one which looks like: [6, None, None, 10]
.
Blank (b)
Slicing lst3
from index 5
to 8
(recall that slicing excludes the upperbound index), we will get [7, 8, 9, 9]
.
Blank (c)
This might be a tough one. When we are working with heavily nested expression, we start by evaluating the deepest one — lst3[:5]
in this case. A new copy of all elements from 0
to 4
would be equal to [2, 3, 4, 5, 6]
. So now we are looking at next(reversed([2, 3, 4, 5, 6]))
. Once more we pay close attention to the deepest expression — a call to reversed
. It returns an iterator to the given sequence, which yields the elements in the reverse order. The first element starting from the back is 6
, which is what gets yielded when we call next
.
Blank (d)
At step 4, we’ve created a label lst2
that points to the same object as lst1
. Since they are still pointing to the same object, lst1 is lst2
evaluates to True
.
3. A Different Kind of Dictionary
Question
The DictionaryEntry
class stores entries for an English dictionary, using
instance variables for the word
and its definition
.
class DictionaryEntry:
"""
>>> euph = DictionaryEntry("euphoric", "intensely happy")
>>> avid = DictionaryEntry("avid", "enthusiastic")
>>> [euph, avid]
[DictionaryEntry('euphoric', 'intensely happy'), DictionaryEntry('avid', 'enthusiastic')]
>>> f'Today we are learning {euph}'
'Today we are learning euphoric: "intensely happy"'
"""
def __init__(self, w, d):
self.word = w
self.definition = d
def __repr__(self):
__________
(a)
def __str__(self):
__________
(b)
Fill in blank (a).
Fill in blank (b).
Walkthrough
Recall that repr
is called when we ask Python interpreter to evaluate the object instance, while str
is called when we would like to print
the object or use it as part of the format string. Let’s run through a quick example with Link
objects which will also help us while solving this problem:
>>> lnk = Link(1, Link(2, Link(3)))
>>> print(str(lnk))
<1 2 3>
>>> print(repr(lnk))
Link(1, Link(2, Link(3)))
>>> a = eval(repr(lnk))
# a is now also a linked list that looks like 1 > 2 > 3
Recall that repr
delivers the representation which could be used to recreate the same object using eval()
(it is the same "text" we use to create lnk
variable in the code).
Now back to the problem. The doctest >>> [euph, avid]
creates a list with two DictionaryEntry
type objects. To create the list, Python interpreter firstly has to evaluate each element (figure out how to represent it with __repr__
function) and display the resulting list. We have to match the result that looks like: [DictionaryEntry('euphoric', 'intensely happy'), DictionaryEntry('avid', 'enthusiastic')]
.
Seems that every element is represented as if we are using the initializer DictionaryEntry
to create it. Our solution could look something like:
def __repr__(self):
return f"DictionaryEntry({self.word}, {self.definition})"
However, we will lose the quotes around the word and definition strings. From the Link
example above, we've learned that repr
outputs a string that can be used to recreate the same object if passed to eval()
function. If attributes lose quotes, eval
method would treat these attributes as variables and try to look them up (which would result in error since such variables are not defined). Consider this example:
DictionaryEntry(avid, enthusiastic)
Here avid
and enthusiastic
are part of the syntax and interpreter will try to make sense of them. In contrast, if we preserve the quotes, two arguments of DictionaryEntry
initializer will be treated as string objects (as originally defined).
DictionaryEntry('avid', 'enthusiastic')
To achieve that, we can wrap string objects into their own repr
calls, which would output them with quotes.
Our solution for part (a) would look like:
def __repr__(self):
return f"DictionaryEntry({repr(self.word)}, {repr(self.definition)})"
The second doctest >>> f'Today we are learning {euph}'
uses the format string, which relies on the implementation of __str__
method of the object. The result we should strive for is 'Today we are learning euphoric: "intensely happy"'
(notice that str
will be called only on for {euph}
part of the format string and "Today we are learning "
is actually part of the doctest, which should not be included in the implementation). So looks like we are just inserting the word, followed by colon and then the word’s definition (with quotes around it). Our code that reflects this logic:
def __str__(self):
return f"{self.word}: "{self.definition}""
However, we would not be able to execute this code since it has an error. Python interpreter treats anything between quotes "
as a string, so __str__
would try to return f"{self.word}: "
, since it is the first combination of symbols trapped between quotes. However, it would not be happy about remaining symbols {self.definition}""
since it does not know what to do with them.
To work around this issue, we have to convey that quotes we use around {self.definition}
are part of the result string and the interpreter should treat only the first and the last quotes for stringcreation purposes. We achieve this by “escaping” the inner quotes and complete the solution for part (b):
def __str__(self):
return f"{self.word}: \"{self.definition}\""
# \" is read by the interpreter as a single " symbol that is part of the string,
# not as a symbol to start/end the string object
The alternative solution would be to just use single quotes without any escaping:
def __str__(self):
return f"{self.word}: '{self.definition}'"
4. Beadazzled
Question
Implement make_necklace
, a function that creates a linked list where each value comes from a given list of beads
, and the beads are repeated in order to make a necklace of a given length
.
For example, if make_necklace
is called with ["~", "@"]
and a length
of 3, then the linked list will contain '~'
, then '@'
, then '~'
. Here's a diagram of that list:
See the docstring and doctests for further details on how the function should behave.
def make_necklace(beads, length):
"""
Returns a linked list where each value is taken from the BEADS list,
repeating the values from the BEADS list until the linked list has reached
LENGTH. You can assume that LENGTH is greater than or equal to 1, there is
at least one bead in BEADS, and all beads are string values.
>>> wavy_ats = make_necklace(["~", "@"], 3)
>>> wavy_ats
Link('~', Link('@', Link('~')))
>>> print(wavy_ats)
<~ @ ~>
>>> wavy_ats2 = make_necklace(["~", "@"], 4)
>>> print(wavy_ats2)
<~ @ ~ @>
>>> curly_os = make_necklace(["}", "O", "{"], 9)
>>> print(curly_os)
<} O { } O { } O {>
"""
if __________:
(a)
return __________
(b)
return Link(__________, make_necklace(__________, __________))
(c) (d) (e)
Fill in blank (a).
Fill in blank (b).
Fill in blank (c).
Fill in blank (d).
Fill in blank (e).
Walkthrough
For this question, we basically have to create a new linked list of given length
using elements from the beads
list. If we run out of elements from there, we circle back to its beginning and start over.
Blanks (a) and (b) look like a spot to handle the base case, but we are not sure what it should be: len(beads) == 0
? length == 0
? or length == 1
? Since we do not know yet how our recursion constructs the list and changes the input arguments, it might be tough to choose the correct base case from the start.
Let’s tackle the recursive call. We see that the last line is creating a new instance of Link
and calling make_necklace
to use its result as the rest
component of a newborn linked list. This call to make_necklace
is inviting us to make a leapoffaith!
Let’s consider this doctest:
>>> curly_os = make_necklace(["}", "O", "{"], 9)
>>> print(curly_os)
<} O { } O { } O {>
We know that the first element of the linked list should be "}"
, which is also the first element in the beads
list. Well, we can move closer to the solution by putting beads[0]
into blank (c):
...
return Link(beads[0], make_necklace(__________, __________))
# (c) (d) (e)
We’ve got the first
element right! Now, we need to come up with the correct rest
of the linked list: <O { } O { } O {>
.
Assuming that the function works correctly (leapoffaith!), how could we use the result of make_necklace
on smaller inputs to get the correct rest
of the linked list? We’ve already used the first element of beads
and the rest
component is supposed to have a smaller length, so we could try changing the arguments the following way:
make_necklace(beads[1:], length  1)
# since initially beads = ["}", "O", "{"] and length = 9, this translates to
make_necklace(["0", "{"], 8)
If we assumed that the function was implemented correctly (taking a leap of faith), the function call above would end up creating a necklace that looks like <0 { 0 { 0 { 0 {>
, which is not the <O { } O { } O {>
that we wish to get. Moreover, this current implementation Link(beads[0], make_necklace(beads[1:], length  1))
would likely result in an IndexError
for beads[0]
, since it will run out of beads
elements before achieving the required length
.
In fact, this function call above would not even be “aware” of a symbol "}"
(because its beads
argument does not contain it)! What if we do not slice the beads
list and only decrement the length
argument?
make_necklace(beads, length  1)
# initially beads = ["}", "O", "{"] and length = 9, so this translates to
make_necklace(["}", "0", "{"], 8)
This call is supposed to bring us <} 0 { } 0 { } 0>
, which is again not the <O { } O { } O {>
we are hoping for. 😕 If we do not slice the list, it would again start from "}"
symbol.
Okay, if we move away from slicing our given list for a moment, what is the correct beads
content that would evaluate to <O { } O { } O {>
?
make_necklace(["0", "{", "}"], 8)
Alright, now lets try to use our beads
(which is equal to ["}", "0", "{"]
) to match this list.
Everything except the last element is actually just the result of slice beads[1:]
. Where do we take the last "}"
? It is actually the first element of our beads
!
# if beads = ["}", "0", "{"], we can use create the circular version of it by
beads[1:] + [beads[0]]
# which evaluates to ["0", "{"] + ["}"] = ["0", "{", "}"]
Woohoo! 🥳
Turns out, slicing the list from the first element and attaching that first element to the end captures the list rotation logic of this question. Finally, our recursive call and blanks (c)(e) look like:
...
return Link(beads[0], make_necklace(beads[1:] + [beads[0]], length  1))
# (c) (d) (e)
The easy way to figure out the base cases would be to consider the smallest instance of the problem or the inputs when our recursive calls would stop making sense. We can’t rely on the length of the beads
list because it is now constant! (the recursive call just shifts the contents, but never decreases the size of the list). However, the answer to make_necklace(["anything", "here"], 0)
must be an empty linked list, irrespective of the beads
content. Therefore, the base case (blanks (a) and (b)) is conditioned on the length
argument, which steadily decreases as recursion progresses:
if length == 0:
return Link.empty
Full solution code for reference:
def make_necklace(beads, length):
if length == 0:
# (a)
return Link.empty
# (b)
return Link(beads[0], make_necklace(beads[1:] + [beads[0]], length  1))
# (c) (d) (e)
5. File Treetionaries
Question
We can represent files and folders on a computer with Trees:
Tree("C:", [Tree("Documents", [Tree("hw05.py")]), Tree("pwd.txt")])
We can also represent the same folder layout with dictionaries:
{"C:": {"Documents": {"hw05.py": "FILE"}, "pwd.txt": "FILE"}}
Notice that in this model, we still treat files as dictionary keys, but with the value "FILE"
.
Complete the implementation of filetree_to_dict
below, which takes in a Tree t
representing files and folders, and converts it to the dictionary representation.
def filetree_to_dict(t):
"""
>>> filetree_to_dict(Tree("hw05.py"))
{"hw05.py": "FILE"}
>>> filetree = Tree("C:", [Tree("Documents", [Tree("hw05.py")]), Tree("pwd.txt")])
>>> filetree_to_dict(filetree)
{"C:": {"Documents": {"hw05.py": "FILE"}, "pwd.txt": "FILE"}}
"""
res = {}
if t.is_leaf():
res[t.label] = _____________
(a)
else:
nested = {}
for branch in t.branches:
nested[branch.label] = _____________(branch)[_____________]
(b) (c)
_____________ = nested
(d)
return res
Fill in blank (a).
Fill in blank (b).
Fill in blank (c).
Fill in blank (d).
Walkthrough
To reiterate the prompt, we are given a tree that resembles the filesystem structure and we have to build out a dictionary with the same structure. Let’s make a few notes before we start:
 The function starts by creating an empty dictionary
res
and ends by returning it. This means that every recursive call to functionfiletree_to_dict
will create its own dictionary and return it as a result. The correct combination of these dictionaries should result in the final answer for the entire treet
.  Notice that node labels always directly correspond to the dictionary keys. There are only two possibilities for the dictionary values: another nested dictionary or a string
"FILE"
. We use the latter only when we get to the files (bottom of the tree) and there are no folders to recurse further.
With these in mind, let’s start playing with the skeleton!
After declaring an empty dictionary res
, we check if the node is a leaf. If that is the case, the skeleton asks us to assign some value (what goes to blank (a)) to the key t.label
in the dictionary res
. Looking at doctests, we see that for any leaf, we assign "FILE"
string as a value (where the key is leaf’s label). Therefore, this line might look like:
if t.is_leaf():
res[t.label] = "FILE"
# blank (a)
If node happened to not be a leaf, we enter the else
case. This indicates that our tree has branches, which means that for the current tree t
, the value of res[t.label]
should be another dictionary that represents the structure of the branches of t
. The newborn dictionary nested
looks to be a perfect candidate and on blank (d), we are already trying to assign it to something:
...
else:
nested = {}
for branch in t.branches:
nested[branch.label] = _____________(branch)[_____________]
# (b) (c)
res[t.label] = nested
# (d)
return res
The final thing we have to do now is to populate the nested
dictionary, which should happen in the forloop with blanks (b) and (c). Let’s consider a doctest below:
>>> filetree = Tree("C:", [Tree("Documents", [Tree("hw05.py")]), Tree("pwd.txt")])
>>> filetree_to_dict(filetree)
{"C:": {"Documents": {"hw05.py": "FILE"}, "pwd.txt": "FILE"}}
When we call the function, we start from the root node with label "C:"
. It is not a leaf, so we go into the else
case, create an empty dictionary and start going over the branches of t
. In the forloop, the branch
will refer to one of the two subtrees of t
. Let’s say it refers to one that starts from the node labeled "Documents"
. So we are going to execute the line:
nested["Documents"] = _____________(branch)[_____________]
# (b) (c)
# 'branch' variable is referring to a subtree that starts with
# a node with label "Documents"
# Namely, branch variable refers to Tree("Documents", [Tree("hw05.py")])
The blank (b) is followed by (branch)
, which strongly looks like a function call. Probably this is the place for our recursion, so we put filetree_to_dict
for blank (b). What is it going to return? If we assume it works correctly (leapoffaith here), for input branch
, it should return {"Documents": {"hw05.py": "FILE"}
. Observe that we come up with this result based on the prompt description, not executing our solution (it is not complete).
So if we assume the expression filetree_to_dict(branch)
evaluates to the abovementioned dictionary, we need to extract {"hw05.py": "FILE"}
from it, which corresponds to the key "Documents"
. To get the value, we can put branch.label
into blank (c). To reiterate, a completed elsecase (and the full solution) looks like the following:
def filetree_to_dict(t):
res = {}
if t.is_leaf():
res[t.label] = "FILE"
# (a)
else:
nested = {}
for branch in t.branches:
nested[branch.label] = filetree_to_dict(branch)[branch.label]
# (b) # (c)
res[t.label] = nested
# (d)
return res
6. Mapping Time and Space
Question
(a) The goal of the maplink_to_list
function below is to map a linked list lnk
into a Python list, applying a provided function f
to each value in the list along the way. The function is fully written and passes all its doctests.
def maplink_to_list1(f, lnk):
"""Returns a Python list that contains f(x) for each x in Link LNK.
>>> square = lambda x: x * x
>>> maplink_to_list1(square, Link(3, Link(4, Link(5))))
[9, 16, 25]
"""
new_lst = []
while lnk is not Link.empty:
new_lst.append(f(lnk.first))
lnk = lnk.rest
return new_lst
 (1.0 pt) What is the order of growth of
maplink_to_list1
in respect to the size of the input linked listlnk
?
(b) The next function, maplink_to_list2
, serves the same purpose but is implemented slightly differently. This alternative implementation also passes all the doctests.
def maplink_to_list2(f, lnk):
"""Returns a Python list that contains f(x) for each x in Link LNK.
>>> square = lambda x: x * x
>>> maplink_to_list2(square, Link(3, Link(4, Link(5))))
[9, 16, 25]
"""
def map_link(f, lnk):
if lnk is Link.empty:
return Link.empty
return Link(f(lnk.first), map_link(f, lnk.rest))
mapped_lnk = map_link(f, lnk)
new_lst = []
while mapped_lnk is not Link.empty:
new_lst.append(mapped_lnk.first)
mapped_lnk = mapped_lnk.rest
return new_lst
 What is the order of growth of the alternative function,
maplink_to_list2
, in respect to the size of the input linked listlnk
?
(c) Which of the functions requires more space to run?
Walkthrough
Part (a)
Recall that the order of growth (efficiency of the function) is the relationship of the size of the input to the “time” it takes to compute the answer. Basically, we have to figure out if increasing the size of the input forces our code to do more operations and if yes, by how much. When considering the number of operations, we often are counting the number of iterations of a loop (in an iterative approach) or the number of recursive function calls (in a recursive approach). Notably, the number of lines of code do not necessarily correspond to the efficiency of a function.
While executing maplink_to_list1
, we have to see each element of the linked list lnk
, so that we can modify and add it to the resulting list new_lst
. If lnk
had more elements, the number of iterations of the forloop would increase proportionally (i.e. if lnk
had 10 more elements, the forloop would have to do 10 more iterations to see those elements, apply f
to them and add the result to new_lst
).
Hence, the order of growth of the function maplink_to_list1
is linear.
Part (b)
The function maplink_to_list2
achieves the same goal as maplink_to_list1
, but has a different implementation. Namely, it firstly creates a new linked list mapped_lnk
(using map_link
function), where each element is the result of applying f
to each element of the original linked list lnk
. After building mapped_lnk
, the function goes over it and copies its contents to new_lst
.
We have two components that might depend on the size of the input linked list lnk
: a call to the inner function map_link
(because it takes lnk
as an argument) and the whileloop that comes right after the call. Let’s evaluate the efficiency of each component:
First, if we look at the body of map_link
, we see that it creates a linked list instance as its return value. In order to evaluate the rest of the linked list, it calls map_link
again on the rest of the input. It means that for each element of the original lnk
, we would have to make a new function call. In other words, the number of calls to map_link
function is directly proportional to the number of elements in the lnk
. This hints to us that the order of growth of map_link
is linear (you could also reason about this from the fact that map_link
has to “see” each element of the linked list in order to compute the modified linked list).
Now, to the whileloop. It actually looks very similar to the loop from the previous part, since all we do on each iteration is to add the element to new_lst
and move the pointer to the next element of the linked list. Therefore, the number of iterations directly depend on the number of elements (you have to see all elements before you stumble upon Link.empty
). This portion of the code has a linear order of growth.
When there are multiple components that affect the final efficiency of the function, we take the one that is the slowest. The reason for that is in the worst case, the faster component’s compute time becomes negligible comparing to the slower component’s one. However, in this case, both components have equal efficiency, so we can take either of them as our answer.
Hence, the order of growth of the function maplink_to_list2
is linear.
Part (c)
The space efficiency is concerned by the amount of storage the function requires to compute the answer. To be precise, it is the relationship of the size of the input to the “space” it takes to compute the answer. As the input gets bigger, the amount of things we store should also grow according to some relationship (linear, exponential etc.)
With that knowledge, let’s analyze both functions.
The first function stores the “mapped” elements of lnk
into new_lst
, which size is the same as number of elements in lnk
. This is all the function needs to compute the final answer.
The second function firstly builds out a new linked list mapped_lnk
, which size is equivalent to the size of the lnk
. Then, it additionally creates new_lst
, which also takes up the same amount of space. Moreover, the mapped_lnk
is created recursively, so we have to store and keep track of all active environments (function frames) to create the linked list. All of that is required by the function to compute the final answer.
Clearly, the first function takes much less space than the second one.
7. Tulip Mania
Question
Implement flower_keeper
, a function that mutates a tree t
so that the only paths that remain are ones which end in a leaf node with a Tulip flower ('V').
For example, consider this tree where only one path ends in a flower. After calling flower_keeper
, the tree has only three nodes left, the ones that lead to the flower.
The shaded nodes in the diagram indicate paths that end in flowers.
For this tree where two paths end in flowers, the tree keeps both paths that lead to flowers.
For a tree where none of the nodes are flowers, the function removes every branch except the root node.
For a tree with only a single node that is a flower, the function does not remove anything.
Read through the docstring and doctests for additional guidance on completing the implementation of the function. The examples shown above are from the doctests.
def flower_keeper(t):
"""
Mutates the tree T to keep only paths that end in flowers ('V').
If a path consists entirely of stems (''), it must be pruned.
If T has no paths that end in flowers, the root node is still kept.
You can assume that a node with a flower will have no branches.
>>> one_f = Tree('', [Tree('', [Tree(''), Tree('')]), Tree('', [Tree('V'), Tree('')])])
>>> print(one_f)





V

>>> flower_keeper(one_f)
>>> one_f
Tree('', [Tree('', [Tree('V')])])
>>> print(one_f)


V
>>> no_f = Tree('', [Tree('', [Tree(''), Tree('')]), Tree('', [Tree(''), Tree('')])])
>>> flower_keeper(no_f)
>>> no_f
Tree('')
>>> just_f = Tree('V')
>>> flower_keeper(just_f)
>>> just_f
Tree('V')
>>> two_f = Tree('', [Tree('', [Tree('V')]), Tree('', [Tree(''), Tree('V')])])
>>> flower_keeper(two_f)
>>> two_f
Tree('', [Tree('', [Tree('V')]), Tree('', [Tree('V')])])
"""
for b in __________:
(a)
__________
(b)
__________ = [__________ for b in __________ if __________]
(c) (d) (e) (f)
Fill in blank (a).
Fill in blank (b).
Fill in blank (c).
Fill in blank (d).
Fill in blank (e).
Fill in blank (f).
Walkthrough
Observe that this is a mutation function, where we only have to prune the nodes, so it is very likely that our function will not return any explicit value (will return None
). Also, it is guaranteed that flower nodes do not have any branches, which means only leaves will have the label "V"
.
Let’s try to reason from the leapoffaith perspective: given a tree t
, if we call flower_keeper
on its branches b
, what is supposed to happen? (if the function is working correctly)
 Case 1: If the branch is a leaf with
"V"
as a label, we should not mutate it anyhow.  Case 2: if the branch is a leaf with
""
as a label, we also can’t mutate it because per spec: for a tree where none of the nodes are flowers, the function removes every branch except* the root node.* Leaf is also considered to be a tree (where the leaf itself is a root).  Case 3: if the branch is a subtree with its own branches, then our function should get rid of the paths that start from
b
and do not end with label"V"
. Since only leaf nodes can end with"V"
, we know that this subtree’s rootb
has a label""
.
Let’s move further with our leapoffaith. Imagine that branches of t
are mutated (we called flower_keeper
on them and it worked correctly). It means that their subtrees are already taken care of (paths that do not end with "V"
are pruned).
Now, for all the paths that start at node t
, we have to make sure that we only keep ones that end with "V"
. This seems trivial because we already pruned branches of t
, so by just adding an extra node on top of them, newly formed paths should only end with "V"
, right? For cases 1 & 3 mentioned above, it is indeed correct. However, Case 2 dealt with leaf nodes that have a “stem” label, which were not modified. By adding a root node t
on top of them, we create a path that starts at t
and ends with label "I"
! We should filter out these branches by modifying t.branches
to prune such paths.
Let’s reiterate our game plan:
1) Take a leapoffaith and modify the branch subtrees of t
(call flower_keeper
on them)
2) For mutated branches, only keep those branches that either have "V"
as a label (which means they are leaf nodes) or they are subtrees with branches (start at ""
but have their own branches, which means they correspond to Case 3).
Notice that we haven’t wrote a single line of code yet. Instead, we just wondered if our function would work correctly for subtrees of t
, how could we use it to correctly modify t
tree itself.
Skeleton fits great for our logic. With blanks (a) and (b), we make sure to mutate our branches first:
# step 1 of our plan
for b in t.branches: # (a)
flower_keeper(b) # (b)
The last line filters our “nonflower” paths from the mutated branches:
# step 2 of our plan
t.branches = [b for b in t.branches if b.label == 'V' or not b.is_leaf()]
# (c) (d) (e) (f)
Since this line comes after the forloop, t.branches
on blank (e) contain the modified branches.
Predicate on blank (f) only keeps branches with label "V"
or branches that are not leaves (their label is ""
but they have branches). This concludes our solution.
8. CS61A Presents the Game of Hoop
When we introduced the Hog project to you, we designed the rules of the game in a way that would make it possible to implement without using more advanced concepts like OOP and iterators/generators. Now that we've learned these concepts, you can rewrite parts of the game and expand it! The new version, called Hoop, will support any number of players greater than or equal to 2.
Assume the following changes from Hog:
 All rules have been taken out except for the Sow Sad rule, which is reiterated below.
 Each player's
strategy
is a functionstrategy(own_score, other_scores)
that takes in that player's score and a list of the other players' scores, and outputs the number of times that player wishes to roll the dice during their turn. Order doesn't matter for the list of other players' scores.  You don't have to keep track of the leader, and there is no commentary mechanism.
Sow Sad: If a player rolls any number of 1s in their turn, their score for that set of rolls is a 1 regardless of whatever else they rolled.
To start, take a look at the HoopPlayer
class, which represents one player in our game:
class HoopPlayer:
def __init__(self, strategy):
"""Initialize a player with STRATEGY, and a starting SCORE of 0. The
STRATEGY should be a function that takes this player's score and a list
of other players' scores.
"""
self.strategy = strategy
self.score = 0
Every game of Hoop will involve rolling a dice as well. Take a look at theHoopDice
class, which represents a rollable dice that takes a set of values. You'll fill in the blanks in the first part of this question.
class HoopDice:
def __init__(self, values):
"""Initialize a dice with possible values VALUES, and a starting INDEX
of 0. The INDEX indicates which value from VALUES to return when the
dice is rolled next.
"""
self.values = values
self.index = 0
def roll(self):
"""Roll this dice. Advance the index to the next step before returning.
"""
value = ______________
______________ = (______________) % ______________
return value
Part (a)
Begin by making the HoopDice
rollable. Fill in the skeleton for the HoopDice.roll
method below. See above for the rest of HoopDice
.
class HoopDice:
...
def roll(self):
"""Roll this dice. Advance the index to the next step before
returning.
>>> five_six = HoopDice([5, 6])
>>> five_six.roll()
5
>>> five_six.index
1
>>> five_six.roll()
6
>>> five_six.index
0
"""
value = ______________
(1a)
______________ = (______________) % ______________
(1b) (1c) (1d)
return value
 Fill in blank (1a)
 Fill in blank (1b)
 Fill in blank (1c)
 Fill in blank (1d)
Walkthrough
According to the description, this function must do three things:
1) roll the dice
2) advance the index (prepare for the future rolls)
3) return the outcome of the roll from the previous point
value
looks to be the variable that captures the outcome and gets returned. From the doctests, we see that rolling the dice gives the elements from self.values
in order and circles back to start (observe how self.index
changes back to 0
in the doctests).
Therefore, it looks like blank (1a) could be a number from self.values
at the current index. Namely, it should be self.values[self.index]
. The first line and the final return value
achieves the requirements 1 and 3 from above.
For advancing the index, we could do self.index = self.index + 1
, so on the future roll, the roll outcome would be the next element of self.values
. However, if we are already on the last element, incrementing the index would go beyond the bounds of the list. In that case, we have to get back to the index 0
. The skeleton offers us the %
operation for help.
In general, when we mod something by the number N
, the result would always stay in range 0..N1
. Recall that in the past assignments, we’ve used % 10
on the number to get its rightmost digit. Using 10
ensured that we would only get numbers from 09.
To avoid the out of bounds error, we always have to stay in the valid index range  0..len(self.values)
. Therefore, as long as we mod self.index + 1
by length of the list, we ensure that going beyond the length of the list will map back to the appropriate index from the beginning.
The complete solution looks like:
class HoopDice:
...
def roll(self):
value = self.values[self.index]
# (1a)
self.index = (self.index + 1) % len(self.values)
# (1b) (1c) (1d)
return value
Part (b)
For the rest of the question, assume that HoopDice.roll
is implemented correctly, regardless of your answers above.
In the rest of the question, you will work on making the game itself. Take a look at the HoopGame
class, which takes in the setup for your game and makes it playable. You'll fill in the blanks shortly.
class HoopGame:
def __init__(self, players, dice, goal):
"""Initialize a game with a list of PLAYERS, which contains at least one
HoopPlayer, a single HoopDice DICE, and a goal score of GOAL.
"""
self.players = players
self.dice = dice
self.goal = goal
def next_player(self):
"""Infinitely yields the next player in the game, in order."""
yield from ______________
yield from ______________
def get_scores(self):
"""Collects and returns a list of the current scores for all players
in the same order as the SELF.PLAYERS list.
"""
# Implementation omitted. Assume this method works correctly.
def get_scores_except(self, player):
"""Collects and returns a list of the current scores for all players
except PLAYER.
"""
return [______________ for pl in ______________ if ______________]
def roll_dice(self, num_rolls):
"""Simulate rolling SELF.DICE exactly NUM_ROLLS > 0 times. Return sum of
the outcomes unless any of the outcomes is 1. In that case, return 1.
"""
outcomes = [______________ for x in ______________]
ones = [______________ for outcome in outcomes]
return 1 if ______________(ones) else ______________(outcomes)
def play(self):
"""Play the game while no player has reached or exceeded the goal score.
After the game ends, return all players' scores.
"""
player_gen = self.next_player()
while max(self.get_scores()) < self.goal:
player = ______________(player_gen)
other_scores = self.get_scores_except(player)
num_rolls = ______________(player.score, other_scores)
outcome = self.roll_dice(num_rolls)
______________ += outcome
return self.get_scores()
To see what the expected behavior of each method is, take a look at its doctests. These will be provided for the relevant methods in each subpart for the rest of the question.
In all following subparts, assume that the following has already been run to set up the game:
>>> roll_once_strategy = lambda pl, ops: 1
>>> roll_twice_strategy = lambda pl, ops: 2
>>> always_5 = HoopDice([5])
>>> player1 = HoopPlayer(roll_twice_strategy)
>>> player2 = HoopPlayer(roll_once_strategy)
>>> player3 = HoopPlayer(lambda pl, ops: 6)
>>> game = HoopGame([player1, player2, player3], always_5, 55)
>>> # since we omit the implementation of HoopGame.get_scores, here's what it
>>> # should output:
>>> game.get_scores()
[0, 0, 0]
The first HoopGame
method you'll implement is HoopGame.next_player
, which gives the game a way to iterate over all of the players playing, in order to give them each a turn in order.
class HoopGame:
...
def next_player(self):
"""Infinitely yields the next player in the game, in order.
>>> player_gen = game.next_player()
>>> next(player_gen) is player1
True
>>> next(player_gen) is player3
False
>>> next(player_gen) is player3
True
>>> next(player_gen) is player1
True
>>> next(player_gen) is player2
True
>>> new_player_gen = game.next_player()
>>> next(new_player_gen) is player1
True
>>> next(player_gen) is player3
True
"""
yield from ______________
(2a)
yield from ______________
(2b)
 Fill in blank (2a)
 Fill in blank (2b)
Walkthrough
The implementation of this method should ensure two functionalities:
1) yielding players of the instance
2) when there are no more players, start over from the first player and keep yielding. In other words, this generator should be infinite.
Recall that yield from <some generator>
can always be rewritten as:
for elem in <some generator>:
yield elem
In other words, yield from
spits out the elements from the iterator/iterable until it is exhausted. Since we have to yield the players, it would make sense for the blank (2a) to be:
yield from self.players
# (2a)
We’ve fulfilled the first requirement (observe that it has to be self.players
, not just players
, since we are using the attribute of the instance).
How do we deal with the infiniteness property though? We need something like:
yield from self.players
yield from self.players
yield from self.players
yield from self.players
yield from self.players
...
but we have only one spot left for yield from
. Do we have a generator method that yields players infinitely from the start (since after the first yield from
, we have to start over)?
Yes! It is self.next_player()
!
yield from self.next_player()
(2b)
Again, we have to use self
to call the method recursively, since that is how it preserves the “attachment” to its players
attribute.
You might be wondering, haven’t we already “exhausted” self.players
? How come that when we call self.next_player()
again, we are able to start from scratch since it is the same players
list object? Well, when yield from
is used with lists (which is an iterable), it firstly needs to turn it into an iterator:
lst = [1, 2, 3, 4]
yield from lst
# the line above translates into:
yield from iter(lst)
It means that every time we execute the yield from
on a list, it creates a new iterator from its contents. This was reflected in one of the most common student solutions, though it was incorrect:
# incorrect but common solution
class HoopGame:
...
def next_player(self):
yield from self.players
# (2a)
yield from self.players
# (2b)
Since every yield from
line creates its own separate iterator, the implementation above yields the elements for two “rounds”. However, we need infinite number of “rounds”, not only two, which is handled by the recursive call. The final solution looks like:
class HoopGame:
...
def next_player(self):
yield from self.players
# (2a)
yield from self.next_player()
# (2b)
Part (c)
The HoopGame.get_scores
method is already fully implemented and provides a way to get a list of the scores of all players.
However, each player's strategy relies on the player's opponents' scores, so HoopGame
also needs a method that gives the scores of all players except the current one. Fill in the skeleton for HoopGame.get_scores_except
below. Keep in mind that multiple players may have the same score.
class HoopGame:
...
def get_scores_except(self, player):
"""Collects and returns a list of the current scores for all players
except PLAYER.
>>> game.get_scores_except(player2)
[0, 0]
"""
return [______________ for pl in ______________ if ______________]
(3a) (3b) (3c)
As a reminder, here's what the HoopPlayer
class looks like:
class HoopPlayer:
def __init__(self, strategy):
"""Initialize a player with STRATEGY, and a starting SCORE of 0. The
STRATEGY should be a function that takes this player's score and a list
of other players' scores.
"""
self.strategy = strategy
self.score = 0
 Fill in blank (3a)
 Fill in blank (3b)
 Fill in blank (3c)
Walkthrough
The method get_scores_except
should return the list with scores of all players except the provided player
argument. Let’s try to translate this statement into the list comprehension. We can focus on each component separately to fill in the blanks:
 return the list ... of all players except ...
How can we get all of the players? Since get_scores_except
is the method of HoopGame
class, we have access to its attributes. self.players
is exactly what we need and what we put for blank (3b):
return [______________ for pl in self.players if ______________]
# (3a) (3b) (3c)
 return the list with scores of all players except ...
The list should be populated with scores of the players. Since we are iterating over self.players
with the forloop, pl
will refer to an instance of a player. To get their score, we can put pl.score
into blank (3a):
return [pl.score for pl in self.players if ______________]
# (3a) (3b) (3c)
 return the list ... except the provided
player
argument
We should consider all of the players, except the one provided as an argument. So as long as pl
is not player
, we should be fine. The complete solution:
class HoopGame:
...
def get_scores_except(self, player):
return [pl.score for pl in self.players if pl is not player]
# (3a) (3b) (3c)
# since we are comparing objects, we should use "is not" instead of using "!=" (though, in this case, both work)
Part (d)
Next, give HoopGame
the ability to roll its dice some given number of times and return the total from rolling all those times. Recall that the dice in the game is just a single dice, represented by the HoopDice
instance at self.dice
. Fill in the skeleton for HoopGame.roll_dice
below:
class HoopGame:
...
def roll_dice(self, num_rolls):
"""Simulate rolling SELF.DICE exactly NUM_ROLLS > 0 times. Return sum of
the outcomes unless any of the outcomes is 1. In that case, return 1.
>>> game.roll_dice(4)
20
"""
outcomes = [______________ for x in ______________]
(4a) (4b)
ones = [______________ for outcome in outcomes]
(4c)
return 1 if ______________(ones) else ______________(outcomes)
(4d) (4e)
 Fill in blank (4a)
 Fill in blank (4b)
 Fill in blank (4c)
 Fill in blank (4d)
 Fill in blank (4e)
Walkthrough
Recall that self.dice
is where we store the dice instance (self
is referring to HoopGame
class instance). In order to roll the dice once, we have to call self.dice.roll()
, which returns the outcome of the roll. The question asks us to roll the dice num_rolls
times and store the results in outcomes
list:
outcomes = [self.dice.roll() for x in range(num_rolls)]
# (4a) (4b)
# this list comprehension is equivalent to the following code:
outcomes_2 = []
for x in range(num_rolls):
outcome = self.dice.roll()
outcomes_2.append(outcome)
# notice that x variable is not used at all in the list comprehension
# the expression below would evaluate to the same list
[self.dice.roll() for _ in range(num_rolls)]
The initial intuition for the list ones
might be that it needs to have all 1
s from the outcomes list. However, the skeleton does not provide any space for the filtering predicate (outcome == 1
) after the forloop. If we put the predicate as the element description into blank (4c), the list ones
would be populated with True
and False
values (the result of evaluating outcome == 1
for each element of outcomes
):
ones = [outcome == 1 for outcome in outcomes]
# (4c)
As long as we keep in mind that ones
contains boolean values, we should be fine moving forward.
For the last two blanks, the function description actually provides us a huge hint: “Return sum of the outcomes unless any of the outcomes is 1”. It would make sense to return 1
if any(ones)
is True
value (there is at least one True
in ones
) and sum(outcomes)
otherwise:
return 1 if any(ones) else sum(outcomes)
# (4d) (4e)
Notice that using sum(ones)
for blank (4d) also works, because for mathematical purposes, True
is equal to 1
and False
is equal to 0
 this was an alternate solution. The complete solution looks like:
class HoopGame:
...
def roll_dice(self, num_rolls):
"""Simulate rolling SELF.DICE exactly NUM_ROLLS > 0 times. Return sum of
the outcomes unless any of the outcomes is 1. In that case, return 1.
>>> game.roll_dice(4)
20
"""
outcomes = [self.dice.roll() for x in range(num_rolls)]
# (4a) (4b)
ones = [outcome == 1 for outcome in outcomes]
# (4c)
return 1 if any(ones) else sum(outcomes)
# (4d) (4e)
Part (e)
Finally, it's time to play the game! Recall that a player's strategy depends on two inputs: the player's own score, and a list of the scores of the player's opponents. Using existing attributes wherever possible, fill in the skeleton for HoopGame.play
below:
class HoopGame:
...
def play(self):
"""Play the game while no player has reached or exceeded the goal score.
After the game ends, return all players' scores.
>>> game.play()
[20, 10, 60]
"""
player_gen = self.next_player()
while max(self.get_scores()) < self.goal:
player = ______________(player_gen)
(5a)
other_scores = self.get_scores_except(player)
num_rolls = ______________(player.score, other_scores)
(5b)
outcome = self.roll_dice(num_rolls)
______________ += outcome
(5c)
return self.get_scores()
 Fill in blank (5a)
 Fill in blank (5b)
 Fill in blank (5c)
Walkthrough
Before we enter the whileloop, the skeleton creates the generator player_gen
using self.next_player()
. From part (b), we know that this is an infinite generator and the only way to interact with it is to call next
on the object (which yields the next player). This is also our answer for blank (5a):
...
player = next(player_gen)
# (5a)
...
The code in blank (5b) should be a function (the blank is followedup by parentheses) that helps us to figure out the number of rolls based on the player’s score and the list of opponents’ score. We haven’t implemented such function ourselves, but we know that each player has a strategy
attribute, which is defined as “The STRATEGY should be a function that takes this player's score and a list of other players' scores”
. Hence the blank (5b) looks like:
...
num_rolls = player.strategy(player.score, other_scores)
# (5b)
...
# notice that we can't do self.strategy,
# since self here refers to the HoopGame instance
After computing the outcome
, it should impact the current player’s score. This can be achieved by writing player.score
into blank (5c). The complete solution looks like:
class HoopGame:
...
def play(self):
"""Play the game while no player has reached or exceeded the goal score.
After the game ends, return all players' scores.
>>> game.play()
[20, 10, 60]
"""
player_gen = self.next_player()
while max(self.get_scores()) < self.goal:
player = next(player_gen)
# (5a)
other_scores = self.get_scores_except(player)
num_rolls = player.strategy(player.score, other_scores)
# (5b)
outcome = self.roll_dice(num_rolls)
player.score += outcome
# (5c)
return self.get_scores()
Changing the score on blank (5c) also ensures that the whileloop would terminate at some point, since by increasing the score of the current player, we move them closer to the goal.
Part (f)
Now that you've finished implementing the game, you'll implement a new kind of BrokenHoopDice
. This dice extends HoopDice
, but is broken! That is, it alternates between behaving like a normal dice and returning when_broken
value between turns.
For this part of the question, you may not use =
or lambda
.
class BrokenHoopDice(HoopDice):
def __init__(self, values, when_broken):
______________(values)
(6a)
self.when_broken = when_broken
self.______________ = False
(6b)
def roll(self):
"""
>>> broken = BrokenHoopDice([5, 6, 7], 11)
>>> broken.roll()
5
>>> [broken.roll() for _ in range(6)]
[11, 6, 11, 7, 11, 5]
"""
if self.is_broken:
self.is_broken = not self.is_broken
return ______________
(6c)
else:
self.is_broken = not self.is_broken
return ______________()
(6d)
 Fill in blank (6a)
 Fill in blank (6b)
 Fill in blank (6c)
 Fill in blank (6d)
Walkthrough
Since BrokenHoopDice
extends from the HoopDice
, we can use the latter’s constructor to initialize the object. The blank (6a) would be super.__init__(values)
.
After initializing the object as HoopDice
, we create two additional attributes, one of which is when_broken
and we should figure out the name for the second. Looking at the roll
method, we see it uses is_broken
attribute, which seems to be the answer for blank (6b). It is set to be False
since for the first roll, BrokenHoopDice
should behave like a normal dice and turn into broken one for the next roll.
So far, we’ve got the following code:
class BrokenHoopDice(HoopDice):
def __init__(self, values, when_broken):
super().__init__(values)
# (6a)
self.when_broken = when_broken
self.is_broken = False
# (6b)
...
In the roll
method, we see an ifcondition that firstly flips the is_broken
attribute and returns the appropriate roll result. We know that if the dice is broken, we return the value of when_broken
and otherwise, we return the result of a normal HoopDice
roll (observe that blank (6d) ends with function call parentheses). The complete solution looks like:
class BrokenHoopDice(HoopDice):
def __init__(self, values, when_broken):
super().__init__(values)
# (6a)
self.when_broken = when_broken
self.is_broken = False
# (6b)
def roll(self):
"""
>>> broken = BrokenHoopDice([5, 6, 7], 11)
>>> broken.roll()
5
>>> [broken.roll() for _ in range(6)]
[11, 6, 11, 7, 11, 5]
"""
if self.is_broken:
self.is_broken = not self.is_broken
return self.when_broken
# (6c)
else:
self.is_broken = not self.is_broken
return super().roll()
# (6d)