[CS61A]lab05

Lab05: http://gaotx.com/cs61a/lab/lab05/
My Solution: http://gaotx.com/blogs/2015/05/16/cs61a-lab05/

lab05
## Trees, Dictionaries ##

#########
# Trees #
#########

import inspect
# Tree definition - same Data Abstraction but different implementation from lecture
def tree(root, branches=[]):
    #for branch in branches:
    # assert is_tree(branch)
    return lambda dispatch: root if dispatch == 'root' else list(branches)

def root(tree):
    return tree('root')

def branches(tree):
    return tree('branches')

def is_tree(tree):
    try:
        tree_data = inspect.getargspec(tree)
        assert tree_data == inspect.getargspec(lambda dispatch: None)
        return all([is_tree(branch) for branch in branches(tree)])
    except:
        return False

def is_leaf(tree):
    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 root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(root(t)))
    for branch in branches(t):
        print_tree(branch, indent + 1)

numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])


# Q1
def countdown_tree():
    """Return a tree that has the following structure.

    >>> print_tree(countdown_tree())
    10
      9
        8
      7
        6
          5
    """
    "*** YOUR CODE HERE ***"
    return tree(10, [tree(9, [tree(8)]), tree(7,[tree(6, [tree(5)])])])

# Q2
def size_of_tree(t):
    """Return the number of entries in the tree.

    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> size_of_tree(numbers)
    7
    """
    "*** YOUR CODE HERE ***"
    branches_num = 0
    for branch in branches(t):
        branch_num += size_of_tree(branch)  
    return branches_num + 1

################
# Dictionaries #
################

# Q3
def counter(message):
    """ Returns a dictionary of each word in message mapped
    to the number of times it appears in the input string.

    >>> x = counter('to be or not to be')
    >>> x['to']
    2
    >>> x['be']
    2
    >>> x['not']
    1
    >>> y = counter('run forrest run')
    >>> y['run']
    2
    >>> y['forrest']
    1
    """
    word_list = message.split()
    "*** YOUR CODE HERE ***"
    dict = {}
    for word in word_list:
        if word in dict:
            dict[word] += 1
        else:
            dict[word] = 1
    return dict


extra
from lab05 import *


## Extra Trees, Dictionaries Questions ##

#########
# Trees #
#########

# Q5
def height(t):
    """Return the depth of the deepest node in the tree.

    >>> height(tree(1))
    0
    >>> height(tree(1, [tree(2), tree(3)]))
    1
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> height(numbers)
    2
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return 0
    depth = 0
    for branch in branches(t):
        depth = max(depth, height(branch))
    return depth + 1

# Q6
def acorn_finder(t):
    """Returns True if t contains a node with the value 'acorn' and
    False otherwise.

    >>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('acorn')]), tree('branch2')])
    >>> acorn_finder(sproul)
    True
    >>> acorn_finder(numbers)
    False
    """
    "*** YOUR CODE HERE ***"
    if root(t) == 'acorn':
        return True
    else:
        for branch in branches(t):
            if acorn_finder(branch) == True:
                return True
    return False

# Q7
def preorder(t):
    """Return a list of the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> preorder(numbers)
    [1, 2, 3, 4, 5, 6, 7]
    >>> preorder(tree(2, [tree(4, [tree(6)])]))
    [2, 4, 6]
    """
    "*** YOUR CODE HERE ***"
    if branches(t) == []:
        return [root(t)]
    pre = []
    for branch in branches(t):
        pre += preorder(branch)
    return [root(t)] + pre

################
# Dictionaries #
################

# Q8
def build_successors_table(tokens):
    """Return a dictionary: keys are words; values are lists of
    successors.

    >>> text = ['We', 'came', 'to', 'investigate', ',', 'catch', 'bad', 'guys', 'and', 'to', 'eat', 'pie', '.']
    >>> table = build_successors_table(text)
    >>> sorted(table)
    [',', '.', 'We', 'and', 'bad', 'came', 'catch', 'eat', 'guys', 'investigate', 'pie', 'to']
    >>> table['to']
    ['investigate', 'eat']
    >>> table['pie']
    ['.']
    >>> table['.']
    ['We']
    """
    table = {}
    prev = '.'
    for word in tokens:
        if prev not in table:
            "*** YOUR CODE HERE ***"
            table[prev] = []
        "*** YOUR CODE HERE ***"
        table[prev].append(word)
        prev = word
    return table

# Q9
def construct_sent(word, table):
    """Prints a random sentence starting with word, sampling from
    table.
    """
    import random
    result = ' '
    while word not in ['.', '!', '?']:
        "*** YOUR CODE HERE ***"
        result += word + ''
        word = random.choice(table[word])
    return result + word

# Warning: do NOT try to print the return result of this function
def shakespeare_tokens(path='shakespeare.txt', url='http://goo.gl/SztLfX'):
    """Return the words of Shakespeare's plays as a list."""
    import os
    from urllib.request import urlopen
    if os.path.exists(path):
        return open('shakespeare.txt', encoding='ascii').read().split()
    else:
        shakespeare = urlopen(url)
        return shakespeare.read().decode(encoding='ascii').split()

