Find The Local Maxima And Minima

Question

Definition

The maxima and minima of a given function are the largest and smallest values of the function either within a given range or otherwise within the entire domain of the function.

Challenge

The challenge is to find the local maxima and minima of a given polynomial function using any method you may like. Don't worry, I will try my best to explain the challenge and keep it as simple as possible.

The input will contain all the coefficients of the single variable polynomial in either decreasing or increasing order of power (up to you). For example,

• [3,-7,1] will represent \$3x^2 - 7x + 1\$
• [4,0,0,-3] will represent \$4x^3 - 3\$

How To Solve Using Derivatives

Now, let's say our input is [1,-12,45,8], which is nothing but the function \$x^3 - 12x^2 + 45x + 8\$.

1. The first task is to find the derivative of that function. Since it is a polynomial function, so it is indeed a simple task to do.

The derivative of \$x^n\$ is \$n\times x^{n-1}\$. Any constant terms present with \$x^n\$ are simply multiplied. Also, if there are terms added/subtracted, then their derivatives are also added or subtracted respectively. Remember, the derivative of any constant numerical value is zero. Here are a few examples:

• \$x^3 \to 3x^2\$
• \$9x^4 \to 9\times4\times x^3 = 36x^3\$
• \$-5x^2 \to -5\times2\times x = - 10x\$
• \$2x^3 - 3x^2 + 7x \to 6x^2 - 6x + 7\$
• \$4x^2 - 3 \to 8x - 0 = 8x\$

2. Now solve the equation by equating the new polynomial to zero and get only the integral values of \$x\$.

3. Put those values of \$x\$ in the original function and return the results. That should be the output.

Example

Let us take the example we mentioned earlier, i.e, [1,-12,45,8].

• Input: [1,-12,45,8]
• Function: \$x^3 - 12x^2 + 45x + 8\$
• Derivative: \$3x^2 - 24x + 45 + 0 \to [3,-24,45]\$
• Solving equation: \$3x^2 - 24x + 45 = 0\$, we get \$x = 3\$ and \$x = 5\$.
• Now putting \$x = 3\$ and \$x = 5\$ in the function, we get the values \$(62,58)\$.
• Output: [62,58]

Assumptions

1. Assume that all the input coefficients are integers. They can be in increasing or decreasing order of power.

2. Assume the input to be at least a 2-degree polynomial. If the polynomial has no integer solutions, you can return anything.

3. Assume that the final result will be integers only.

4. You can print the results in any order. The degree of the input polynomial would not be more than 5, so that your code can handle it.

5. The input will be valid so that the solutions of x are not saddle points.

Also, you are not forced to do it by the derivative method. You can use any method you feel like.

Sample Input And Output

[2,-8,0] -> (-8)
[2,3,-36,10] -> (91,-34)
[1,-8,22,-24,8] -> (-1,0,-1) 
[1,0,0] -> (0)

Scoring

This is code-golf so the shortest code wins.

Answer 1

Jelly, 20 bytes

ASŒRḅ@Ðḟ
J’U×µṖÇḅ@€³

Try it online!

Explanation

ASŒRḅ@Ðḟ     Helper Function; find all integer solutions to a polynomial
             All integer roots are within the symmetric range of the sum of the absolute values of the coefficients
A            Absolute Value (Of Each)
 S           Sum
  ŒR         Symmetric Range; `n -> [-n, n]`
      Ðḟ     Filter; keep elements where the result is falsy for:
    ḅ@       Base conversion, which acts like the application of the polynomial
J’U×µṖÇḅ@€³  Main Link
J                             Range of length
 ’                    Lowered
  U          Reversed
   ×         Multiplied with the original list (last value is 0)
    µ        Begin new monadic chain
     Ṗ       Pop; all but the last element
      Ç      Apply last link (get all integer solutions of the derivative)
       ḅ@€³  Base conversion of the polynomial into each of the solutions; apply polynomial to each solution of the derivative.

The helper function in this program was taken from Mr. Xcoder's answer here which was based off of Luis's answer here

Answer 2

JavaScript (ES7), 129 120 bytes

Takes the coefficients in increasing order of power.

a=>(g=x=>x+k?(A=g(x-1),h=e=>a.reduce((s,n,i)=>s+n*(e||i&&i--)*x**i,0))()?A:[h(1),...A]:[])(k=Math.max(...a.map(n=>n*n)))

Test cases

let f =

a=>(g=x=>x+k?(A=g(x-1),h=e=>a.reduce((s,n,i)=>s+n*(e||i&&i--)*x**i,0))()?A:[h(1),...A]:[])(k=Math.max(...a.map(n=>n*n)))

console.log(JSON.stringify(f([0,-8,2])))        // (-8)
console.log(JSON.stringify(f([10,-36,3,2])))    // (91,-34)
console.log(JSON.stringify(f([8,-24,22,-8,1]))) // (-1,0,-1) 

Commented

a => (                        // given the input array a[]
  g = x =>                    // g = recursive function checking whether x is a solution
    x + k ? (                 //   if x != -k:
      A = g(x - 1),           //     A[] = result of a recursive call with x - 1
      h = e =>                //     h = function evaluating the polynomial:
        a.reduce((s, n, i) => //       for each coefficient n at position i:
          s +                 //         add to s
          n                   //         the coefficient multiplied by
          * (e || i && i--)   //         either 1 (if e = 1) or i (if e is undefined)
          * x**i,             //         multiplied by x**i or x**(i-1)
          0                   //         initial value of s
        )                     //       end of reduce()
      )() ?                   //     if h() is non-zero:
        A                     //       just return A[]
      :                       //     else:
        [h(1), ...A]          //       prepend h(1) to A[]
    :                         //   else:
      []                      //     stop recursion
  )(k = Math.max(             // initial call to g() with x = k = maximum of
    ...a.map(n => n * n)      // the squared coefficients of the polynomial
  ))                          // (Math.abs would be more efficient, but longer)

