This question uses the following tree data abstraction.
def tree(entry, children=[]):
return [entry, children]
def entry(tree):
return tree[0]
def children(tree):
return tree[1]
Define the function track_lineage
that takes in a tree of strings family_tree
and a string name
. Assume that there is a unique node with entry name
. track_lineage
returns a list with the entries of the parent and grandparent of that node. If the node with entry name does not have a parent or grandparent, return None
for that element in the list. See the doctests for details. Do not violate abstraction barriers. You may only use the lines provided. You may not need to fill all the lines.
def track_lineage(family_tree, name):
"""
Return the entries of the parent and grandparent of the node with entry name in family_tree.
>>> t = tree('Tytos', [
... tree('Tywin', [
... tree('Cersei'), tree('Jaime'), tree('Tyrion')
... ]),
... tree('Kevan', [
... tree('Lancel'), tree('Martyn'), tree('Willem')
... ])])
>>> track_lineage(t, 'Tywin')
['Tytos', None]
>>> track_lineage(t, 'Tytos')
[None, None]
"""
def tracker(t, p, gp):
if
for c in children(t):
return tracker(, , )
Assuming that track_lineage
works correctly, define the function are cousins that takes in a tree of strings family_tree
and two strings name1
and name2
and returns True
if the node with entry name1
and the node with entry name2
are cousins in family_tree
. Assume that there are unique nodes with entries name1
and name2
in family_tree
. See the doctests for details. Two nodes are cousins if they have the same grandparent but different parents.
You may only use the lines provided. You may not need to fill all the lines.
def are_cousins(family_tree, name1, name2):
"""Return True if a node with entry name1 is a cousin of a node with entry name2 in family_tree.
>>> are_cousins(t, ‘Kevan’, ‘Tytos’) # same tree as before False
>>> are_cousins(t, ‘Cersei’, ‘Lancel’)
True
>>> are_cousins(t, ‘Jaime’, ‘Lancel’)
True
>>> are_cousins(t, ‘Jaime’, ‘Tyrion’)
False
"""
A GrootTree
g
is a binary tree that has an attribute parent
. Its parent is the GrootTree
in which g
is a branch. If a GrootTree
instance is not a branch of any other GrootTree
instance, then its parent is BinaryTree.empty
.
BinaryTree.empty
should not have a parent
attribute. Assume that every GrootTree
instance is a branch of at most one other GrootTree
instance and not a branch of any other kind of tree.
Fill in the blanks below so that the parent
attribute is set correctly. You may not need to use all of the lines. Indentation is allowed. You should not include any assert
statements. Using your solution, the doctests for fib_groot
should pass.
class GrootTree(BinaryTree):
"""A binary tree with a parent."""
def __init__(self, entry, left=BinaryTree.empty, right=BinaryTree.empty):
BinaryTree.__init__(self, entry, left, right)
def fib_groot(n):
"""
Return a Fibonacci GrootTree.
>>> t = fib_groot(3)
>>> t.entry
2
>>> t.parent.is_empty
True
>>> t.left.parent.entry
2
>>> t.right.left.parent.right.parent.entry
1
"""
if n == 0 or n == 1:
return GrootTree(n)
else:
left, right = fib_groot(n - 2), fib_groot(n - 1)
return GrootTree(left.entry + right.entry, left, right)
Fill in the blanks of the implementation of paths
, a function that takes two arguments: a GrootTree
instance g
and a list s
. It returns the number of paths through g
whose entries are the elements of s
. A path through a GrootTree
can extend either to a branch or its parent
.
You may assume that the GrootTree
class is implemented correctly and that the list s
is non-empty.
There are two paths for [2, 1, 2, 1, 0]
, one path for [2, 1, 0, 1, 0]
in the tree below:
2 +-------+ 1 1 +---+ 0 1
def paths(g, s):
"""
The number of paths through g with entries s.
>>> t = fib_groot(3)
>>> paths(t, [1])
0
>>> paths(t, [2])
1
>>> paths(t, [2, 1, 2, 1, 0])
2
>>> paths(t, [2, 1, 0, 1, 0])
1
>>> paths(t, [2, 1, 2, 1, 2, 1])
8
"""
if g is BinaryTree.empty :
return 0
elif :
return 1
else:
xs = []
return sum([ for x in xs])
Implement decrypt
, which takes a string s
and a dictionary d
that contains words as values and their secret codes as keys. It returns a list of all possible ways in which s
can be decoded by splitting it into secret codes and separating the corresponding words by spaces.
def decrypt(s, d):
"""
List all possible decoded strings of s.
>>> codes = {
... 'alan': 'spooky',
... 'al': 'drink',
... 'antu': 'your',
... 'turing': 'ghosts',
... 'tur': 'scary',
... 'ing': 'skeletons',
... 'ring': 'ovaltine'
... }
>>> decrypt('alanturing', codes)
['drink your ovaltine', 'spooky ghosts', 'spooky scary skeletons']
"""
if s == '':
return []
ms = []
if :
ms.append()
for k in :
first , suffix = s[:k], s[k:]
if :
for rest in :
ms.append()
return ms