-
Notifications
You must be signed in to change notification settings - Fork 0
/
hw8.py
291 lines (231 loc) · 8.13 KB
/
hw8.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
"""Homework 8: Sets"""
"""Fill in the missing implementations of set operations below. This file
already contains the implementations presented in lecture. Missing
implementations are marked with "*** YOUR CODE HERE ***" strings.
"""
# Take 2: Sets as ordered sequences
def empty(s):
return len(s) == 0
def set_contains2(s, v):
"""Return true if set s contains value v as an element.
>>> set_contains2(s, 2)
True
>>> set_contains2(s, 5)
False
"""
if empty(s) or s.first > v:
return False
if s.first == v:
return True
return set_contains2(s.rest, v)
def adjoin_set2(s, v):
"""Return a set containing all elements of s and element v.
>>> adjoin_set2(s, 2.5)
Rlist(1, Rlist(2, Rlist(2.5, Rlist(3))))
"""
"*** YOUR CODE HERE ***"
if set_contains2(s, v):
return s
elif empty(s):
return v
else:
if s.first > v:
return Rlist(v, s)
else:
return Rlist(s.first, adjoin_set2(s.rest, v))
def intersect_set2(set1, set2):
"""Return a set containing all elements common to set1 and set2.
>>> t = Rlist(2, Rlist(3, Rlist(4)))
>>> intersect_set2(s, t)
Rlist(2, Rlist(3))
"""
if empty(set1) or empty(set2):
return Rlist.empty
e1, e2 = set1.first, set2.first
if e1 == e2:
return Rlist(e1, intersect_set2(set1.rest, set2.rest))
if e1 < e2:
return intersect_set2(set1.rest, set2)
if e2 < e1:
return intersect_set2(set1, set2.rest)
def union_set2(set1, set2):
"""Return a set containing all elements either in set1 or set2.
>>> t = Rlist(1, Rlist(3, Rlist(5)))
>>> union_set2(s, t)
Rlist(1, Rlist(2, Rlist(3, Rlist(5))))
"""
"*** YOUR CODE HERE ***"
s1f, s2f = set1.first, set2.first
if set_contains2(set1, s2f) == False:
return Rlist(s2f, )
# Take 3: Sets as trees
def set_contains3(s, v):
"""Return true if set s contains value v as an element.
>>> t = Tree(2, Tree(1), Tree(3))
>>> set_contains3(t, 3)
True
>>> set_contains3(t, 0)
False
>>> set_contains3(big_tree(20, 60), 34)
True
"""
if s is None:
return False
if s.entry == v:
return True
if s.entry < v:
return set_contains3(s.right, v)
if s.entry > v:
return set_contains3(s.left, v)
def adjoin_set3(s, v):
"""Return a set containing all elements of s and element v.
>>> b = big_tree(0, 9)
>>> b
Tree(4, Tree(1), Tree(7, None, Tree(9)))
>>> adjoin_set3(b, 5)
Tree(4, Tree(1), Tree(7, Tree(5), Tree(9)))
"""
if s is None:
return Tree(v)
if s.entry == v:
return s
if s.entry < v:
return Tree(s.entry, s.left, adjoin_set3(s.right, v))
if s.entry > v:
return Tree(s.entry, adjoin_set3(s.left, v), s.right)
def depth(s, v):
"""Return the depth of the value v in tree set s.
The depth of a value is the number of branches followed to reach the value.
The depth of the root of a tree is always 0.
>>> b = big_tree(0, 9)
>>> depth(b, 4)
0
>>> depth(b, 7)
1
>>> depth(b, 9)
2
"""
"*** YOUR CODE HERE ***"
def tree_to_ordered_sequence(s):
"""Return an ordered sequence containing the elements of tree set s.
Challenge: implement this operation to run in Theta(length of s).
>>> b = big_tree(0, 9)
>>> tree_to_ordered_sequence(b)
Rlist(1, Rlist(4, Rlist(7, Rlist(9))))
"""
"*** YOUR CODE HERE ***"
def ordered_sequence_to_tree(s):
"""Return a balanced tree containing the elements of ordered Rlist s.
A tree is balanced if the lengths of the paths from the root to any two
leaves are at most one apart.
Note: this implementation is complete, but the definition of partial_tree
below is not complete.
>>> ordered_sequence_to_tree(Rlist(1, Rlist(2, Rlist(3))))
Tree(2, Tree(1), Tree(3))
>>> b = big_tree(0, 20)
>>> elements = tree_to_ordered_sequence(b)
>>> elements
Rlist(1, Rlist(4, Rlist(7, Rlist(10, Rlist(13, Rlist(16, Rlist(19)))))))
>>> ordered_sequence_to_tree(elements)
Tree(10, Tree(4, Tree(1), Tree(7)), Tree(16, Tree(13), Tree(19)))
"""
return partial_tree(s, len(s))[0]
def partial_tree(s, n):
"""Return a balanced tree of the first n elements of Rlist s, along with
the rest of s. A tree is balanced if the length of the path to any two
leaves are at most one apart.
Hint: This function requires two recursive calls. The first call builds a
left branch out of the first left_size elements of s; Then, the next elemnt
is used as the entry of the returned tree. Finally, the second recursive
call builds the right branch out of the next right_size elements. In
total, (left_size + 1 + right_size) = n, where 1 is for the entry.
Challenge: Implement partial_tree to run in Theta(n) time.
>>> s = Rlist(1, Rlist(2, Rlist(3, Rlist(4, Rlist(5)))))
>>> partial_tree(s, 3)
(Tree(2, Tree(1), Tree(3)), Rlist(4, Rlist(5)))
"""
if n == 0:
return None, s
left_size = (n-1)//2
right_size = n - left_size - 1
"*** YOUR CODE HERE ***"
def intersect_set3(set1, set2):
"""Return a set containing all elements common to set1 and set2.
Note: If tree_to_ordered_sequence and ordered_sequence_to_tree run in
linear time, then so does intersect_set3.
>>> s, t = big_tree(0, 12), big_tree(6, 18)
>>> intersect_set3(s, t)
Tree(8, Tree(6), Tree(10, None, Tree(12)))
"""
s1, s2 = map(tree_to_ordered_sequence, (set1, set2))
return ordered_sequence_to_tree(intersect_set2(s1, s2))
def union_set3(set1, set2):
"""Return a set containing all elements either in set1 or set2.
Note: If tree_to_ordered_sequence and ordered_sequence_to_tree run in
linear time, then so does union_set3.
>>> s, t = big_tree(6, 12), big_tree(10, 16)
>>> union_set3(s, t)
Tree(10, Tree(6, None, Tree(9)), Tree(13, Tree(11), Tree(15)))
"""
s1, s2 = map(tree_to_ordered_sequence, (set1, set2))
return ordered_sequence_to_tree(union_set2(s1, s2))
# From lecture 22: Recursive lists and trees
class Rlist(object):
"""A recursive list consisting of a first element and the rest."""
class EmptyList(object):
def __len__(self):
return 0
empty = EmptyList()
def __init__(self, first, rest=empty):
self.first = first
self.rest = rest
def __repr__(self):
args = repr(self.first)
if self.rest is not Rlist.empty:
args += ', {0}'.format(repr(self.rest))
return 'Rlist({0})'.format(args)
def __len__(self):
return 1 + len(self.rest)
def __getitem__(self, i):
if i == 0:
return self.first
return self.rest[i-1]
def extend_rlist(s1, s2):
"""Return a list containing the elements of s1 followed by those of s2."""
if s1 is Rlist.empty:
return s2
return Rlist(s1.first, extend_rlist(s1.rest, s2))
def map_rlist(s, fn):
"""Return a list resulting from mapping fn over the elements of s."""
if s is Rlist.empty:
return s
return Rlist(fn(s.first), map_rlist(s.rest, fn))
def filter_rlist(s, fn):
"""Filter the elemenst of s by predicate fn."""
if s is Rlist.empty:
return s
rest = filter_rlist(s.rest, fn)
if fn(s.first):
return Rlist(s.first, rest)
return rest
s = Rlist(1, Rlist(2, Rlist(3))) # A set is an Rlist with no duplicates
class Tree(object):
"""A tree with internal values."""
def __init__(self, entry, left=None, right=None):
self.entry = entry
self.left = left
self.right = right
def __repr__(self):
args = repr(self.entry)
if self.left or self.right:
args += ', {0}, {1}'.format(repr(self.left), repr(self.right))
return 'Tree({0})'.format(args)
def big_tree(left, right):
"""Return a tree of elements between left and right.
>>> big_tree(0, 12)
Tree(6, Tree(2, Tree(0), Tree(4)), Tree(10, Tree(8), Tree(12)))
"""
if left > right:
return None
split = left + (right - left)//2
return Tree(split, big_tree(left, split-2), big_tree(split+2, right))