-
Notifications
You must be signed in to change notification settings - Fork 0
/
disc06.py
207 lines (159 loc) · 4.29 KB
/
disc06.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
def fib_iter(n):
prev, curr, i = 0, 1, 1
while i < n:
prev, curr = curr, prev + curr
i += 1
return prev
def fib_recursive(n):
if n == 0 or n == 1:
return n
else:
return fib_recursive(n - 1) + fib_recursive(n - 2)
import compo
"""Write a function that takes in a a linked list and returns the sum of all its elements.
You may assume all elements in lnk are integers. """
def sum_nums(lnk):
"""
>>> a = Link(1, Link(6, Link(7)))
>>> sum_nums(a)
14
"""
if lnk is Link.empty:
return 0
return lnk.first + sum_nums(lnk.rest)
def sum_of_factorial(n):
if n == 0:
return 1
else:
return factorial(n) + sum_of_factorial(n - 1)
def bonk(n):
total = 0
while n >= 2:
total += n
n = n / 2
return total
def mod_7(n):
if n % 7 == 0:
return 0
else:
return 1 + mod_7(n - 1)
def bar(n):
if n % 2 == 1:
return n + 1
return n
def foo(n):
if n < 1:
return 2
if n % 2 == 0:
return foo(n - 1) + foo(n - 2)
else:
return 1 + foo(n - 2)
""" What is the order of growth of foo(bar(n))?"""
from compo import *
def multiply_lnks(lst_of_lnks):
"""
>>> a = Link(2, Link(3, Link(5)))
>>> b = Link(6, Link(4, Link(2)))
>>> c = Link(4, Link(1, Link(0, Link(2))))
>>> p = multiply_lnks([a, b, c])
>>> p.first
48
>>> p.rest.first
12
>>> p.rest.rest.rest
()
"""
product = 1
for lnk in lst_of_lnks:
if lnk is Link.empty:
return Link.empty
product *= lnk.first
lst_of_lnk_rests = [lnk.rest for lnk in lst_of_lnks]
return Link(product, multiply_lnks(lst_of_lnk_rests))
"""Write a function that takes a SORTED linked list of integers and mutates it so that
all duplicates are removed."""
def remove_duplicates(lnk):
"""
>>> lnk = Link(1, Link(1, Link(1, Link(5))))
>>> unique = remove_duplicates(lnk)
>>> unique
Link(1, Link(5))
>>> lnk
Link(1, Link(5))
"""
if lnk is Link.empty or lnk.rest is Link.empty:
return lnk
elif lnk.first == lnk.rest.first:
lnk.rest = lnk.rest.rest
remove_duplicates(lnk)
return lnk
else:
remove_duplicates(lnk.rest)
return lnk
"""Write a function that takes a list and returns a new list that keeps only the even-indexed
elements of lst and multiplies them by their corresponding index."""
def even_weighted(lst):
"""
>>> x = [1, 2, 3, 4, 5, 6]
>>> even_weighted(x)
[0, 6, 20]
"""
return [ lst[i] * i for i in range(0, len(lst), 2) ]
"""QuickSort"""
def quickSort_list(lst):
if len(lst)<2:
return lst
pivot = lst[0]
less = [ ele for ele in lst[1:] if ele <= pivot ]
greater = [ele for ele in lst[1:] if ele > pivot]
return quickSort_list(less) + [pivot] + quickSort_list(greater)
"""Write a function that takes in a list and returns the maximum product that can be
formed using nonconsecutive elements of the list. The input list will contain only
numbers greater than or equal to 1. """
from operator import mul
from functools import reduce
def max_product(lst):
"""Return the maximum product that can be formed using lst
without using any consecutive numbers.
>>> max_product([10,3,1,9,2]) # 10 * 9
90
>>> max_product([5,10,5,10,5]) # 5 * 5 * 5
125
>>> max_product([])
1
"""
if len(lst) == 0:
return 1
result = 0
splited = [lst[i::j] for i in range(len(lst)) for j in range(2,len(lst)) ]
for ele in splited:
temp = reduce(mul, ele)
if result < temp:
result = temp
return temp
"""An expression tree is a tree that contains a function for each non-leaf node,
which can be either ’+’ or ’*’. All leaves are numbers. Implement eval_tree,
which evaluates an expression tree to its value. You may want to use the functions
sum and prod, which take a list of numbers and compute the sum and product
respectively."""
def eval_tree(tree):
"""Evaluates an expression tree with functions the root.
>>> eval_tree(tree(1))
1
>>> expr = tree('*', [tree(2), tree(3)])
>>> eval_tree(expr)
6
>>> eval_tree(tree('+', [expr, tree(4), tree(5)]))
15
"""
if is_leaf(tree):
return label[tree]
args = [eval_tree(b) for b in branches(tree)]
if label[tree] == '+':
return sum(args)
else:
return prod(args)
def prod(iter):
from functools import reduce
from operator import mul
return reduce(mul, iter, 1)