3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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]? \$\endgroup\$ – DLosc May 26 '15 at 5:49
  • \$\begingroup\$ What should be the output for polynomials whose minimum value is negative infinity, such as x^3? \$\endgroup\$ – DLosc May 26 '15 at 5:50
  • \$\begingroup\$ @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. \$\endgroup\$ – ibanez221 May 26 '15 at 5:59
  • \$\begingroup\$ Is a local minimum acceptable ? \$\endgroup\$ – Michael M. May 26 '15 at 6:28
  • \$\begingroup\$ @Mig yes, but ideally the program will find all minima and select the smallest one (not just magnitude, so -100 is lower than -2). \$\endgroup\$ – ibanez221 May 26 '15 at 6:32
6
\$\begingroup\$

Python - 202 Bytes

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
\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can do the polynomial evaluation shorter recursively: A=lambda p,x:p>[]and p[0]+x*A(p[1:],x). \$\endgroup\$ – xnor May 26 '15 at 11:39
  • \$\begingroup\$ How do you guarantee that Newton's method converges? \$\endgroup\$ – Peter Taylor May 26 '15 at 17:44
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – primo May 26 '15 at 23:58
  • 1
    \$\begingroup\$ I was more interested in the case where there is a local minimum, but Newton's method goes in circles. \$\endgroup\$ – Peter Taylor May 27 '15 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.