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!
x
values? \$\endgroup\$(0, 42)
and(0, 0)
valid testcases? \$\endgroup\$x
values are unnecessary for any method of finding the degree, since the degree of a polynomialf(x)
is the same as the degree off(x - a)
for some constanta
. So we can always assume thex
values in the sequence start from 0 and get the correct result. \$\endgroup\$