Midterm 2 Walkthrough
1. A Bug’s Life
Wasp
Richard is trying to write a generator function that maps a given iterable using a one-argument 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 eThis means that we can rewrite Richard’s function as:
def map_gen(fn, iterable):
for it in iterable:
for e in fn(it):
yield eFrom 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) * 100i. (0.5 pt) Melanie runs the following code expecting to see it return 50.0, since 392.5 is a half-empty cyl (or is it half-full?).
>>> 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 numberBumblebee
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 resi. (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 for-loop 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 if-condition 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 4-th 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 box-and-pointer 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
lst1with numbers from 1-10. - Step 2:
removemethod modifies the list by removing the first occurrence of the argument (1in this case), going left to right. So1gets removed fromlst1. However, the call toremovewill evaluate toNoneand that is the final value ofnumber_onevariable. - Step 3:
popdeletes the last element of the list and also returns that last element, settingsome_numbervariable to10. Afterremove(1), followed bypop(),lst1has numbers from 2 to 9. - Step 4: we create variable
lst2which just points to the same list object aslst1. - Step 5: we are creating a copy of
lst2with slicing and sincelst2refers tolst1, we copy its contents to form a new list object.lst3will point to that object. - Step 6:
insertmethod 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 7-13: 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 fromlst1and populates the list with them. The last three elements (counting from backwards sincepopdeletes the last element every time it gets called) fromlst1form 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 fromlst1in the past). Therefore,lst1loses three elements and looks like[2, 3, 4, 5, lst3, 6], whilelst3gains three elements and now is[2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7]. - Step 14:
appendadds its argument as a single element intolst2. What is the argument? The result of evaluatinglst1.remove(lst3)). From step 2, we know thatremovewill just delete the first occurrence oflst3, which is at index4oflst1. After deleting that element, the remove method returnsNone. Solst1loses one more element, but gainsNonesince we are executinglst2.append(None)(lst1andlst2are 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 upper-bound 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 -> 3Recall that repr delivers the representation which could be used to re-create 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 re-create 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 string-creation 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 objectThe 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 leap-of-faith!
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 (leap-of-faith!), 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.emptyFull 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 Tree-tionaries
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 resFill 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
resand ends by returning it. This means that every recursive call to functionfiletree_to_dictwill 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 resThe final thing we have to do now is to populate the nested dictionary, which should happen in the for-loop 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 for-loop, 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 (leap-of-faith 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 above-mentioned 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 else-case (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 res6. 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_list1in 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 for-loop would increase proportionally (i.e. if lnk had 10 more elements, the for-loop 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 while-loop 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 while-loop. 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 leap-of-faith 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
band do not end with label"V". Since only leaf nodes can end with"V", we know that this subtree’s rootbhas a label"|".
Let’s move further with our leap-of-faith. 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 leap-of-faith 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 “non-flower” 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 for-loop, 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
strategyis 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 = 0Every 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 valuePart (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..N-1. 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 0-9.
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 valuePart (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 elemIn 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 for-loop, 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
playerargument
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 for-loop. 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 while-loop, 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 followed-up 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 instanceAfter 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 while-loop 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 if-condition 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)