# Uncomment the following two lines
# tokens = shakespeare_tokens()
# table = build_successors_table(tokens)

def random_sent():
    import random
    return construct_sent(random.choice(table['.']), table)


extra里面还有些不理解

楼主 求问reading链接没问题吗~~
一直都打不开好着急嗷嗷嗷嗷

TammyChow 发表于 2015-5-23 16:39
楼主 求问reading链接没问题吗~~
一直都打不开好着急嗷嗷嗷嗷

似乎好多国内的同学都看不了，有另一本书，但是那本书是scheme，不是Python的，内容一样。你可以去cs61a.org看一下，其实光看lecture我觉得就够了

EXTRA里的来不及做了，就先交这些吧


## Trees, Dictionaries ##

#########
# Trees #
#########

import inspect
# Tree definition - same Data Abstraction but different implementation from lecture
def tree(root, branches=[]):
    #for branch in branches:
    # assert is_tree(branch)
    return lambda dispatch: root if dispatch == 'root' else list(branches)

def root(tree):
    return tree('root')

def branches(tree):
    return tree('branches')

def is_tree(tree):
    try:
        tree_data = inspect.getargspec(tree)
        assert tree_data == inspect.getargspec(lambda dispatch: None)
        return all([is_tree(branch) for branch in branches(tree)])
    except:
        return False

def is_leaf(tree):
    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 root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(root(t)))
    for branch in branches(t):
        print_tree(branch, indent + 1)

numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])


# Q1
def countdown_tree():
    """Return a tree that has the following structure.

    >>> print_tree(countdown_tree())
    10
      9
        8
      7
        6
          5
    """
    "*** YOUR CODE HERE ***"
    return tree(10,[tree(9,[tree(8)]),tree(7,[tree(6,[tree(5)])])])

# Q2
def size_of_tree(t):
    """Return the number of entries in the tree.

    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> size_of_tree(numbers)
    7
    """
    "*** YOUR CODE HERE ***"
    i = 1
    if not is_leaf(t):
        for branch in branches(t):
            i += size_of_tree(branch)
    return i
        

################
# Dictionaries #
################

# Q3
def counter(message):
    """ Returns a dictionary of each word in message mapped
    to the number of times it appears in the input string.

    >>> x = counter('to be or not to be')
    >>> x['to']
    2
    >>> x['be']
    2
    >>> x['not']
    1
    >>> y = counter('run forrest run')
    >>> y['run']
    2
    >>> y['forrest']
    1
    """
    word_list = message.split()
    "*** YOUR CODE HERE ***"
    l = {}
    for word in word_list:
        if word not in l:
            l[word]=1
        else:
            l[word]+=1
    return l

# Q1
def countdown_tree():
    """Return a tree that has the following structure.

    >>> print_tree(countdown_tree())
    10
      9
        8
      7
        6
          5
    """
    "*** YOUR CODE HERE ***"
    return tree(10, [tree(9, [tree(8)]), tree(7, [tree(6, [tree(5)])])])

# Q2
def size_of_tree(t):
    """Return the number of entries in the tree.

    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> size_of_tree(numbers)
    7
    """
    "*** YOUR CODE HERE ***"
    return 1 + sum([size_of_tree(t) for t in branches(t)])

################
# Dictionaries #
################

