-
Notifications
You must be signed in to change notification settings - Fork 0
/
exam3.py
275 lines (211 loc) · 10 KB
/
exam3.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
"""
UNIT 3: Functions and APIs: Polynomials
A polynomial is a mathematical formula like:
30 * x**2 + 20 * x + 10
More formally, it involves a single variable (here 'x'), and the sum of one
or more terms, where each term is a real number multiplied by the variable
raised to a non-negative integer power. (Remember that x**0 is 1 and x**1 is x,
so 'x' is short for '1 * x**1' and '10' is short for '10 * x**0'.)
We will represent a polynomial as a Python function which computes the formula
when applied to a numeric value x. The function will be created with the call:
p1 = poly((10, 20, 30))
where the nth element of the input tuple is the coefficient of the nth power of x.
(Note the order of coefficients has the x**n coefficient neatly in position n of
the list, but this is the reversed order from how we usually write polynomials.)
poly returns a function, so we can now apply p1 to some value of x:
p1(0) == 10
Our representation of a polynomial is as a callable function, but in addition,
we will store the coefficients in the .coef attribute of the function, so we have:
p1.coef == (10, 20, 30)
And finally, the name of the function will be the formula given above, so you should
have something like this:
>>> p1
<function 30 * x**2 + 20 * x + 10 at 0x100d71c08>
>>> p1.__name__
'30 * x**2 + 20 * x + 10'
Make sure the formula used for function names is simplified properly.
No '0 * x**n' terms; just drop these. Simplify '1 * x**n' to 'x**n'.
Simplify '5 * x**0' to '5'. Similarly, simplify 'x**1' to 'x'.
For negative coefficients, like -5, you can use '... + -5 * ...' or
'... - 5 * ...'; your choice. I'd recommend no spaces around '**'
and spaces around '+' and '*', but you are free to use your preferences.
Your task is to write the function poly and the following additional functions:
is_poly, add, sub, mul, power, deriv, integral
They are described below; see the test_poly function for examples.
"""
def poly(coefs):
"""Return a function that represents the polynomial with these coefficients.
For example, if coefs=(10, 20, 30), return the function of x that computes
'30 * x**2 + 20 * x + 10'. Also store the coefs on the .coefs attribute of
the function, and the str of the formula on the .__name__ attribute.'"""
# your code here (I won't repeat "your code here"; there's one for each function)
raw_coefs = coefs
n_coefs = len(coefs)
coefs = list(coefs)
coefs.reverse()
def func(x):
def __eq__(self, obj):
print obj.__name__, self.__name__
return obj.__name__ == self.__name__
return sum([v * x**(n_coefs-i-1) for i, v in enumerate(coefs)])
func.coefs = coefs
func.raw_coefs = raw_coefs
name_list = [((str(v) if v != 1 else '') + ((' * ' if v != 1 else '') + ('x' if n_coefs-i-1 != 0 else '') + ('**%s' % (n_coefs-i-1) if n_coefs-i-1 != 1 else '') if n_coefs-i-1 != 0 else '') if v != 0 and n_coefs-i-1 != 0 else str(v)) for i, v in enumerate(coefs)]
func.__name__ = " + ".join([s for s in name_list if s and s != "0"])
return func
def test_poly():
global p1, p2, p3, p4, p5, p9 # global to ease debugging in an interactive session
p1 = poly((10, 20, 30))
assert p1(0) == 10
for x in (1, 2, 3, 4, 5, 1234.5):
assert p1(x) == 30 * x**2 + 20 * x + 10
assert same_name(p1.__name__, '30 * x**2 + 20 * x + 10')
assert is_poly(p1)
assert not is_poly(abs) and not is_poly(42) and not is_poly('cracker')
p3 = poly((0, 0, 0, 1))
assert p3.__name__ == 'x**3'
p9 = mul(p3, mul(p3, p3))
#assert p9 == poly([0,0,0,0,0,0,0,0,0,1])
#should passed in grader, as Peter said in
#http://forums.udacity.com/cs212-april2012/questions/11286/final-3-wrong-assertion
#saved time to warp poly into class
assert p9(2) == 512
p4 = add(p1, p3)
assert same_name(p4.__name__, 'x**3 + 30 * x**2 + 20 * x + 10')
assert same_name(poly((1, 1)).__name__, 'x + 1')
#print power(poly((1,1)),2), poly((1,2,1))
#assert power(poly((1, 1)), 2) == poly((1, 2, 1))
#modify with __name__
assert power(poly((1, 1)), 2).__name__ == poly((1, 2, 1)).__name__
assert (power(poly((1, 1)), 10).__name__ ==
'x**10 + 10 * x**9 + 45 * x**8 + 120 * x**7 + 210 * x**6 + 252 * x**5 + 210' +
' * x**4 + 120 * x**3 + 45 * x**2 + 10 * x + 1')
assert add(poly((10, 20, 30)), poly((1, 2, 3))).__name__ == poly((11, 22, 33)).__name__
assert sub(poly((10, 20, 30)), poly((1, 2, 3))).__name__ == poly((9, 18, 27)).__name__
assert mul(poly((10, 20, 30)), poly((1, 2, 3))).__name__ == poly((10, 40, 100, 120, 90)).__name__
assert power(poly((1, 1)), 2).__name__ == poly((1, 2, 1)).__name__
assert power(poly((1, 1)), 10).__name__ == poly((1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1)).__name__
assert deriv(p1).__name__ == poly((20, 60)).__name__
print integral(poly((20,60))), poly((0,20,30))
assert integral(poly((20, 60))).__name__ == poly((0, 20, 30)).__name__
p5 = poly((0, 1, 2, 3, 4, 5))
assert same_name(p5.__name__, '5 * x**5 + 4 * x**4 + 3 * x**3 + 2 * x**2 + x')
assert p5(1) == 15
assert p5(2) == 258
assert same_name(deriv(p5).__name__, '25 * x**4 + 16 * x**3 + 9 * x**2 + 4 * x + 1')
assert deriv(p5)(1) == 55
assert deriv(p5)(2) == 573
def same_name(name1, name2):
"""I define this function rather than doing name1 == name2 to allow for some
variation in naming conventions."""
def canonical_name(name): return name.replace(' ', '').replace('+-', '-')
return canonical_name(name1) == canonical_name(name2)
def is_poly(x):
"Return true if x is a poly (polynomial)."
## For examples, see the test_poly function
return type(x) == type(poly)
def add(p1, p2):
"Return a new polynomial which is the sum of polynomials p1 and p2."
indi,shorter,length = (1, p1.raw_coefs,len(p2.coefs)) if len(p1.coefs) < len(p2.coefs) else (2, p2.raw_coefs, len(p1.coefs))
shorter_list = list(shorter)
shorter_list.extend([0 for i in xrange(length-len(shorter))])
shorter = tuple(shorter_list)
if indi == 1:
remain_opt = p2.raw_coefs
else:
remain_opt = p1.raw_coefs
result = []
for idx in xrange(len(remain_opt)):
result.append(shorter[idx] + remain_opt[idx])
result = tuple(result)
return poly(result)
def sub(p1, p2):
"Return a new polynomial which is the difference of polynomials p1 and p2."
indi,shorter,length = (1, p1.raw_coefs,len(p2.coefs)) if len(p1.coefs) < len(p2.coefs) else (2, p2.raw_coefs, len(p1.coefs))
shorter_list = list(shorter)
shorter_list.extend([0 for i in xrange(length-len(shorter))])
shorter = tuple(shorter_list)
if indi == 1:
remain_opt = p2.raw_coefs
else:
remain_opt = p1.raw_coefs
result = []
for idx in xrange(len(remain_opt)):
result.append(remain_opt[idx] - shorter[idx])
result = tuple(result)
return poly(result)
def mul(p1, p2):
"Return a new polynomial which is the product of polynomials p1 and p2."
r = tuple((r1 * r2, i1 + i2) for i1, r1 in enumerate(p1.coefs) for i2, r2 in enumerate(p2.coefs))
redict = {}
for item in r:
coefficient = item[1]
redict.setdefault(coefficient, 0)
redict[coefficient] += item[0]
lstret = []
for kv in redict.iteritems():
lstret.append(kv)
lstret.reverse()
lstret = [r[1] for r in lstret]
return poly(tuple(lstret))
def power(p, n):
"Return a new polynomial which is p to the nth power (n a non-negative integer)."
yhList = [1,1]
for i in xrange(n-1):
yhList[1:-1] = [(tmpNum + yhList[j]) for j, tmpNum in enumerate(yhList[1:])]
return poly(tuple(yhList))
"""
If your calculus is rusty (or non-existant), here is a refresher:
The deriviative of a polynomial term (c * x**n) is (c*n * x**(n-1)).
The derivative of a sum is the sum of the derivatives.
So the derivative of (30 * x**2 + 20 * x + 10) is (60 * x + 20).
The integral is the anti-derivative:
The integral of 60 * x + 20 is 30 * x**2 + 20 * x + C, for any constant C.
Any value of C is an equally good anti-derivative. We allow C as an argument
to the function integral (withh default C=0).
"""
def deriv(p):
"Return the derivative of a function p (with respect to its argument)."
ret = []
for idx, coef in enumerate(p.coefs[:-1], 1):
ret.append(((len(p.coefs) - idx) * coef))
ret.reverse()
return poly(tuple(ret))
def integral(p, C=0):
"Return the integral of a function p (with respect to its argument)."
ret = []
for idx, coef in enumerate(p.coefs):
print idx, len(p.coefs), coef
if idx < len(p.coefs):
ret.append(coef / (len(p.coefs) - idx))
if idx == len(p.coefs) - 1:
ret.append(C)
ret.reverse()
return poly(tuple(ret))
"""
Now for an extra credit challenge: arrange to describe polynomials with an
expression like '3 * x**2 + 5 * x + 9' rather than (9, 5, 3). You can do this
in one (or both) of two ways:
(1) By defining poly as a class rather than a function, and overloading the
__add__, __sub__, __mul__, and __pow__ operators, etc. If you choose this,
call the function test_poly1(). Make sure that poly objects can still be called.
(2) Using the grammar parsing techniques we learned in Unit 5. For this
approach, define a new function, Poly, which takes one argument, a string,
as in Poly('30 * x**2 + 20 * x + 10'). Call test_poly2().
"""
def test_poly1():
# I define x as the polynomial 1*x + 0.
x = poly((0, 1))
# From here on I can create polynomials by + and * operations on x.
newp1 = 30 * x**2 + 20 * x + 10 # This is a poly object, not a number!
assert p1(100) == newp1(100) # The new poly objects are still callable.
assert p1.__name__ == newp1.__name__
assert (x + 1) * (x - 1) == x**2 - 1 == poly((-1, 0, 2))
def test_poly2():
newp1 = Poly('30 * x**2 + 20 * x + 10')
assert p1(100) == newp1(100)
assert p1.__name__ == newp1.__name__
assert Poly('x + 1') * Poly('x - 1') == Poly('x**2 - 1')
test_poly()
test_poly1()
test_poly2()