Exam: CS61A Summer 2020 Midterm
Name: Solution Key
Email: example_key
secure
Point breakdown
q1: 1.0/1
Score:
Total: 1.0
Reskeletonized solution follows
==================================================
def cat(password, limit):
" Write a higher-order function `cat` that returns a one-argument\n funct¶
ion `attempt`. Every time `attempt` is called, it checks to see if its argument\¶
n matches the password at the corresponding index.\n\n If the password ent¶
irely matches, return a success string. If more than `limit`\n number of inco¶
rrect hacks are attempted, you should return an error string.\n For details, ¶
see the doctest.\n\n\n Note: to comment out a blank that covers an entire lin¶
e, just put down 'unnecessary' (with quotes)\n\n >>> hacker = cat([1,2], 2)\n¶
>>> hacker(1)\n >>> hacker(2)\n 'Successfully unlocked!'\n >>> hack¶
er = cat([1,2], 1)\n >>> hacker(1)\n >>> hacker(3) # used up attempts to g¶
ain access\n >>> hacker(2) # correct attempt to gain access, but already lock¶
ed\n 'The safe is now inaccessible!'\n >>> hacker = cat([1,2], 2)\n >>>¶
hacker(1)\n >>> hacker(3) # 1 attempt left to gain access\n >>> hacker(2)¶
# correct attempt to gain access\n 'Successfully unlocked!'\n "
num_incorrect = 0
index = 0
def attempt(digit):
nonlocal num_incorrect
nonlocal index
if (num_incorrect >= limit):
return 'The safe is now inaccessible!'
if (password[index] == digit):
index += 1
if (index == len(password)):
return 'Successfully unlocked!'
else:
num_incorrect += 1
return attempt
==================================================
Original code follows
==================================================
def cat(password, limit):
""" Write a higher-order function `cat` that returns a one-argument
function `attempt`. Every time `attempt` is called, it checks to see if its ¶
argument
matches the password at the corresponding index.
If the password entirely matches, return a success string. If more than `lim¶
it`
number of incorrect hacks are attempted, you should return an error string.
For details, see the doctest.
Note: to comment out a blank that covers an entire line, just put down 'unne¶
cessary' (with quotes)
>>> hacker = cat([1,2], 2)
>>> hacker(1)
>>> hacker(2)
'Successfully unlocked!'
>>> hacker = cat([1,2], 1)
>>> hacker(1)
>>> hacker(3) # used up attempts to gain access
>>> hacker(2) # correct attempt to gain access, but already locked
'The safe is now inaccessible!'
>>> hacker = cat([1,2], 2)
>>> hacker(1)
>>> hacker(3) # 1 attempt left to gain access
>>> hacker(2) # correct attempt to gain access
'Successfully unlocked!'
"""
num_incorrect = 0
index = 0
def attempt(digit):
nonlocal num_incorrect
nonlocal index
if num_incorrect >= limit:
return 'The safe is now inaccessible!'
if password[index] == digit:
index += 1
if index == len(password):
return "Successfully unlocked!"
else:
num_incorrect += 1
return attempt
==================================================


