Complete the function prune_small that takes in a Treet and a number n and prunes t mutatively. If t or any of its branches has more than n branches, the n branches with the smallest labels should be kept and any other branches should be pruned, or removed, from the tree
defprune_small(t,n):"""Prune the tree mutatively, keeping only the n branches of each node with the smallest label.>>> t1 = Tree(6)>>> prune_small(t1, 2)>>> t1 Tree(6)>>> t2 = Tree(6, [Tree(3), Tree(4)])>>> prune_small(t2, 1)>>> t2 Tree(6, [Tree(3)])>>> t3 = Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2), Tree(3)]), Tree(5, [Tree(3), Tree(4)])])>>> prune_small(t3, 2)>>> t3 Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2)])]) """while ___________________________: largest =max(_______________, key=____________________) _________________________for __ in _____________: ___________________
Q1: Solution
defprune_small(t,n):"""Prune the tree mutatively, keeping only the n branches of each node with the smallest label.>>> t1 = Tree(6)>>> prune_small(t1, 2)>>> t1 Tree(6)>>> t2 = Tree(6, [Tree(3), Tree(4)])>>> prune_small(t2, 1)>>> t2 Tree(6, [Tree(3)])>>> t3 = Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2), Tree(3)]), Tree(5, [Tree(3), Tree(4)])])>>> prune_small(t3, 2)>>> t3 Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2)])]) """whilelen(t.branches)> n: largest =max(t.branches, key=lambdax: x.label) t.branches.remove(largest)for b in t.branches:prune_small(b, n)
Scheme - Q2: Compose All
Implement compose-all, which takes a list of one-argument functions and returns a one-argument function that applies each function in that list in turn to its argument. For example, if func is the result of calling compose-all on a list of functions (f g h), then (func x) should be equivalent to the result of calling (h (g (f x))).
scm> (define (square x) (* x x))squarescm> (define (add-one x) (+ x 1))add-onescm> (define (double x) (* x 2))doublescm> (define composed (compose-all (list double square add-one)))composedscm> (composed 1)5scm> (composed 2)17
Implement a function insert that takes a Link, a value, and an index, and inserts the value into the Link at the given index. You can assume the linked list already has at least one element. Do not return anything -- insert should mutate the linked list
definsert(link,value,index):"""Insert a value into a Link at the given index.>>> link = Link(1, Link(2, Link(3)))>>> print(link) <1 2 3>>>> insert(link, 9001, 0)>>> print(link) <9001 1 2 3>>>> insert(link, 100, 2)>>> print(link) <9001 1 100 2 3>>>> insert(link, 4, 5) IndexError """"*** YOUR CODE HERE ***"
Q4: Solution
definsert(link,value,index):"""Insert a value into a Link at the given index.>>> link = Link(1, Link(2, Link(3)))>>> print(link) <1 2 3>>>> insert(link, 9001, 0)>>> print(link) <9001 1 2 3>>>> insert(link, 100, 2)>>> print(link) <9001 1 100 2 3>>>> insert(link, 4, 5) IndexError """"*** YOUR CODE HERE ***"if index ==0: old_first = link.first link.first = value new_link =Link(old_first) new_link.rest = link.rest link.rest = new_link i =1while i <= index:if link.rest is Link.empty:raiseIndexErrorif i == index: new_link =Link(value) new_link.rest = link.rest link.rest = new_linkbreak i +=1 link = link.rest
Streams - Q5: Cycles
In Scheme, it's possible to have a stream with cycles. That is, a stream may contain itself as part of the stream definition.
Implement has-cycle?, which returns whether a stream contains a cycle. You may assume that the input is either a stream of some unknown finite length, or is one that contains a cycle. You should implement and use the contains? procedure in your solution. We have provided a skeleton for has-cycle?; your solution must fit on the lines provided.
Hint: A stream has a cycle if you see the same pair object more than once. The built-in procedure eq? may be used to check if two expressions evaluate to the same object in memory.