Determine the degree of a polynomial

Question

Background:

For this challenge, a polynomial looks like this:

$$P(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_2x^2+a_1x+a_0$$

The degree, \$n\$, is the highest power \$x\$ is raised to. An example of a degree 7 polynomial would be:

$$P(x)=4x^7+2x^6-7x^4+x^2-6x+17$$

All powers are integers \$n\ge0\$. This means \$x\$, \$-2\$, and \$0\$ could all be considered polynomials, but not \$\frac{1}{x}\$ or \$\sqrt{x}\$.

Challenge:

Write a program or functions which takes a number of pairs \$(x, P(x))\$, and finds the smallest possible degree of \$P(x)\$. The values of \$x\$ will be incrementing; \$\{(0, 1), (1, 0), (2, 1)\}\$ is a valid input, but \$\{(0, 2), (10, 20), (11, 22)\}\$ is not.

Given \$\{(0, 1), (1, 0), (2, 1)\}\$, for example, the degree is \$2\$ (and \$P(x)=x^2-2x+1\$).

Input:

Input will consist of at least \$n+1\$ pairs of integer values, and at least \$2\$, representing \$x\$ and \$P(x)\$. The \$x\$ values will all be one higher than the previous one.

Input can be taken in any reasonable format. Invalid inputs do not need to be handled. Optionally, you can input only the \$P(x)\$ values (and ignore \$x\$ altogether).

Output:

Output will be an integer \$n\ge0\$, representing the degree of \$P(x)\$.

As with the input, any reasonable format is valid.

Tip:

A simple way to find the degree of a polynomial function (like \$P(x)\$) when you have a list of inputs with incrementing \$x\$ values is to create a list of the \$P(x)\$ values, then repeatedly find the difference between adjacent items. For example, given the inputs \$\{(-3, 14), (-2, 4), (-1, -2), (0, -4), (1, -2)\}\$:

$$\{14, 4, -2, -4, -2\}$$ $$\{10, 6, 2, -2\}$$ $$\{4, 4, 4\}$$

After some number of iterations, \$2\$ in this case, all of the items will be the same number. That number of iterations is \$n\$.

Test cases:

(-1, 8), (0, 8), (1, 8)                                    0
(0, 0), (1, 0), (2, 0)                                     0
(1, 0), (2, 1)                                             1
(0, 0), (1, 2), (2, 4), (3, 6), (4, 8)                     1
(-4, -20), (-3, -12), (-2, -6)                             2
(6, 1296), (7, 2401), (8, 4096), (9, 6561), (10, 10000)    4

This is code-golf, so shortest answer in bytes per language wins!

Answer 1

Husk, ⁸ 6 bytes

←VE¡Ẋ-

Try it online!

-2 bytes from Leo.

Explanation

←VE¡Ẋ- Input: list of P(x)
   ¡Ẋ- repeatedly take deltas and put in infinite list
 V     First index where
  E    all elements are equal
←      decrement

Answer 2

J, ^{26 18} 17 bytes

-~@}.i.~#\-/\~&2]

Try it online!

^{Thanks to Bubbler for -1 byte and for catching a bug!}

• -/\~&2 Apply "successive deltas" verb iteratively "left arg" times to the right arg.

• #\ ... ] Where the left arg is the lengths of input prefixes (ie, 1 2 3 ... <input length>) and the right arg is the input. Eg, with the input 14 4 _2 _4 _2 this gives us the matrix:

   10 6 2 _2
   4 4 4  0
   0 0 0  0
   0 0 0  0
   0 0 0  0
  

• -~@}. Subtract the original input from itself after killing the first element }.. The gives a row of all zeros:

   0 0 0 0
  

• i.~ Return index of the first row in the matrix above matching that all zeros row.

Answer 3

Pyth, 9 bytes

tl.u@.+QY

Try it online!

Input taken as a list of \$P(x)\$.

Translation of Razetime's Husk answer.

Answer 4

R, 50 39 bytes

x=scan();while(any(x<-diff(x)))F=F+1;+F

Try it online!

Answer 5

Jelly, 6 bytes

IƬE€ċ0

Try it online!

How it works

IƬE€ċ0 - Main link. Takes P on the left
 Ƭ     - Until reaching a fixed point:
I      -   Take deltas
   €   - For each:
  E    -   All equal?
    ċ0 - Count the number of 0s

Answer 6

05AB1E, 13 7 bytes