# Q3
def counter(message):
    """ Returns a dictionary of each word in message mapped
    to the number of times it appears in the input string.

    >>> x = counter('to be or not to be')
    >>> x['to']
    2
    >>> x['be']
    2
    >>> x['not']
    1
    >>> y = counter('run forrest run')
    >>> y['run']
    2
    >>> y['forrest']
    1
    """
    word_list = message.split()
    "*** YOUR CODE HERE ***"
    dic = {}
    for word in word_list:
        if word in dic:
            dic[word] += 1
        else:
            dic[word] = 1
    return dic

from lab05 import *

## Extra Trees, Dictionaries Questions ##

#########
# Trees #
#########

# Q5
def height(t):
    """Return the depth of the deepest node in the tree.

    >>> height(tree(1))
    0
    >>> height(tree(1, [tree(2), tree(3)]))
    1
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> height(numbers)
    2
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return 0
    return 1 + max([height(subtree) for subtree in branches(t)])

# Q6
def acorn_finder(t):
    """Returns True if t contains a node with the value 'acorn' and
    False otherwise.

    >>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('acorn')]), tree('branch2')])
    >>> acorn_finder(sproul)
    True
    >>> acorn_finder(numbers)
    False
    """
    "*** YOUR CODE HERE ***"
    if root(t) == 'acorn':
        return True
    else:
        for branch in branches(t):
            if acorn_finder(branch) == True:
                return True
        return False


# Q7
def preorder(t):
    """Return a list of the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> preorder(numbers)
    [1, 2, 3, 4, 5, 6, 7]
    >>> preorder(tree(2, [tree(4, [tree(6)])]))
    [2, 4, 6]
    """
    "*** YOUR CODE HERE ***"
    if branches(t) == []:
        return [root(t)]
    orged_branches = []
    for branch in branches(t):
        orged_branches += preorder(branch)
    return [root(t)] + orged_branches

################
# Dictionaries #
################

# Q8
def build_successors_table(tokens):
    """Return a dictionary: keys are words; values are lists of
    successors.

    >>> text = ['We', 'came', 'to', 'investigate', ',', 'catch', 'bad', 'guys', 'and', 'to', 'eat', 'pie', '.']
    >>> table = build_successors_table(text)
    >>> sorted(table)
    [',', '.', 'We', 'and', 'bad', 'came', 'catch', 'eat', 'guys', 'investigate', 'pie', 'to']
    >>> table['to']
    ['investigate', 'eat']
    >>> table['pie']
    ['.']
    >>> table['.']
    ['We']
    """
    table = {}
    prev = '.'
    for word in tokens:
        if prev not in table:
            "*** YOUR CODE HERE ***"
            table[prev] = []
        "*** YOUR CODE HERE ***"
        table[prev].append(word)
        prev = word
    return table

# Q9
def construct_sent(word, table):
    """Prints a random sentence starting with word, sampling from
    table.
    """
    import random
    result = ' '
    while word not in ['.', '!', '?']:
        "*** YOUR CODE HERE ***"
        result += word + ''
        word = random.choice(table[word])
    return result + word

关于树的内容上次作业基本都做过，倒是list那题想了一会，代码：
## Trees, Dictionaries ##

#########
# Trees #
#########

import inspect
# Tree definition - same Data Abstraction but different implementation from lecture
def tree(root, branches=[]):
    #for branch in branches:
    # assert is_tree(branch)
    return lambda dispatch: root if dispatch == 'root' else list(branches)

def root(tree):
    return tree('root')

def branches(tree):
    return tree('branches')

def is_tree(tree):
    try:
        tree_data = inspect.getargspec(tree)
        assert tree_data == inspect.getargspec(lambda dispatch: None)
        return all([is_tree(branch) for branch in branches(tree)])
    except:
        return False

def is_leaf(tree):
    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 root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(root(t)))
    for branch in branches(t):
        print_tree(branch, indent + 1)

numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])


# Q1
def countdown_tree():
    """Return a tree that has the following structure.

    >>> print_tree(countdown_tree())
    10
      9
        8
      7
        6
          5
    """
    "*** YOUR CODE HERE ***"
    return tree(10, [tree(9,[tree(8)]),tree(7,[tree(6,[tree(5)])])])

# Q2
def size_of_tree(t):
    """Return the number of entries in the tree.

    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> size_of_tree(numbers)
    7
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return 1
    return 1 + sum(size_of_tree(subtree) for subtree in branches(t))

