3
1
What is the shortest amount of code that can find the minimum of an inputted polynomial? I realize that you can import packages like Numpy and others, but using only user defined functions, what is the shortest way to do this? For example, if 6x6 + 4x3-12 is entered (ignore parsing issues), what would be the shortest amount of code to find the minimum value?
ibanez221
Posted 2015-05-26T04:45:37.497
Reputation: 39
6
D=lambda p:[i*p[i]for i in range(1,len(p))]
A=lambda p,x:p>[]and p[0]+x*A(p[1:],x)
def N(p):f=D(p);s=D(f);x=1.;y=-x;exec'x-=A(f,x)/A(s,x);y-=A(f,y)/A(s,y);'*99;return A(p,x),A(p,y)
print min(N(input()))
11 bytes saved due to @xnor.
Input is taken from stdin, and is expected to be in the following format: [x0, x1, x2, ...]. For example, the sample in the problem description would be entered as [-12, 0, 0, 4, 0, 0, 6].
Functions
D - Calculates the derivative of a polynomial p.
A - Applies a polynomial p to the value x.
N - Uses Newton's Method to calculate local minima/maxima of a polynomial p.
Note: For higher order polynomials, there may be several local minima. In these cases, this function is not guaranteed to find the global minimum.
Sample Usage
$ echo [-12, 0, 0, 4, 0, 0, 6] | python poly-min.py
-12.6666666667
primo
Posted 2015-05-26T04:45:37.497
Reputation: 30 891
1I think you can do the polynomial evaluation shorter recursively: A=lambda p,x:p>[]and p[0]+x*A(p[1:],x). – xnor – 2015-05-26T11:39:05.547
How do you guarantee that Newton's method converges? – Peter Taylor – 2015-05-26T17:44:12.913
1@PeterTaylor if the first derivative isn't zero anywhere, for example x³ + x, it obviously won't. But this also implies that there isn't a local minimum anywhere, either. – primo – 2015-05-26T23:58:31.940
1
I was more interested in the case where there is a local minimum, but Newton's method goes in circles.
– Peter Taylor – 2015-05-27T07:04:59.330
Does "ignore parsing issues" mean that we can assume the polynomial data is in any convenient form? E.g. can I accept the example polynomial as a list of coefficients
[-12, 0, 0, 4, 0, 0, 6]? – DLosc – 2015-05-26T05:49:05.093What should be the output for polynomials whose minimum value is negative infinity, such as x^3? – DLosc – 2015-05-26T05:50:08.857
@DLosc yes that is acceptable, and I guess I should exclude those that don't have a finite number. Let's assume they exist in the space of R2, and are rational numbers. – ibanez221 – 2015-05-26T05:59:14.303
Is a local minimum acceptable ? – Michael M. – 2015-05-26T06:28:21.470
@Mig yes, but ideally the program will find all minima and select the smallest one (not just magnitude, so -100 is lower than -2). – ibanez221 – 2015-05-26T06:32:23.433