Lab 7: Linked Lists, Trees / Tree Mutation lab07.zip
What Would Python Display?
Q1: WWPD: Linked Lists
Read over the Link class in lab07.py. Make sure you understand the doctests.
Use Ok to test your knowledge with the following “What Would Python Display?” questions:
1
python3 ok -q link -u
Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed.
If you get stuck, try drawing out the box-and-pointer diagram for the linked list on a piece of paper or loading the Link class into the interpreter with python3 -i lab07.py.
--------------------------------------------------------------------- Link > Suite 1 > Case 3 (cases remaining: 1)
What would Python display? If you get stuck, try it out in the Python interpreter!
>>> from lab07 import * >>> link = Link(5, Link(6, Link(7))) >>> link # Look at the __repr__ method of Link ? Link(5, Link(6, Link(7))) -- OK! --
>>> print(link) # Look at the __str__ method of Link ? <5 6 7> -- OK! --
--------------------------------------------------------------------- OK! All cases for Link unlocked.
Parsons Problems
To work on these problems, open the Parsons editor:
1
python3 parsons
Q2: Reverse Link
Write a function that takes in a linked list and returns a reversed version of that linked list (with elements in the opposite order). It should not mutate the original list.
1 2 3 4 5 6 7 8 9 10
>>> s = Link(1, Link(2, Link(3, Link.empty))) >>> reverse_link(s) Link(3, Link(2, Link(1))) >>> s Link(1, Link(2, Link(3))) >>> k = Link(3, Link(5, Link(7, Link(9)))) >>> reverse_link(k) Link(9, Link(7, Link(5, Link(3)))) >>> k Link(3, Link(5, Link(7, Link(9))))
Hint: you should iterate over the linked list. If you’re having trouble starting, attempt to replicate the following diagram.
defreverse_link(lnk): """ Given a linked list lnk, return a new linked list which has all the elements of lnk but in reverse order. >>> s = Link(1, Link(2, Link(3, Link.empty))) >>> reverse_link(s) Link(3, Link(2, Link(1))) >>> s Link(1, Link(2, Link(3))) >>> k = Link(3, Link(5, Link(7, Link(9)))) >>> reverse_link(k) Link(9, Link(7, Link(5, Link(3)))) >>> k Link(3, Link(5, Link(7, Link(9)))) """ "*** YOUR CODE HERE ***" result = Link.empty while lnk: result = Link(lnk.first, result) lnk = lnk.rest return result
Q3: Label Multiplier
Write a function label_multiplier that takes in a Tree and an integer val. label_multiplier should mutate the tree’s labels by multiplying their original value by val.
defstore_digits(n): """Stores the digits of a positive number n in a linked list. >>> s = store_digits(1) >>> s Link(1) >>> store_digits(2345) Link(2, Link(3, Link(4, Link(5)))) >>> store_digits(876) Link(8, Link(7, Link(6))) >>> # a check for restricted functions >>> import inspect, re >>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(store_digits))) >>> print("Do not use str or reversed!") if any([r in cleaned for r in ["str", "reversed"]]) else None >>> link1 = Link(3, Link(Link(4), Link(5, Link(6)))) """ "*** YOUR CODE HERE ***" lnk = Link.empty while n: lnk = Link(n % 10, lnk) n = n // 10 return lnk
Use Ok to test your code:
1
python3 ok -q store_digits✂️
Q5: Cumulative Mul
Write a function cumulative_mul that mutates the Tree t so that each node’s label becomes the product of its label and all labels in the subtrees rooted at the node.
Hint: Consider carefully when to do the mutation of the tree and whether that mutation should happen before or after processing the subtrees.
defcumulative_mul(t): """Mutates t so that each node's label becomes the product of all labels in the corresponding subtree rooted at t. >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)]) >>> cumulative_mul(t) >>> t Tree(105, [Tree(15, [Tree(5)]), Tree(7)]) >>> otherTree = Tree(2, [Tree(1, [Tree(3), Tree(4), Tree(5)]), Tree(6, [Tree(7)])]) >>> cumulative_mul(otherTree) >>> otherTree Tree(5040, [Tree(60, [Tree(3), Tree(4), Tree(5)]), Tree(42, [Tree(7)])]) """ "*** YOUR CODE HERE ***" if t.is_leaf(): return for b in t.branches: cumulative_mul(b) ifisinstance(b, Tree): t.label *= b.label
Use Ok to test your code:
1
python3 ok -q cumulative_mul✂️
Submit
Make sure to submit this assignment by running:
1
python3 ok --submit
Optional Questions
Q6: Cycles
The Link class can represent lists with cycles. That is, a list may contain itself as a sublist.
1 2 3 4
>>> s = Link(1, Link(2, Link(3))) >>> s.rest.rest.rest = s >>> s.rest.rest.rest.rest.rest.first 3
Implement has_cycle,that returns whether its argument, a Link instance, contains a cycle.
Hint: Iterate through the linked list and try keeping track of which Link objects you’ve already seen.
defhas_cycle(link): """Return whether link contains a cycle. >>> s = Link(1, Link(2, Link(3))) >>> s.rest.rest.rest = s >>> has_cycle(s) True >>> t = Link(1, Link(2, Link(3))) >>> has_cycle(t) False >>> u = Link(2, Link(2, Link(2))) >>> has_cycle(u) False """ "*** YOUR CODE HERE ***" links = [] while link isnot Link.empty: if link in links: returnTrue links.append(link) link = link.rest returnFalse
Use Ok to test your code:
1
python3 ok -q has_cycle✂️
Extra challenge (Optional): Implement has_cycle without keeping track of all Link objects you’ve already seen. The solution is short (less than 20 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around.
defhas_cycle_constant(link): """Return whether link contains a cycle. >>> s = Link(1, Link(2, Link(3))) >>> s.rest.rest.rest = s >>> has_cycle_constant(s) True >>> t = Link(1, Link(2, Link(3))) >>> has_cycle_constant(t) False """ "*** YOUR CODE HERE ***" slow = link fast = link while fast isnot Link.empty: if fast.rest is Link.empty: returnFalse slow = slow.rest fast = fast.rest.rest if slow is fast: returnTrue returnFalse