14
\$\begingroup\$

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 3x2 - 7x + 1 = 0
  • [4,0,0,-3] will represent 4x3-3=0.

How To Solve (Using Derivatives)?

Now, let's say our input is [1,-12,45,8], which is nothing but the function x3 - 12x2 + 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 xn is n*xn-1. Any constant terms present with xn 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:

    • x3 -> 3x2
    • 9x4 -> 9*4*x3 = 36x3
    • -5x2 -> -5*2*x = - 10x
    • 2x3 - 3x2 + 7x -> 6x2 - 6x + 7
    • 4x2 - 3 -> 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: x3 - 12x2 + 45x + 8
  • Derivative -> 3x2 - 24x + 45 + 0 -> [3,-24,45]
  • Solving equation 3x2 - 24x + 45 = 0, we get x = 3 or 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 so the shortest code wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ If I understand correctly: in the example the step "Solving equation" would be partially this previous challenge of you? Also, step "Now putting x=3 and x=5 in the function" means the original function at "Function" and not the function at "Derivative", right? \$\endgroup\$ – Kevin Cruijssen Jan 31 '18 at 16:11
  • 1
    \$\begingroup\$ For sample I/O 3, I'm getting (-1, 0, 1), which I believe is the actual correct answer... not sure though. If you disagree with me ping me in chat. \$\endgroup\$ – HyperNeutrino Jan 31 '18 at 16:14
  • 1
    \$\begingroup\$ The input will be valid so that the solutions of x are not saddle points, the case [1,0,0,3] seems to give a saddle point. \$\endgroup\$ – JungHwan Min Jan 31 '18 at 17:03
  • 1
    \$\begingroup\$ @JungHwanMin ah that example was added before the rule was made. Removed now. \$\endgroup\$ – Manish Kundu Jan 31 '18 at 17:19
  • 1
    \$\begingroup\$ x^3 - 12x^2 + 45x + 8 = 0, although personally I prefer you write it as f(x)=x^3-12x^2+45x+8 without the =0 because =0 doesn't make sense since we are dealing with a function, not solving an equation. \$\endgroup\$ – Weijun Zhou Jan 31 '18 at 20:40
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ @JungHwanMin I'll point that out to OP. That's a direct violation of the statement that there will be no saddle points because the derivative of the polynomial at 3 is 0. edit oh you already did nvm just upvoted the comment then \$\endgroup\$ – HyperNeutrino Jan 31 '18 at 17:11
3
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ fails for 0,0,1 (x^2=0) \$\endgroup\$ – betseg Jan 31 '18 at 17:18
  • \$\begingroup\$ @betseg Thanks for reporting this. Fixed. \$\endgroup\$ – Arnauld Jan 31 '18 at 17:41
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ fails for 1,0,0 (x^2=0) \$\endgroup\$ – betseg Jan 31 '18 at 17:16
  • \$\begingroup\$ @betseg Thanks! Fixed and golfed. \$\endgroup\$ – Kevin Cruijssen Jan 31 '18 at 19:35
  • 1
    \$\begingroup\$ You should accept the input in reversed order (it is explicitly allowed) to reduce your count like this: int... ,i, ...; for(;f>0;)A[--f]*=f;. Unless I'm mistaken, this should save you at least 4 bytes. If you do this, make sure to invert all your accesses to the input. \$\endgroup\$ – Olivier Grégoire Feb 1 '18 at 15:57
  • \$\begingroup\$ @OlivierGrégoire Thanks, 8 bytes saved! \$\endgroup\$ – Kevin Cruijssen Feb 2 '18 at 7:55
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ d<-tail$ can be shortened to _:d<-. \$\endgroup\$ – Laikoni Jan 31 '18 at 20:01
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 28 bytes

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

Evaluate the polynomial at the roots of its derivative.

Try it online!

\$\endgroup\$

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.