18
\$\begingroup\$

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 , so shortest answer in bytes per language wins!

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Given the tip, why do we need the x values? \$\endgroup\$
    – Jonah
    Feb 24, 2021 at 5:04
  • 2
    \$\begingroup\$ @Jonah I think there are other ways to find the degree, and if so I don't want to exclude them. I will allow only inputting the \$P(x)\$ values, though. \$\endgroup\$ Feb 24, 2021 at 5:06
  • \$\begingroup\$ @Dingus Yes, the minimum \$\endgroup\$ Feb 24, 2021 at 5:28
  • \$\begingroup\$ Will the input guarantee contains at least 2 points? Is (0, 42) and (0, 0) valid testcases? \$\endgroup\$
    – tsh
    Feb 24, 2021 at 8:21
  • 1
    \$\begingroup\$ The x values are unnecessary for any method of finding the degree, since the degree of a polynomial f(x) is the same as the degree of f(x - a) for some constant a. So we can always assume the x values in the sequence start from 0 and get the correct result. \$\endgroup\$
    – kaya3
    Feb 25, 2021 at 2:32

18 Answers 18

6
\$\begingroup\$

Husk, 8 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
\$\endgroup\$
2
  • \$\begingroup\$ Input can now be taken as \$P(x)\$ alone, forgot to specify that \$\endgroup\$ Feb 24, 2021 at 5:07
  • \$\begingroup\$ L↑o¬E -> ←VE Try it online! \$\endgroup\$
    – Leo
    Feb 24, 2021 at 6:11
6
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ I don't think sum is the right way, instead it should be directly tested if the entire row is zero. (Example: input 2 _4 2 which is obviously quadratic, but your function gives 0) \$\endgroup\$
    – Bubbler
    Feb 24, 2021 at 6:03
  • 1
    \$\begingroup\$ Fixed 17 bytes \$\endgroup\$
    – Bubbler
    Feb 24, 2021 at 6:12
  • \$\begingroup\$ Very good catch, ty @Bubbler. \$\endgroup\$
    – Jonah
    Feb 24, 2021 at 6:16
5
\$\begingroup\$

Pyth, 9 bytes

tl.u@.+QY

Try it online!

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

Translation of Razetime's Husk answer.

\$\endgroup\$
5
\$\begingroup\$

R, 50 39 bytes

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

Try it online!

\$\endgroup\$
0
4
\$\begingroup\$

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

05AB1E, 13 7 bytes

[DËD–#¥

Try it online!

-6 thanks to ovs!

\$\endgroup\$
2
  • \$\begingroup\$ Does this work for 8 bytes? \$\endgroup\$
    – ovs
    Feb 24, 2021 at 7:54
  • 1
    \$\begingroup\$ 7 bytes \$\endgroup\$
    – ovs
    Feb 24, 2021 at 8:02
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 45 bytes

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.

\$\endgroup\$
3
  • \$\begingroup\$ &&f(q)+1 is acceptable. \$\endgroup\$
    – Arnauld
    Feb 24, 2021 at 11:27
  • \$\begingroup\$ 47 bytes, I think. \$\endgroup\$
    – Arnauld
    Feb 24, 2021 at 14:23
  • \$\begingroup\$ @Arnauld That's works. And luckily, we do not need to initial p. When p contains at least 2 elements, math operator convert to NaN. When p contains only 1 element, p-x yield 0, and [0] is still all falsy. \$\endgroup\$
    – tsh
    Feb 25, 2021 at 1:44
2
\$\begingroup\$

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

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

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!

\$\endgroup\$
6
  • 3
    \$\begingroup\$ "69 bytes". nice. \$\endgroup\$
    – lyxal
    Feb 24, 2021 at 5:22
  • \$\begingroup\$ @Lyxal Unfortunately I had to golf it :/ \$\endgroup\$ Feb 24, 2021 at 5:25
  • \$\begingroup\$ you need to update your link \$\endgroup\$
    – Razetime
    Feb 24, 2021 at 5:30
  • \$\begingroup\$ @Razetime Done, sorry about that \$\endgroup\$ Feb 24, 2021 at 5:31
  • \$\begingroup\$ f=p=>p.some(x=>x-p[0])?f(p.slice(1).map((x,j)=>x-p[j]))+1:0 is only 59 bytes. \$\endgroup\$
    – Neil
    Feb 24, 2021 at 11:46
2
\$\begingroup\$

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

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.

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

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)

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

Stax, 9 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
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 24 bytes

W⁻⌈θ⌊θ«UMθ⁻§θ⊕λκ⊞υ⊟θ»ILυ

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

W⁻⌈θ⌊θ«

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

UMθ⁻§θ⊕λκ

... 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).

»ILυ

Print the final number of iterations.

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

Julia, 25 bytes

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

Try it online!

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

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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