################
# Dictionaries #
################

# Q3
def counter(message):
    """ Returns a dictionary of each word in message mapped
    to the number of times it appears in the input string.

    >>> x = counter('to be or not to be')
    >>> x['to']
    2
    >>> x['be']
    2
    >>> x['not']
    1
    >>> y = counter('run forrest run')
    >>> y['run']
    2
    >>> y['forrest']
    1
    """
    word_list = message.split()
    "*** YOUR CODE HERE ***"
    dict = {}
    for word in word_list:
        if word in dict:
            dict[word] += 1
        else:
            dict[word] = 1
    return dict
   
   

因为赶进度，制作了必做的部分， extra没有写

代码：

1. ## Trees, Dictionaries ##
   
2. 
   
3. #########
   
4. # Trees #
   
5. #########
   
6. 
   
7. import inspect
   
8. # Tree definition - same Data Abstraction but different implementation from lecture
   
9. def tree(root, branches=[]):
   
10.     #for branch in branches:
    
11.     # assert is_tree(branch)
    
12.     return lambda dispatch: root if dispatch == 'root' else list(branches)
    
13. 
    
14. def root(tree):
    
15.     return tree('root')
    
16. 
    
17. def branches(tree):
    
18.     return tree('branches')
    
19. 
    
20. def is_tree(tree):
    
21.     try:
    
22.         tree_data = inspect.getargspec(tree)
    
23.         assert tree_data == inspect.getargspec(lambda dispatch: None)
    
24.         return all([is_tree(branch) for branch in branches(tree)])
    
25.     except:
    
26.         return False
    
27. 
    
28. def is_leaf(tree):
    
29.     return not branches(tree)
    
30. 
    
31. def print_tree(t, indent=0):
    
32.     """Print a representation of this tree in which each node is
    
33.     indented by two spaces times its depth from the root.
    
34. 
    
35.     >>> print_tree(tree(1))
    
36.     1
    
37.     >>> print_tree(tree(1, [tree(2)]))
    
38.     1
    
39.       2
    
40.     >>> print_tree(numbers)
    
41.     1
    
42.       2
    
43.       3
    
44.         4
    
45.         5
    
46.       6
    
47.         7
    
48.     """
    
49.     print('  ' * indent + str(root(t)))
    
50.     for branch in branches(t):
    
51.         print_tree(branch, indent + 1)
    
52. 
    
53. numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    
54. 
    
55. 
    
56. # Q1
    
57. def countdown_tree():
    
58.     """Return a tree that has the following structure.
    
59. 
    
60.     >>> print_tree(countdown_tree())
    
61.     10
    
62.       9
    
63.         8
    
64.       7
    
65.         6
    
66.           5
    
67.     """
    
68.     "*** YOUR CODE HERE ***"
    
69.     return tree(10, [tree(9, [tree(8)]), tree(7, [tree(6, [tree(5)])])])
    
70. 
    
71. # Q2
    
72. def size_of_tree(t):
    
73.     """Return the number of entries in the tree.
    
74. 
    
75.     >>> print_tree(numbers)
    
76.     1
    
77.       2
    
78.       3
    
79.         4
    
80.         5
    
81.       6
    
82.         7
    
83.     >>> size_of_tree(numbers)
    
84.     7
    
85.     """
    
86.     "*** YOUR CODE HERE ***"
    
87.     if is_leaf(t):
    
88.         return 1
    
89.     else:
    
90.         return 1 + sum([size_of_tree(node) for node in branches(t)])
    
91. 
    
92. ################
    
93. # Dictionaries #
    
94. ################
    
95. 
    
96. # Q3
    
97. def counter(message):
    
98.     """ Returns a dictionary of each word in message mapped
    
99.     to the number of times it appears in the input string.
    
100. 
     
101.     >>> x = counter('to be or not to be')
     
102.     >>> x['to']
     
103.     2
     
104.     >>> x['be']
     
105.     2
     
106.     >>> x['not']
     
107.     1
     
108.     >>> y = counter('run forrest run')
     
109.     >>> y['run']
     
110.     2
     
111.     >>> y['forrest']
     
112.     1
     
113.     """
     
114.     word_list = message.split()
     
