-
Notifications
You must be signed in to change notification settings - Fork 0
/
test.py
609 lines (421 loc) · 15.9 KB
/
test.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
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
# Question 1: Pick One
# Define a procedure, pick_one, that takes three inputs: a Boolean
# and two other values. If the first input is True, it should return
# the second input. If the first input is False, it should return the
# third input.
# For example, pick_one(True, 37, 'hello') should return 37, and
# pick_one(False, 37, 'hello') should return 'hello'.
def pick_one(a,b,c):
if a==True:
return b
else:
return c
print pick_one(True, 37, 'hello')
#>>> 37
print pick_one(False, 37, 'hello')
#>>> hello
print pick_one(True, 'red pill', 'blue pill')
#>>> red pill
print pick_one(False, 'sunny', 'rainy')
#>>> rainy
# Question 2. Triangular Numbers
# The triangular numbers are the numbers 1, 3, 6, 10, 15, 21, ...
# They are calculated as follows.
# 1
# 1 + 2 = 3
# 1 + 2 + 3 = 6
# 1 + 2 + 3 + 4 = 10
# 1 + 2 + 3 + 4 + 5 = 15
# Write a procedure, triangular, that takes as its input a positive
# integer n and returns the nth triangular number.
def triangular(n):
x=0
while n>0:
x=x+n
n=n-1
return x
print triangular(1)
#>>>1
print triangular(3)
#>>> 6
print triangular(10)
#>>> 55
#Linear Time
#For the procedures below, check the procedures whose running time scales linearly with the length of the input in the worst case. You may assume the elements in input_list are fairly small numbers.
def proc1(input_list):
maximum = None
for element in input_list :
if maximum < element:
maximum = element
return maximum
def proc2(input_list):
sum = 0
while len(input_list) > 0:
sum = sum + input_list[0] # Assume input_list[0] is constant time
input_list = input_list[1:] # Assume input_list[1:] is constant time
return sum
def proc3(input_list):
for i in range(0, len(input_list)):
for j in range(0, len(input_list)):
if input_list[i] == input_list[j] and i != j:
return False
return True
#only first two true
# Question 4: Remove Tags
# When we add our words to the index, we don't really want to include
# html tags such as <body>, <head>, <table>, <a href="..."> and so on.
# Write a procedure, remove_tags, that takes as input a string and returns
# a list of words, in order, with the tags removed. Tags are defined to be
# strings surrounded by < >. Words are separated by whitespace or tags.
# You may assume the input does not include any unclosed tags, that is,
# there will be no '<' without a following '>'.
def remove_tags(page):
split_page = page.split("<")
print split_page
my_list=[]
for each in split_page:
if each != "":
words=each.replace("\n","")
words=words.strip()
words=words.split(">")[1]
if words != "":
my_list.append(words)
return my_list
print remove_tags('''<h1>Title</h1><p>This is a
<a href="http://www.udacity.com">link</a>.<p>''')
#>>> ['Title','This','is','a','link','.']
print remove_tags('''<table cellpadding='3'>
<tr><td>Hello</td><td>World!</td></tr>
</table>''')
#>>> ['Hello','World!']
print remove_tags("<hello><goodbye>")
#>>> []
# Question 5: Date Converter
# Write a procedure date_converter which takes two inputs. The first is
# a dictionary and the second a string. The string is a valid date in
# the format month/day/year. The procedure should return
# the date written in the form <day> <name of month> <year>.
# For example , if the
# dictionary is in English,
english = {1:"January", 2:"February", 3:"March", 4:"April", 5:"May",
6:"June", 7:"July", 8:"August", 9:"September",10:"October",
11:"November", 12:"December"}
# then "5/11/2012" should be converted to "11 May 2012".
# If the dictionary is in Swedish
swedish = {1:"januari", 2:"februari", 3:"mars", 4:"april", 5:"maj",
6:"juni", 7:"juli", 8:"augusti", 9:"september",10:"oktober",
11:"november", 12:"december"}
# then "5/11/2012" should be converted to "11 maj 2012".
# Hint: int('12') converts the string '12' to the integer 12.
def date_converter(dictionary, date):
if dictionary==english:
numbers=date.split("/")
return numbers[1]+" "+dictionary[int(numbers[0])]+" "+numbers[2]
if dictionary==swedish:
numbers=date.split("/")
return numbers[1]+" "+dictionary[int(numbers[0])]+" "+numbers[2]
print date_converter(english, '5/11/2012')
#>>> 11 May 2012
print date_converter(english, '5/11/12')
#>>> 11 May 12
print date_converter(swedish, '5/11/2012')
#>>> 11 maj 2012
print date_converter(swedish, '12/5/1791')
#>>> 5 december 179
#For each of the procedures defined below, check the box if the procedure always terminates for all inputs that are natural numbers (1,2,3...).
def proc1(n):
while True:
n = n - 1
if n == 0:
break
return 3
#true
def proc2(n):
if n == 0:
return n
return 1 + proc2(n-2)
#breaks on.. prime numbers?
def proc3(n):
if n <=3:
return 1
return proc3(n-1) + proc3(n-2) + proc3(n-3)
#breaks on big numbers?
# Question 7: Find and Replace
# For this question you need to define two procedures:
# make_converter(match, replacement)
# Takes as input two strings and returns a converter. It doesn't have
# to make a specific type of thing. Itcan
# return anything you would find useful in apply_converter.
# apply_converter(converter, string)
# Takes as input a converter (produced by create_converter), and
# a string, and returns the result of applying the converter to the
# input string. This replaces all occurrences of the match used to
# build the converter, with the replacement. It keeps doing
# replacements until there are no more opportunities for replacements.
def make_converter(match, replacement):
def apply_converter(converter, string):
# For example,
c1 = make_converter('aa', 'a')
print apply_converter(c1, 'aaaa')
#>>> a
c = make_converter('aba', 'b')
print apply_converter(c, 'aaaaaabaaaaa')
#>>> ab
# Note that this process is not guaranteed to terminate for all inputs
# (for example, apply_converter(make_converter('a', 'aa'), 'a') would
# run forever).
# Question 8: Longest Repetition
# Define a procedure, longest_repetition, that takes as input a
# list, and returns the element in the list that has the most
# consecutive repetitions. If there are multiple elements that
# have the same number of longest repetitions, the result should
# be the one that appears first. If the input list is empty,
# it should return None.
def longest_repetition():
#For example,
print longest_repetition([1, 2, 2, 3, 3, 3, 2, 2, 1])
# 3
print longest_repetition(['a', 'b', 'b', 'b', 'c', 'd', 'd', 'd'])
# b
print longest_repetition([1,2,3,4,5])
# 1
print longest_repetition([])
# None
print longest_repetition([1,2,3,4,5])
# 1
# Question 9: Deep Reverse
# Define a procedure, deep_reverse, that takes as input a list,
# and returns a new list that is the deep reverse of the input list.
# This means it reverses all the elements in the list, and if any
# of those elements are lists themselves, reverses all the elements
# in the inner list, all the way down.
# Note: The procedure must not change the input list.
# The procedure is_list below is from Homework 6. It returns True if
# p is a list and False if it is not.
def is_list(p):
return isinstance(p, list)
def deep_reverse():
#For example,
p = [1, [2, 3, [4, [5, 6]]]]
print deep_reverse(p)
#>>> [[[[6, 5], 4], 3, 2], 1]
print p
#>>> [1, [2, 3, [4, [5, 6]]]]
q = [1, [2,3], 4, [5,6]]
print deep_reverse(q)
#>>> [ [6,5], 4, [3, 2], 1]
print q
#>>> [1, [2,3], 4, [5,6]]
# One Gold Star
# Question 1-star: Stirling and Bell Numbers
# The number of ways of splitting n items in k non-empty sets is called
# the Stirling number, S(n,k), of the second kind. For example, the group
# of people Dave, Sarah, Peter and Andy could be split into two groups in
# the following ways.
# 1. Dave, Sarah, Peter Andy
# 2. Dave, Sarah, Andy Peter
# 3. Dave, Andy, Peter Sarah
# 4. Sarah, Andy, Peter Dave
# 5. Dave, Sarah Andy, Peter
# 6. Dave, Andy Sarah, Peter
# 7. Dave, Peter Andy, Sarah
# so S(4,2) = 7
# If instead we split the group into one group, we have just one way to
# do it.
# 1. Dave, Sarah, Peter, Andy
# so S(4,1) = 1
# or into four groups, there is just one way to do it as well
# 1. Dave Sarah Peter Andy
# so S(4,4) = 1
# If we try to split into more groups than we have people, there are no
# ways to do it.
# The formula for calculating the Stirling numbers is
# S(n, k) = k*S(n-1, k) + S(n-1, k-1)
# Furthermore, the Bell number B(n) is the number of ways of splitting n
# into any number of parts, that is,
# B(n) is the sum of S(n,k) for k =1,2, ... , n.
# Write two procedures, stirling and bell. The first procedure, stirling
# takes as its inputs two positive integers of which the first is the
# number of items and the second is the number of sets into which those
# items will be split. The second procedure, bell, takes as input a
# positive integer n and returns the Bell number B(n).
def stirling():
def bell():
#print stirling(1,1)
#>>> 1
#print stirling(2,1)
#>>> 1
#print stirling(2,2)
#>>> 1
#print stirling(2,3)
#>>>0
#print stirling(3,1)
#>>> 1
#print stirling(3,2)
#>>> 3
#print stirling(3,3)
#>>> 1
#print stirling(4,1)
#>>> 1
#print stirling(4,2)
#>>> 7
#print stirling(4,3)
#>>> 6
#print stirling(4,4)
#>>> 1
#print stirling(5,1)
#>>> 1
#print stirling(5,2)
#>>> 15
#print stirling(5,3)
#>>> 25
#print stirling(5,4)
#>>> 10
#print stirling(5,5)
#>>> 1
#print stirling(20,15)
#>>> 452329200
#print bell(1)
#>>> 1
#print bell(2)
#>>> 2
#print bell(3)
#>>> 5
#print bell(4)
#>>> 15
#print bell(5)
#>>> 52
#print bell(15)
#>>> 1382958545
# Two Gold Stars
# Question 2: Combatting Link Spam
# One of the problems with our page ranking system is pages can
# collude with each other to improve their page ranks. We consider
# A->B a reciprocal link if there is a link path from B to A of length
# equal to or below the collusion level, k. The length of a link path
# is the number of links which are taken to travel from one page to the
# other.
# If k = 0, then a link from A to A is a reciprocal link for node A,
# since no links needs to be taken to get from A to A.
# If k=1, B->A would count as a reciprocal link if there is a link
# A->B, which includes one link and so is of length 1. (it requires
# two parties, A and B, to collude to increase each others page rank).
# If k=2, B->A would count as a reciprocal link for node A if there is
# a path A->C->B, for some page C, (link path of length 2),
# or a direct link A-> B (link path of length 1).
# Modify the compute_ranks code to
# - take an extra input k, which is a non-negative integer, and
# - exclude reciprocal links of length up to and including k from
# helping the page rank.
def compute_ranks(graph):
d = 0.8 # damping factor
numloops = 10
ranks = {}
npages = len(graph)
for page in graph:
ranks[page] = 1.0 / npages
for i in range(0, numloops):
newranks = {}
for page in graph:
newrank = (1 - d) / npages
for node in graph:
if page in graph[node]:
newrank = newrank + d * (ranks[node]/len(graph[node]))
newranks[page] = newrank
ranks = newranks
return ranks
# For example
g = {'a': ['a', 'b', 'c'], 'b':['a'], 'c':['d'], 'd':['a']}
#print compute_ranks(g, 0) # the a->a link is reciprocal
#>>> {'a': 0.26676872354238684, 'c': 0.1216391112164609,
# 'b': 0.1216391112164609, 'd': 0.1476647842238683}
#print compute_ranks(g, 1) # a->a, a->b, b->a links are reciprocal
#>>> {'a': 0.14761759762962962, 'c': 0.08936469270123457,
# 'b': 0.04999999999999999, 'd': 0.12202199703703702}
#print compute_ranks(g, 2)
# a->a, a->b, b->a, a->c, c->d, d->a links are reciprocal
# (so all pages end up with the same rank)
#>>> {'a': 0.04999999999999999, 'c': 0.04999999999999999,
# 'b': 0.04999999999999999, 'd': 0.04999999999999999}
# THREE GOLD STARS
# Question 3-star: Elementary Cellular Automaton
# Please see the video for additional explanation.
# A one-dimensional cellular automata takes in a string, which in our
# case, consists of the characters '.' and 'x', and changes it according
# to some predetermined rules. The rules consider three characters, which
# are a character at position k and its two neighbours, and determine
# what the character at the corresponding position k will be in the new
# string.
# For example, if the character at position k in the string is '.' and
# its neighbours are '.' and 'x', then the pattern is '..x'. We look up
# '..x' in the table below. In the table, '..x' corresponds to 'x' which
# means that in the new string, 'x' will be at position k.
# Rules:
# pattern in position k in contribution to
# Value current string new string pattern number
# is 0 if replaced by '.'
# and value if replaced
# by 'x'
# 1 '...' '.' 1 * 0
# 2 '..x' 'x' 2 * 1
# 4 '.x.' 'x' 4 * 1
# 8 '.xx' 'x' 8 * 1
# 16 'x..' '.' 16 * 0
# 32 'x.x' '.' 32 * 0
# 64 'xx.' '.' 64 * 0
# 128 'xxx' 'x' 128 * 1
# ----------
# 142
# To calculate the patterns which will have the central character x, work
# out the values required to sum to the pattern number. For example,
# 32 = 32 so only pattern 32 which is x.x changes the central position to
# an x. All the others have a . in the next line.
# 23 = 16 + 4 + 2 + 1 which means that 'x..', '.x.', '..x' and '...' all
# lead to an 'x' in the next line and the rest have a '.'
# For pattern 142, and starting string
# ...........x...........
# the new strings created will be
# ..........xx........... (generations = 1)
# .........xx............ (generations = 2)
# ........xx............. (generations = 3)
# .......xx.............. (generations = 4)
# ......xx............... (generations = 5)
# .....xx................ (generations = 6)
# ....xx................. (generations = 7)
# ...xx.................. (generations = 8)
# ..xx................... (generations = 9)
# .xx.................... (generations = 10)
# Note that the first position of the string is next to the last position
# in the string.
# Define a procedure, cellular_automaton, that takes three inputs:
# a non-empty string,
# a pattern number which is an integer between 0 and 255 that
# represents a set of rules, and
# a positive integer, n, which is the number of generations.
# The procedure should return a string which is the result of
# applying the rules generated by the pattern to the string n times.
def cellular_automaton():
print cellular_automaton('.x.x.x.x.', 17, 2)
#>>> xxxxxxx..
print cellular_automaton('.x.x.x.x.', 249, 3)
#>>> .x..x.x.x
print cellular_automaton('...x....', 125, 1)
#>>> xx.xxxxx
print cellular_automaton('...x....', 125, 2)
#>>> .xxx....
print cellular_automaton('...x....', 125, 3)
#>>> .x.xxxxx
print cellular_automaton('...x....', 125, 4)
#>>> xxxx...x
print cellular_automaton('...x....', 125, 5)
#>>> ...xxx.x
print cellular_automaton('...x....', 125, 6)
#>>> xx.x.xxx
print cellular_automaton('...x....', 125, 7)
#>>> .xxxxx..
print cellular_automaton('...x....', 125, 8)
#>>> .x...xxx
print cellular_automaton('...x....', 125, 9)
#>>> xxxx.x.x
print cellular_automaton('...x....', 125, 10)
#>>> ...xxxxx