schedule
Point breakdown
q2: 1.0/1
Score:
Total: 1.0
Reskeletonized solution follows
==================================================
def schedule(galaxy, sum_to, max_digit):
'\n A \'galaxy\' is a string which contains either digits or \'?\'s.\n\n ¶
A \'completion\' of a galaxy is a string that is the same as galaxy, except\n¶
with digits replacing each of the \'?\'s.\n\n Your task in this question ¶
is to find all completions of the given `galaxy`\n that use digits up to `max¶
_digit`, and whose digits sum to `sum_to`.\n\n Note 1: the function int can b¶
e used to convert a string to an integer and str\n can be used to convert¶
an integer to a string as such:\n\n >>> int("5")\n 5\n >>>¶
str(5)\n \'5\'\n\n Note 2: Indexing and slicing can be used on string¶
s as well as on lists.\n\n >>> \'evocative\'[3]\n \'c\'\n >¶
>> \'evocative\'[3:]\n \'cative\'\n >>> \'evocative\'[:6]\n ¶
\'evocat\'\n >>> \'evocative\'[3:6]\n \'cat\'\n\n\n >>> schedu¶
le(\'?????\', 25, 5)\n [\'55555\']\n >>> schedule(\'???\', 5, 2)\n [\'1¶
22\', \'212\', \'221\']\n >>> schedule(\'?2??11?\', 5, 3)\n [\'0200111\', ¶
\'0201110\', \'0210110\', \'1200110\']\n '
def schedule_helper(galaxy, sum_sofar, index):
if ((index >= len(galaxy)) and (sum_sofar == sum_to)):
return [galaxy]
elif ((sum_sofar > sum_to) or (index >= len(galaxy))):
return []
elif (galaxy[index] != '?'):
return schedule_helper(galaxy, (sum_sofar + int(galaxy[index])), (in¶
dex + 1))
ans = []
for x in range((max_digit + 1)):
modified_galaxy = ((galaxy[:index] + str(x)) + galaxy[(index + 1):])¶
ans += schedule_helper(modified_galaxy, (sum_sofar + x), (index + 1)¶
)
return ans
return schedule_helper(galaxy, 0, 0)
==================================================
Original code follows
==================================================
def schedule(galaxy, sum_to, max_digit):
"""
A 'galaxy' is a string which contains either digits or '?'s.
A 'completion' of a galaxy is a string that is the same as galaxy, except
with digits replacing each of the '?'s.
Your task in this question is to find all completions of the given `galaxy`
that use digits up to `max_digit`, and whose digits sum to `sum_to`.
Note 1: the function int can be used to convert a string to an integer and s¶
tr
can be used to convert an integer to a string as such:
>>> int("5")
5
>>> str(5)
'5'
Note 2: Indexing and slicing can be used on strings as well as on lists.
>>> 'evocative'[3]
'c'
>>> 'evocative'[3:]
'cative'
>>> 'evocative'[:6]
'evocat'
>>> 'evocative'[3:6]
'cat'
>>> schedule('?????', 25, 5)
['55555']
>>> schedule('???', 5, 2)
['122', '212', '221']
>>> schedule('?2??11?', 5, 3)
['0200111', '0201110', '0210110', '1200110']
"""
def schedule_helper(galaxy, sum_sofar, index):
if index >= len(galaxy) and sum_sofar == sum_to:
return [galaxy]
elif sum_sofar > sum_to or index >= len(galaxy):
return []
elif galaxy[index] != '?':
return schedule_helper(galaxy, sum_sofar + int(galaxy[index]), index¶
+ 1)
ans = []
for x in range(max_digit + 1):
modified_galaxy = galaxy[:index] + str(x) + galaxy[index + 1:]
ans += schedule_helper(modified_galaxy, sum_sofar + x, index + 1)
return ans
return schedule_helper(galaxy, 0, 0)
==================================================



consume
Point breakdown
q3: 1.0/1
Score:
Total: 1.0
Reskeletonized solution follows
==================================================
'\nLet a `painting` be a self-referential function that\n - takes in one inte¶
ger\n - returns two values, another painting and well as an integer\n\nFor an¶
example see the function `identity_painting` below.\n\nYou have two tasks in th¶
is assignment, to implement the functions `microscope`\nand `plush`. Both have t¶
heir behavior defined by their doctests.\n\nIt is not necessary to implement `mi¶
croscope` correctly to get the points for\n`plush`. However, the ok test cases f¶
or `plush` will fail if you have not correctly\nimplemented `microscope`.\n'
def identity_painting(x):
return (identity_painting, x)
def microscope(a=0, s=1):
'\n This function returns a painting function that processes a sequence\n¶
of integers, and returns the alternating sum of all integers seen thus\n ¶
far (see doctest for an example).\n\n >>> painting_a = microscope()\n >>> ¶
painting_b, x = painting_a(2)\n >>> x # 2\n¶
2\n >>> painting_c, x = painting_b(8)\n >>> x ¶
# 2 - 8\n -6\n >>> painting_d, x = painting_c(12)\n >>> x ¶
# 2 - 8 + 12\n 6\n >>> painting_e, x = pain¶
ting_d(30)\n >>> x # 2 - 8 + 12 - 30\n -¶
24\n >>> painting_b_again, x = painting_a(100)\n >>> x ¶
# 100 [note that we are using painting_a not painting_d here]\n ¶
100\n '
def painting(x):
return (microscope((a + (s * x)), (- s)), (a + (s * x)))
return painting
def plush(painting, items):
'\n The function `plush` takes in a `painting` and a nonempty list of `it¶
ems` and\n runs the given `painting` on each of the `items` in turn, returnin¶
g the final\n numeric result.\n\n For example, on the items [1, 2, 3, 4, 5¶
] with the painting microscope\n we return 1 - 2 + 3 - 4 + 5 = 3\n\n >>> p¶
lush(microscope(), [1, 2, 3, 4, 5])\n 3\n >>> plush(microscope(), [4000])\¶
n 4000\n >>> plush(microscope(), [2, 90])\n -88\n >>> plush(identity¶
_painting, [2, 90])\n 90\n '
(painting, x) = painting(items[0])
if (len(items) == 1):
return x
return plush(painting, items[1:])
==================================================
Original code follows
==================================================
"""
Let a `painting` be a self-referential function that
- takes in one integer
- returns two values, another painting and well as an integer
For an example see the function `identity_painting` below.
You have two tasks in this assignment, to implement the functions `microscope`
and `plush`. Both have their behavior defined by their doctests.
It is not necessary to implement `microscope` correctly to get the points for
`plush`. However, the ok test cases for `plush` will fail if you have not correc¶
tly
implemented `microscope`.
"""
def identity_painting(x):
return identity_painting, x
def microscope(a=0, s=1):
"""
This function returns a painting function that processes a sequence
of integers, and returns the alternating sum of all integers seen thus
far (see doctest for an example).
>>> painting_a = microscope()
>>> painting_b, x = painting_a(2)
>>> x # 2
2
>>> painting_c, x = painting_b(8)
>>> x # 2 - 8
-6
>>> painting_d, x = painting_c(12)
>>> x # 2 - 8 + 12
6
>>> painting_e, x = painting_d(30)
>>> x # 2 - 8 + 12 - 30
-24
>>> painting_b_again, x = painting_a(100)
>>> x # 100 [note that we are using painti¶
ng_a not painting_d here]
100
"""
def painting(x):
return microscope(a + s * x, -s), a + s * x
return painting
def plush(painting, items):
"""
The function `plush` takes in a `painting` and a nonempty list of `items` an¶
d
runs the given `painting` on each of the `items` in turn, returning the fina¶
l
numeric result.
For example, on the items [1, 2, 3, 4, 5] with the painting microscope
we return 1 - 2 + 3 - 4 + 5 = 3
>>> plush(microscope(), [1, 2, 3, 4, 5])
3
>>> plush(microscope(), [4000])
4000
>>> plush(microscope(), [2, 90])
-88
>>> plush(identity_painting, [2, 90])
90
"""
painting, x = painting(items[0])
if len(items) == 1:
return x
return plush(painting, items[1:])
==================================================


exact_copy
Point breakdown
q4: 1.0/1
Score:
Total: 1.0
Reskeletonized solution follows
==================================================
def lemon(xv):
'\n A lemon-copy is a perfect replica of a nested list\'s box-and-pointer¶
structure.\n If an environment diagram were drawn out, the two should be¶
entirely\n separate but identical.\n\n A `xv` is a list that only con¶
tains ints and other lists.\n\n The function `lemon` generates a lemon-copy o¶
f the given list `xv`.\n\n Note: The `isinstance` function takes in a value a¶
nd a type and determines\n whether the value is of the given type. So\n\n¶
>>> isinstance("abc", str)\n True\n >>> isinstance("abc", ¶
list)\n False\n\n Here\'s an example, where lemon_y = lemon(y)\n\n\n ¶
+-----+-----+ +-----+-----+-----+\n ¶
| | | | | | |\n ¶
| + | +-------------> | 200 | 300 | + |\n y +------¶
----------> | | | | | | | | |\n ¶
+-----+-----+ +--> +-----+-----+-----+\n lemon_y +-+ ¶
| | ^ |\n | +--¶
--------------+ | |\n | ¶
+-----------+\n |\n | +¶
-----+-----+ +-----+-----+-----+\n | | ¶
| | | | | |\n +-------> | + | +-¶
------------> | 200 | 300 | + |\n | | | | ¶
| | | | |\n +-----+-----+ +¶
--> +-----+-----+-----+\n | | ¶
^ |\n +----------------+ | ¶
|\n +-----------+\¶
n\n >>> x = [200, 300]\n >>> x.append(x)\n >>> y = [x, x] ¶
# this is the `y` from the doctests\n >>> lemon_y = lemon(y) # this is t¶
he `lemon_y` from the doctests\n >>> # check that lemon_y has the same struct¶
ure as y\n >>> len(lemon_y)\n 2\n >>> lemon_y[0] is lemon_y[1]\n Tru¶
e\n >>> len(lemon_y[0])\n 3\n >>> lemon_y[0][0]\n 200\n >>> lemon¶
_y[0][1]\n 300\n >>> lemon_y[0][2] is lemon_y[0]\n True\n >>> # chec¶
k that lemon_y and y have no list objects in common\n >>> lemon_y is y\n F¶
alse\n >>> lemon_y[0] is y[0]\n False\n '
lemon_lookup = []
def helper(xv):
if isinstance(xv, int):
return xv
for old_new in lemon_lookup:
if (old_new[0] is xv):
return old_new[1]
new_xv = []
lemon_lookup.append((xv, new_xv))
for element in xv:
new_xv.append(helper(element))
return new_xv
return helper(xv)
==================================================
Original code follows
==================================================
def lemon(xv):
"""
A lemon-copy is a perfect replica of a nested list's box-and-pointer structu¶
re.
If an environment diagram were drawn out, the two should be entirely
separate but identical.
A `xv` is a list that only contains ints and other lists.
The function `lemon` generates a lemon-copy of the given list `xv`.
Note: The `isinstance` function takes in a value and a type and determines
whether the value is of the given type. So
>>> isinstance("abc", str)
True
>>> isinstance("abc", list)
False
Here's an example, where lemon_y = lemon(y)
+-----+-----+ +-----+-----+-----+
| | | | | | |
| + | +-------------> | 200 | 300 | + |
y +----------------> | | | | | | | | |
+-----+-----+ +--> +-----+-----+-----+
lemon_y +-+ | | ^ |
| +----------------+ | |
| +-----------+
|
| +-----+-----+ +-----+-----+-----+
| | | | | | | |
+-------> | + | +-------------> | 200 | 300 | + |
| | | | | | | | |
+-----+-----+ +--> +-----+-----+-----+
| | ^ |
+----------------+ | |
+-----------+
>>> x = [200, 300]
>>> x.append(x)
>>> y = [x, x] # this is the `y` from the doctests
>>> lemon_y = lemon(y) # this is the `lemon_y` from the doctests
>>> # check that lemon_y has the same structure as y
>>> len(lemon_y)
2
>>> lemon_y[0] is lemon_y[1]
True
>>> len(lemon_y[0])
3
>>> lemon_y[0][0]
200
>>> lemon_y[0][1]
300
>>> lemon_y[0][2] is lemon_y[0]
True
>>> # check that lemon_y and y have no list objects in common
>>> lemon_y is y
False
>>> lemon_y[0] is y[0]
False
"""
lemon_lookup = []
def helper(xv):
if isinstance(xv, int):
return xv
for old_new in lemon_lookup:
if old_new[0] is xv:
return old_new[1]
new_xv = []
lemon_lookup.append((xv, new_xv))
for element in xv:
new_xv.append(helper(element))
return new_xv
return helper(xv)
==================================================


nth_repeating_seq
Point breakdown
q5: 1.0/1
Score:
Total: 1.0
Reskeletonized solution follows
==================================================
def subsaltshaker(disk):
"\n A 'saltshaker' is a sequence of digits of length `d` composed entirel¶
y of the digit `d`. Examples include\n 1\n 4444\n 7777777\n¶
\n Note that `1 <= d <= 9`; there are no 0-length saltshakers.\n\n Your ta¶
sk is to implement the `subsaltshaker` function, which takes in an integer `disk¶
` and returns\n whether `disk` contains a saltshaker as a consecutive sub¶
integer of its digits.\n\n >>> subsaltshaker(2233) # 22 counts\n True\n ¶
>>> subsaltshaker(2444423) # 4444 counts\n True\n >>> subsaltshaker(82223¶
) # 22 counts even if it appears as part of 222\n True\n >>> subsaltshaker¶
(234562) # 2...2 does not count if the 2s are not consecutive\n False\n >>¶
> subsaltshaker(1) # 1 counts\n True\n >>> subsaltshaker(498729879871) # 1¶
counts\n True\n >>> subsaltshaker(149872987987) # 1 counts\n True\n ¶
>>> subsaltshaker(4445555) # no saltshakers in this number\n False\n >>> ¶
subsaltshaker(20) # no saltshakers in this number\n False\n "
current_digit = (disk % 10)
count = 0
while (disk != 0):
last = (disk % 10)
if (current_digit == last):
count += 1
else:
count = 1
current_digit = last
if (count == current_digit):
return True
disk = (disk // 10)
return False
==================================================
Original code follows
==================================================
def subsaltshaker(disk):
"""
A 'saltshaker' is a sequence of digits of length `d` composed entirely of th¶
e digit `d`. Examples include
1
4444
7777777
Note that `1 <= d <= 9`; there are no 0-length saltshakers.
Your task is to implement the `subsaltshaker` function, which takes in an in¶
teger `disk` and returns
whether `disk` contains a saltshaker as a consecutive subinteger of its ¶
digits.
>>> subsaltshaker(2233) # 22 counts
True
>>> subsaltshaker(2444423) # 4444 counts
True
>>> subsaltshaker(82223) # 22 counts even if it appears as part of 222
True
>>> subsaltshaker(234562) # 2...2 does not count if the 2s are not consecuti¶
ve
False
>>> subsaltshaker(1) # 1 counts
True
>>> subsaltshaker(498729879871) # 1 counts
True
>>> subsaltshaker(149872987987) # 1 counts
True
>>> subsaltshaker(4445555) # no saltshakers in this number
False
>>> subsaltshaker(20) # no saltshakers in this number
False
"""
current_digit = disk % 10
count = 0
while disk != 0:
last = disk % 10
if current_digit == last:
count += 1
else:
count = 1
current_digit = last
if count == current_digit:
return True
disk = disk // 10
return False
==================================================



copycat
Point breakdown
q6: 1.0/1
Score:
Total: 1.0
Reskeletonized solution follows
==================================================
def copycat(lst1, lst2):
"\n Write a function `copycat` that takes in two lists.\n `lst1` i¶
s a list of strings\n `lst2` is a list of integers\n\n It returns a ne¶
w list where every element from `lst1` is copied the\n number of times as the¶
corresponding element in `lst2`. If the number\n of times to be copied is ne¶
gative (-k), then it removes the previous\n k elements added.\n\n Note 1: ¶
`lst1` and `lst2` do not have to be the same length, simply ignore\n any extr¶
a elements in the longer list.\n\n Note 2: you can assume that you will never¶
be asked to delete more\n elements than exist\n\n\n >>> copycat(['a', 'b'¶
, 'c'], [1, 2, 3])\n ['a', 'b', 'b', 'c', 'c', 'c']\n >>> copycat(['a', 'b¶
', 'c'], [3])\n ['a', 'a', 'a']\n >>> copycat(['a', 'b', 'c'], [0, 2, 0])\¶
n ['b', 'b']\n >>> copycat([], [1,2,3])\n []\n >>> copycat(['a', 'b'¶
, 'c'], [1, -1, 3])\n ['c', 'c', 'c']\n "
def copycat_helper(lst1, lst2, lst_so_far):
if ((len(lst1) == 0) or (len(lst2) == 0)):
return lst_so_far
if (lst2[0] >= 0):
lst_so_far = (lst_so_far + [lst1[0] for _ in range(lst2[0])])
else:
lst_so_far = lst_so_far[:lst2[0]]
return copycat_helper(lst1[1:], lst2[1:], lst_so_far)
return copycat_helper(lst1, lst2, [])
==================================================
Original code follows
==================================================
def copycat(lst1, lst2):
"""
Write a function `copycat` that takes in two lists.
`lst1` is a list of strings
`lst2` is a list of integers
It returns a new list where every element from `lst1` is copied the
number of times as the corresponding element in `lst2`. If the number
of times to be copied is negative (-k), then it removes the previous
k elements added.
Note 1: `lst1` and `lst2` do not have to be the same length, simply ignore
any extra elements in the longer list.
Note 2: you can assume that you will never be asked to delete more
elements than exist
>>> copycat(['a', 'b', 'c'], [1, 2, 3])
['a', 'b', 'b', 'c', 'c', 'c']
>>> copycat(['a', 'b', 'c'], [3])
['a', 'a', 'a']
>>> copycat(['a', 'b', 'c'], [0, 2, 0])
['b', 'b']
>>> copycat([], [1,2,3])
[]
>>> copycat(['a', 'b', 'c'], [1, -1, 3])
['c', 'c', 'c']
"""
def copycat_helper(lst1, lst2, lst_so_far):
if len(lst1) == 0 or len(lst2) == 0:
return lst_so_far
if lst2[0] >= 0:
lst_so_far = lst_so_far + [lst1[0] for _ in range(lst2[0])]
else:
lst_so_far = lst_so_far[:lst2[0]]
return copycat_helper(lst1[1:], lst2[1:], lst_so_far)
return copycat_helper(lst1, lst2, [])
==================================================



flatmap_tree
Point breakdown
q7: 1.0/1
Score:
Total: 1.0
Reskeletonized solution follows
==================================================
def village(apple, t):
'\n The `village` operation takes\n a function `apple` that maps a¶
n integer to a tree where\n every label is an integer.\n a tre¶
e `t` whose labels are all integers\n\n And applies `apple` to every label in¶
`t`.\n\n To recombine this tree of trees into a a single tree,\n simp¶
ly copy all its branches to each of the leaves\n of the new tree.\n\n ¶
For example, if we have\n apple(x) = tree(x, [tree(x + 1), tree(x + 2)])\¶
n and\n t = 10\n / 20 ¶
30\n\n We should get the output\n\n village(apple, t)\n = ¶
10\n / ¶
/ 11 12\n / ¶
\\ / 20 30 20 30\n ¶
/ \\ / \\ / \\ / 21 22 31 32 21 22 31 ¶
32\n >>> t = tree(10, [tree(20), tree(30)])\n >>> apple = lambda x: tree(x¶
, [tree(x + 1), tree(x + 2)])\n >>> print_tree(village(apple, t))\n 10\n ¶
11\n 20\n 21\n 22\n 30\n 31\n ¶
32\n 12\n 20\n 21\n 22\n 30\n ¶
31\n 32\n '
def graft(t, bs):
'\n Grafts the given branches `bs` onto each leaf\n of the¶
given tree `t`, returning a new tree.\n '
if is_leaf(t):
return tree(label(t), bs)
new_branches = [graft(b, bs) for b in branches(t)]
return tree(label(t), new_branches)
base_t = apple(label(t))
bs = [village(apple, b) for b in branches(t)]
return graft(base_t, bs)
def tree(label, branches=[]):
'Construct a tree with the given label value and a list of branches.'
for branch in branches:
assert is_tree(branch), 'branches must be trees'
return ([label] + list(branches))
def label(tree):
'Return the label value of a tree.'
return tree[0]
def branches(tree):
'Return the list of branches of the given tree.'
return tree[1:]
def is_tree(tree):
'Returns True if the given tree is a tree, and False otherwise.'
if ((type(tree) != list) or (len(tree) < 1)):
return False
for branch in branches(tree):
if (not is_tree(branch)):
return False
return True
def is_leaf(tree):
"Returns True if the given tree's list of branches is empty, and False\n ¶
otherwise.\n "
return (not branches(tree))
def print_tree(t, indent=0):
'Print a representation of this tree in which each node is\n indented by ¶
two spaces times its depth from the entry.\n '
print(((' ' * indent) + str(label(t))))
for b in branches(t):
print_tree(b, (indent + 1))
==================================================
Original code follows
==================================================
def village(apple, t):
"""
The `village` operation takes
a function `apple` that maps an integer to a tree where
every label is an integer.
a tree `t` whose labels are all integers
And applies `apple` to every label in `t`.
To recombine this tree of trees into a a single tree,
simply copy all its branches to each of the leaves
of the new tree.
For example, if we have
apple(x) = tree(x, [tree(x + 1), tree(x + 2)])
and
t = 10
/ \
20 30
We should get the output
village(apple, t)
= 10
/ \
/ \
11 12
/ \ / \
20 30 20 30
/ \ / \ / \ / \
21 22 31 32 21 22 31 32
>>> t = tree(10, [tree(20), tree(30)])
>>> apple = lambda x: tree(x, [tree(x + 1), tree(x + 2)])
>>> print_tree(village(apple, t))
10
11
20
21
22
30
31
32
12
20
21
22
30
31
32
"""
def graft(t, bs):
"""
Grafts the given branches `bs` onto each leaf
of the given tree `t`, returning a new tree.
"""
if is_leaf(t):
return tree(label(t), bs)
new_branches = [graft(b, bs) for b in branches(t)]
return tree(label(t), new_branches)
base_t = apple(label(t))
bs = [village(apple, b) for b in branches(t)]
return graft(base_t, bs)
def tree(label, branches=[]):
"""Construct a tree with the given label value and a list of branches."""
for branch in branches:
assert is_tree(branch), 'branches must be trees'
return [label] + list(branches)
def label(tree):
"""Return the label value of a tree."""
return tree[0]
def branches(tree):
"""Return the list of branches of the given tree."""
return tree[1:]
def is_tree(tree):
"""Returns True if the given tree is a tree, and False otherwise."""
if type(tree) != list or len(tree) < 1:
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return True
def is_leaf(tree):
"""Returns True if the given tree's list of branches is empty, and False
otherwise.
"""
return not branches(tree)
def print_tree(t, indent=0):
"""Print a representation of this tree in which each node is
indented by two spaces times its depth from the entry.
"""
print(' ' * indent + str(label(t)))
for b in branches(t):
print_tree(b, indent + 1)
==================================================