115.     "*** YOUR CODE HERE ***"
     
116.     my_dict = dict()
     
117.     for word in word_list:
     
118.         if word in my_dict:
     
119.             my_dict[word] += 1
     
120.         else:
     
121.             my_dict[word] = 1
     
122. 
     
123.     return my_dict
     

复制代码

## Trees, Dictionaries ##

#########
# Trees #
#########

import inspect
# Tree definition - same Data Abstraction but different implementation from lecture
def tree(root, branches=[]):
    #for branch in branches:
    # assert is_tree(branch)
    return lambda dispatch: root if dispatch == 'root' else list(branches)

def root(tree):
    return tree('root')

def branches(tree):
    return tree('branches')

def is_tree(tree):
    try:
        tree_data = inspect.getargspec(tree)
        assert tree_data == inspect.getargspec(lambda dispatch: None)
        return all([is_tree(branch) for branch in branches(tree)])
    except:
        return False

def is_leaf(tree):
    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 root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(root(t)))
    for branch in branches(t):
        print_tree(branch, indent + 1)

numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])


# Q1
def countdown_tree():
    """Return a tree that has the following structure.

    >>> print_tree(countdown_tree())
    10
      9
        8
      7
        6
          5
    """
    "*** YOUR CODE HERE ***"
    return tree(10, [tree(9, [tree(8)]), tree(7, [tree(6, [tree(5)])])])

# Q2
def size_of_tree(t):
    """Return the number of entries in the tree.

    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> size_of_tree(numbers)
    7
    """
    "*** YOUR CODE HERE ***"
    entry_sum = 1
    for entry in branches(t):
        entry_sum += size_of_tree(entry)
    return entry_sum

################
# Dictionaries #
################

# Q3
def counter(message):
    """ Returns a dictionary of each word in message mapped
    to the number of times it appears in the input string.

    >>> x = counter('to be or not to be')
    >>> x['to']
    2
    >>> x['be']
    2
    >>> x['not']
    1
    >>> y = counter('run forrest run')
    >>> y['run']
    2
    >>> y['forrest']
    1
    """
    word_list = message.split()
    "*** YOUR CODE HERE ***"
    result = {}
    for word in word_list:
        if word in result:
            result[word] += 1
        else:
            result[word] = 1
    return result
from lab05 import *

## Extra Trees, Dictionaries Questions ##

#########
# Trees #
#########

# Q5
def height(t):
    """Return the depth of the deepest node in the tree.

    >>> height(tree(1))
    0
    >>> height(tree(1, [tree(2), tree(3)]))
    1
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> height(numbers)
    2
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return 0
    depth = 0
    for branch in branches(t):
        depth = max(depth, height(branch))
    return depth + 1

# Q6
def acorn_finder(t):
    """Returns True if t contains a node with the value 'acorn' and
    False otherwise.

    >>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('acorn')]), tree('branch2')])
    >>> acorn_finder(sproul)
    True
    >>> acorn_finder(numbers)
    False
    """
    "*** YOUR CODE HERE ***"
    if root(t) == 'acorn':
        return True
    for branch in branches(t):
        if acorn_finder(branch) == True:
            return True
    return False



# Q7
def preorder(t):
    """Return a list of the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> preorder(numbers)
    [1, 2, 3, 4, 5, 6, 7]
    >>> preorder(tree(2, [tree(4, [tree(6)])]))
    [2, 4, 6]
    """
    "*** YOUR CODE HERE ***"
    if branches(t) == []:
        return [root(t)]
    print_order = []
    for branch in branches(t):
        print_order += preorder(branch)
    return [root(t)] + print_order



################
# Dictionaries #
################

# Q8
def build_successors_table(tokens):
    """Return a dictionary: keys are words; values are lists of
    successors.

    >>> text = ['We', 'came', 'to', 'investigate', ',', 'catch', 'bad', 'guys', 'and', 'to', 'eat', 'pie', '.']
    >>> table = build_successors_table(text)
    >>> sorted(table)
    [',', '.', 'We', 'and', 'bad', 'came', 'catch', 'eat', 'guys', 'investigate', 'pie', 'to']
    >>> table['to']
    ['investigate', 'eat']
    >>> table['pie']
    ['.']
    >>> table['.']
    ['We']
    """
    table = {}
    prev = '.'
    for word in tokens:
        if prev not in table:
            "*** YOUR CODE HERE ***"
            table[prev] = []
        "*** YOUR CODE HERE ***"
        table[prev].append(word)
        prev = word
    return table

# Q9
def construct_sent(word, table):
    """Prints a random sentence starting with word, sampling from
    table.
    """
    import random
    result = ' '
    while word not in ['.', '!', '?']:
        "*** YOUR CODE HERE ***"
        result += word + ' '
        word = randon.choice(table[word])
    return result + word

# Warning: do NOT try to print the return result of this function
def shakespeare_tokens(path='shakespeare.txt', url='http://goo.gl/SztLfX'):
    """Return the words of Shakespeare's plays as a list."""
    import os
    from urllib.request import urlopen
    if os.path.exists(path):
        return open('shakespeare.txt', encoding='ascii').read().split()
    else:
        shakespeare = urlopen(url)
        return shakespeare.read().decode(encoding='ascii').split()