Answer 3

Wolfram Language (Mathematica), 30 bytes

a@x/.#&/@Solve[a=#;#'@x==0,x]&

Takes a pure-function polynomial (i.e. a polynomial with # as a variable and with a & at the end).

Try it online!

Answer 4

Julia 0.6 (with Polynomials package), 57 bytes

using Polynomials
x->map(Poly(x),roots(polyder(Poly(x))))

Try it online!

Takes coefficients in increasing order, i.e. the first input is the constant term.

Example run:

julia> using Polynomials

julia> g = x -> map(Poly(x), roots(polyder(Poly(x))))
(::#1) (generic function with 1 method)

julia> g([8,45,-12,1])
2-element Array{Float64,1}:
 58.0
 62.0

Answer 5

Java 8, 364 239 227 226 218 bytes

a->{int l=a.length,A[]=a.clone(),s=0,i,r,f=l,p;for(;f>0;A[--f]*=f);for(int n:A)s+=n<0?-n:n;for(r=~s;r++<s;){for(p=0,i=f=1;i<l;f*=r)p+=A[i++]*f;if(p==0){for(f=i=0;i<l;f+=a[i++]*Math.pow(r,p++));System.out.println(f);}}}

Uses the same functionality from this answer of mine.

-8 bytes thanks to @OlivierGrégoire by taking the array in reversed order.

Explanation:

Try it online.

a->{                  // Method with integer-varargs parameter and integer return-type
  int l=a.length,     //  The length of the input-array
      A[]=a.clone(),  //  Copy of the input-array
      s=0,            //  Sum-integer, starting at 0
      i,              //  Index-integer
      r,              //  Range-integer
      f=l,            //  Factor-integer, starting at `l`
      p;              //  Polynomial-integer
  for(;f>0;           //  Loop over the copy-array
    A[--f]*=f);       //   And multiply each value with it's index
                      //   (i.e. [8,45,-12,1] becomes [0,45,-24,3])
  for(int n:A)        //  Loop over this copy-array:
    s+=n<0?-n:n;      //   And sum their absolute values
  for(r=~s;r++<s;){   //  Loop `r` from `-s` up to `s` (inclusive) (where `s` is the sum)
    for(p=0,          //   Reset `p` to 0
        i=f=1;        //   and `f` to 1
                      //   (`i` is 1 to skip the first item in the copy-array)
        i<l;          //   Inner loop over the input again, this time with index (`i`)
        f*=r)         //     After every iteration: multiply `f` with the current `r`
      p+=             //    Sum the Polynomial-integer `p` with:
         A[i++]       //     The value of the input at index `i`,
               *f;}   //     multiplied with the current factor `f`
    if(p==0){         //   If `p` is now 0:
      for(f=i=0;      //    Use `f` as sum, and reset it to 0
          i<l;        //    Loop over the input-array
        f+=a[i++]*Math.pow(r,p++));
                      //     Fill in `r` in the parts of the input-function
      System.out.println(f);}}}
                      //    And print the sum

Answer 6

Haskell, 89 bytes

-3 bytes thanks to Laikoni.

r#l=foldr1((.(r*)).(+))l
r l|_:d<-zipWith(*)[0..]l,t<-sum$abs<$>d=[i#l|i<-[-t..t],i#d==0]

Try it online!

Takes coefficients reversed.

Answer 7

Jelly, 9 bytes

J’×UḊÆrḅ@

Try it online!

Takes input as a list of coefficients in decreasing order of powers

How it works

J’×UḊÆrḅ@ - Main link. Takes a list of coefficients C on the left
J         - Yield indices; [1, 2, ..., len(C)]
 ’        - Decrement; [0, 1, ..., len(C)-1]
   U      - Yield C reversed
  ×       - Multiply each element of C reversed by each element of [0, 1, ..., len(C) - 1]
    Ḋ     - Remove the leading 0
     Ær   - Solve the polynomial represented by the new list of coefficients
       ḅ@ - Evaluate the roots as inputs to C (base conversion)

Answer 8

Vyxal, 8 bytes

∆Ċ:∆Kv∆Q

Try it Online!

The power of actual symbolic algebra.

Explained

∆Ċ:∆Kv∆Q
∆Ċ        # Convert the list of coefficients into an expression that looks like a*x**n + b*x**(n-1) ... + z
  :       # Push a second copy of that
   ∆K     # Get the stationary points of that (returns x values)
     v∆Q  # and sub those x-values into the original equation

Answer 9

Python 3, 156 bytes

def f(p,E=enumerate):a=lambda p,v:sum(e*v**i for i,e in E(p));d=[e*i for i,e in E(p)][1:];r=sum(map(abs,d));return[a(p,x)for x in range(-r,r+1)if a(d,x)==0]

Try it online!

-2 bytes thanks to Mr. Xcoder
-22 bytes thanks to ovs

Answer 10

Python + numpy, 91

• 1 byte saved thanks to @KevinCruijssen

from numpy import*
p=poly1d(input())
print map(lambda x:int(polyval(p,x)),roots(p.deriv()))

Try it online.

Answer 11

Pari/GP, 28 bytes

p->[eval(p)|x<-polroots(p')]

Evaluate the polynomial at the roots of its derivative.

Try it online!