"""
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
>>> 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)
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])
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')
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))) == poly((11, 22, 33))
assert sub(poly((10, 20, 30)), poly((1, 2, 3))) == poly((9, 18, 27))
assert mul(poly((10, 20, 30)), poly((1, 2, 3))) == poly((10, 40, 100, 120, 90))
assert power(poly((1, 1)), 2) == poly((1, 2, 1))
assert power(poly((1, 1)), 10) == poly((1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1))
assert deriv(p1) == poly((20, 60))
assert integral(poly((20, 60))) == poly((0, 20, 30))
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
def add(p1, p2):
"Return a new polynomial which is the sum of polynomials p1 and p2."
def sub(p1, p2):
"Return a new polynomial which is the difference of polynomials p1 and p2."
def mul(p1, p2):
"Return a new polynomial which is the product of polynomials p1 and p2."
def power(p, n):
"Return a new polynomial which is p to the nth power (n a non-negative integer)."
"""
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)."
def integral(p, C=0):
"Return the integral of a function p (with respect to its argument)."
"""
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, 1))
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')
My solution:
"""
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
>>> 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)
formula = getFormula(coefs)
def p(x):
return eval(formula.replace('x', str(x)))
p.coefs = coefs
p.__name__ = formula
return p
def getFormula(coefs):
coefs_list = list(coefs)
coefs_list.reverse()
#(10, 20, 30) results in '30 * x**2 + 20 * x + 10'
return ' + '.join(map_coef(coef, len(coefs_list) - index - 1) for index, coef in enumerate(coefs_list) if map_coef(coef, len(coefs_list) - index - 1) != '')
def map_coef(coef, index):
"""
map_coef(7, 3) = '7 * x**3'
map_coef(10, 2) = '10 * x**2'
map_coef(5, 1) = '5 * x'
map_coef(0, 2) = '' <-- 0 * x**2
map_coef(1, 2) = 'x**2' <-- 1 * x**2
map_coef(3, 0) = '3'
"""
if index == 0:
return str(coef) if coef != 0 else ''
elif index == 1:
if coef == 0:
return ''
elif coef == 1:
return 'x'
else:
return str(coef) + ' * x'
else:
if coef == 0:
return ''
if coef == 1:
return 'x**' + str(index)
else:
return str(coef) + ' * x**' + str(index)
def coefsDictionaryToTuple(coefs_dict):
dict_to_list = coefs_dict.items()
dict_to_list.sort()
return tuple((ele[1] for ele in dict_to_list))
def coefs_product(coefs1, coefs2):
#coef1=(10, 20, 30), coefs2=(1, 2, 3)
prod = []
for index1,coef1 in enumerate(coefs1):
for index2, coef2 in enumerate(coefs2):
prod.append((index1 + index2, coef1 * coef2))
#prod => [(0, 10), (1, 20), (2, 30), (1, 20), (2, 40), (3, 60), (2, 30), (3, 60), (4, 90)]
coefs_dict = {} #we will store tuples of same format in this dict but add up coefs with same index
for ele in prod:
if ele[0] not in coefs_dict:
#we create entry
coefs_dict[ele[0]] = ele[1]
else:
#we update entry by adding current coef
coefs_dict[ele[0]] = coefs_dict[ele[0]] + ele[1]
return coefsDictionaryToTuple(coefs_dict)
def coefs_add(coefs1, coefs2):
return coefs_op(coefs1, coefs2, lambda x,y: x + y)
def coefs_sub(coefs1, coefs2):
return coefs_op(coefs1, coefs2, lambda x,y: x - y)
def coefs_op(coefs1, coefs2, op):
coefs_dict = {}
for index, coef in enumerate(coefs1):
coefs_dict[index] = coef
for index, coef in enumerate(coefs2):
if index not in coefs_dict:
#we create entry
coefs_dict[index] = coef
else:
#we update entry by adding current coef
coefs_dict[index] = op(coefs_dict[index], coef)
return coefsDictionaryToTuple(coefs_dict)
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(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')
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))).coefs == (11,22,33)
assert sub(poly((10, 20, 30)), poly((1, 2, 3))).coefs == (9,18,27)
assert mul(poly((10, 20, 30)), poly((1, 2, 3))).coefs == (10, 40, 100, 120, 90)
assert power(poly((1, 1)), 2).coefs == (1, 2, 1)
assert power(poly((1, 1)), 10).coefs == (1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1)
assert deriv(p1).coefs == (20, 60)
assert integral(poly((20, 60))).coefs == (0, 20, 30)
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 hasattr(x, '__call__') and isinstance(x(1), int) and x.__name__.find('x') != -1
def add(p1, p2):
"Return a new polynomial which is the sum of polynomials p1 and p2."
return poly(coefs_add(p1.coefs, p2.coefs))
def sub(p1, p2):
"Return a new polynomial which is the difference of polynomials p1 and p2."
return poly(coefs_sub(p1.coefs, p2.coefs))
def mul(p1, p2):
"Return a new polynomial which is the product of polynomials p1 and p2."
return poly(coefs_product(p1.coefs, p2.coefs))
def power(p, n):
"Return a new polynomial which is p to the nth power (n a non-negative integer)."
if n in [0,1]:
return p
else:
return mul(p, power(p,n-1))
"""
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)."
coefs_new = tuple((index * coef for index, coef in enumerate(p.coefs) if index > 0))
return poly(coefs_new)
def integral(p, C=0):
"Return the integral of a function p (with respect to its argument)."
#The integral of 60 * x + 20 == 30 * x**2 + 20 * x + C, for any constant C.
#assert integral(poly((20, 60))).coefs == (0, 20, 30)
coefs_new = tuple([C] + [coef / (index + 1) for index, coef in enumerate(p.coefs)])
return poly(coefs_new)
"""
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, 1))
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')
No comments:
Post a Comment