# Uncomment the following two lines
# tokens = shakespeare_tokens()
# table = build_successors_table(tokens)

def random_sent():
    import random
    return construct_sent(random.choice(table['.']), table)

现在做完的还能加分吗？这是我的code：
""" Lab 05: Mutable Sequences and Trees """
# Q2
def map(fn, seq):
    """Applies fn onto each element in seq and returns a list.

    >>> map(lambda x: x*x, [1, 2, 3])
    [1, 4, 9]
    """
    "*** YOUR CODE HERE ***"
    return [fn(x) for x in seq]

def filter(pred, seq):
    """Keeps elements in seq only if they satisfy pred.

    >>> filter(lambda x: x % 2 == 0, [1, 2, 3, 4])
    [2, 4]
    """
    "*** YOUR CODE HERE ***"
    return [x for x in seq if pred(x)==True]

def reduce(combiner, seq):
    """Combines elements in seq using combiner.

    >>> reduce(lambda x, y: x + y, [1, 2, 3, 4])
    10
    >>> reduce(lambda x, y: x * y, [1, 2, 3, 4])
    24
    >>> reduce(lambda x, y: x * y, [4])
    4
    """
    "*** YOUR CODE HERE ***"
    total = seq[0]
    for elem in seq[1:]:
        total = combiner(total, elem)
    return total

# Q3
def acorn_finder(t):
    """Returns True if t contains a node with the value 'acorn' and
    False otherwise.

    >>> scrat = tree('acorn')
    >>> acorn_finder(scrat)
    True
    >>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('acorn')]), tree('branch2')])
    >>> acorn_finder(sproul)
    True
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> acorn_finder(numbers)
    False
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t) and label(t)=='acorn' :
        return True
    elif True in ( [acorn_finder(b) for b in branches(t)] ):
        return True
    else:
        return False

# Q4
def replace_leaf(t, old, new):
    """Returns a new tree where every leaf value equal to old has
    been replaced with new.

    >>> yggdrasil = tree('odin',
    ...                  [tree('balder',
    ...                        [tree('thor'),
    ...                         tree('loki')]),
    ...                   tree('frigg',
    ...                        [tree('thor')]),
    ...                   tree('thor',
    ...                        [tree('sif'),
    ...                         tree('thor')]),
    ...                   tree('thor')])
    >>> laerad = copy_tree(yggdrasil) # copy yggdrasil for testing purposes
    >>> print_tree(replace_leaf(yggdrasil, 'thor', 'freya'))
    odin
      balder
        freya
        loki
      frigg
        freya
      thor
        sif
        freya
      freya
    >>> laerad == yggdrasil # Make sure original tree is unmodified
    True
    """
    "*** YOUR CODE HERE ***"

# Tree ADT
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 root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(label(t)))
    for b in branches(t):
        print_tree(b, indent + 1)

def copy_tree(t):
    """Returns a copy of t. Only for testing purposes.

    >>> t = tree(5)
    >>> copy = copy_tree(t)
    >>> t = tree(6)
    >>> print_tree(copy)
    5
    """
    return tree(label(t), [copy_tree(b) for b in branches(t)])


def make_withdraw(balance):

    def withdraw(amount):
        nonlocal balance
        balance = balance - amount
        return balance

    return withdraw