[DËD–#¥

Try it online!

-6 thanks to ovs!

Answer 7

Wolfram Language (Mathematica), 39 bytes

Exponent[InterpolatingPolynomial[#,],]&

Try it online!

Takes input as the list of y-values only. Spits some syntax errors because it uses Null as the variable (after each comma) to save two bytes.

If anyone knows how to translate this into Sledgehammer, I bet it would be really short.

Answer 8

Wolfram Language (Mathematica), 32 34 bytes

f@{a_..}=0
f@a_:=f@Differences@a+1

Try it online!

Perhaps less interesting than Greg's answer. Implements the differences algorithm.

Answer 9

JavaScript (Node.js), 45 bytes

• 6 bytes saved by Arnauld

f=p=>(q=p.map(x=>p-(p=x))).some(x=>x)&&f(q)+1

Try it online!

NaN is falsy, let's propagate it.

---

As the tip shown in question. We iterate one more step as:

$$ \begin{matrix} \{& 14 & 4 & −2 & −4 & −2 & \} \\ \{& 10 & 6 & 2 & −2 & & \} \\ \{& 4 & 4 & 4 & & & \} \\ \{& 0 & 0 & & & &\} \\ \end{matrix} $$

We check the finish of iteration by looking if all elements are \$0\$.

Reducing array size when iterate cost to many bytes. So we simply fill NaN instead.

$$ \begin{matrix} \{& 14 & 4 & −2 & −4 & −2 & \} \\ \{& 10 & 6 & 2 & −2 & \text{NaN} & \} \\ \{& 4 & 4 & 4 & \text{NaN} & \text{NaN} & \} \\ \{& 0 & 0 & \text{NaN} & \text{NaN} & \text{NaN} &\} \\ \end{matrix} $$

And check if everything is falsy.

Answer 10

Python 3, 59 56 bytes

from numpy import*
f=lambda x:len({*x})-1and-~f(diff(x))

Try it online!

Takes a tuple of P(x) values as input.

-3 bytes thanks to Danis

Answer 11

JavaScript (V8), 59 bytes

-9 bytes thanks to @Neil

f=p=>p.some(x=>x-p[0])?f(p.slice(1).map((x,j)=>x-p[j]))+1:0

[Can't add TIO link on school internet]

Old, 68 bytes

f=(p,i=0)=>!p.some(x=>x-p[0])?i:f(p.slice(1).map((x,j)=>x-p[j]),i+1)

Try it online!

Answer 12

Java, 153 bytes

int s(int[]y){return java.util.Arrays.stream(y).distinct().count()!=1?s(java.util.stream.IntStream.range(1,y.length).map(i->y[i]-y[i-1]).toArray())+1:0;}

Takes an array of P(x) values as input.

Try it online!

Explanation

int s(int[] y){
   return java.util.Arrays.stream(y).distinct().count() != 1 //if not all elements are equal
       ?
        s(
           java.util.stream.IntStream.range(1,y.length).map(i->y[i]-y[i-1]).toArray() 
           //get difference of adjacent elements as new array
        ) + 1 //get result of recursive call plus 1
       :  0; //otherwise, we are done
}

Answer 13

Ruby, 45 bytes

f=->a{(a|(r,*a=a))[1]?f[a.map{|c|r-r=c}]+1:0}

Try it online!

Some explanation please?

Basically, a recursive function checking if all elements in the array are equals, and then calculating the differences and increasing by 1 at every step.

f=->a{

    (a|(r,*a=a))[1]?

Check if the array has at least 2 different elements, and split it into head and tail. r,*a=a does the split, putting the first element of a into the variable r. The second step is equivalent to (a|a)[1], or a.uniq[1]. If the array has at least 2 unique elements, this is a truthy value, and if it doesn't, then the result is nil.

    f[a.map{|c|r-r=c}]+1

If the array has at least 2 different values, then calculate the difference between consecutive elements of the array, and increase the final result by 1.

    :0}

If the array only contains one unique value, then the degree of the polynomial is 0.

It took me some time to come up with this solution, so I'm a little late to the party, but I didn't want to post anything above 50 bytes.

Answer 14

Vyxal, l, 6 bytes

‡≈¬⁽¯ẋ

Try it Online!

I'm very proud with how this turned out. It looks and works exactly how I hoped Vyxal would eventually look like.

Explained

‡≈¬

Push a two character lambda to the stack, which returns the logical not of whether or not every element in the list is equal.

⁽¯

Push a function reference of the detlas built-in

ẋ

Repeat the deltas function on the input until the first lambda returns true for the current iteration (generate while condition true). Push and implicitly print the length of the resulting list (done by the -l flag)

Answer 15

Stax, ⁹ 8 bytes

▓>ⁿⁿ∟╔♪╒

Run and debug it

Same idea as my Husk answer. Takes input as P(x) alone.

Explanation

{uD}{:-gf% 
       g   generate values till:
        f  a value fails the filter
{  }       filter:
 u         uniquify the list
  D        and delete first element
    {  g   generator:
     :-    take deltas of the previous iteration
         % take the length of the generated list

Answer 16

Charcoal, 24 bytes

Ｗ⁻⌈θ⌊θ«ＵＭθ⁻§θ⊕λκ⊞υ⊟θ»ＩＬυ

Try it online! Link is to verbose version of code. Explanation:

Ｗ⁻⌈θ⌊θ«

Repeat until the maximum and minimum of the array are equal...

ＵＭθ⁻§θ⊕λκ

... calculate the cyclic differences of the elements...

⊞υ⊟θ

... and remove the last one (which is meaningless) and push it to the predefined empty list (which thereby keeps track of the number of iterations).

»ＩＬυ

Print the final number of iterations.

Answer 17

Julia, 25 bytes

~n=any(n'.<n)&&1+~diff(n)

Try it online!

Answer 18

Scala, 72 bytes

def g(a:Int*):Int=if(a.min<a.max)1+g(a.lazyZip(a.tail)map(_-_):_*)else 0

For once, recursion is shorter!

Without recursion, 74 bytes

Stream.iterate(_){a=>a.lazyZip(a.tail)map(_-_)}indexWhere(a=>a.min==a.max)

Try them both in Scastie!