Desafío

El desafío es escribir un programa que tome los coeficientes de cualquier ecuación polinómica de n grados como entrada y devuelva los valores integrales de x para los que la ecuación es verdadera. Los coeficientes se proporcionarán como entrada en el orden de potencia decreciente o creciente. Puede asumir que todos los coeficientes son enteros .

Entrada y salida

La entrada será los coeficientes de la ecuación en orden decreciente o creciente de potencia. El grado de la ecuación, es decir, la potencia máxima de x, es siempre 1 menor que el total de elementos en la entrada.

Por ejemplo:

[1,2,3,4,5] -> represents x^4 + 2x^3 + 3x^2 + 4x + 5 = 0 (degree = 4, as there are 5 elements)
[4,0,0,3] -> represents 4x^3 + 3 = 0 (degree = 3, as there are 3+1 = 4 elements)

Su salida debe ser solo los distintos valores integrales de x que satisfacen la ecuación dada. Todos los coeficientes de entrada son enteros y el polinomio de entrada no será un polinomio cero . Si no hay una solución para la ecuación dada, entonces la salida no está definida.

Si una ecuación tiene raíces repetidas, muestre esa raíz en particular solo una vez. Puede generar los valores en cualquier orden. Además, suponga que la entrada contendrá al menos 2 números.

Ejemplos

[1,5,6] -> (-3,-2)
[10,-42,8] -> (4)
[1,-2,0] -> (0,2)
[1, 1, -39, -121, -10, 168] -> (-4, -3, -2, 1, 7)
[1, 0, -13, 0, 36] -> (-3, -2, 2, 3)
[1,-5] -> (5)
[1,2,3] -> -

Tenga en cuenta que la ecuación en el segundo ejemplo también tiene la raíz 0.2, pero no se muestra ya que 0.2 no es un número entero.

Puntuación

Este es el código de golf , por lo que gana el código más corto (en bytes).

MATL , 13 12 bytes

|stE:-GyZQ~)

Pruébalo en línea!

Esto usa el hecho que, para coeficientes enteros, el valor absoluto de cualquier raíz es estrictamente menor que la suma de los valores absolutos de los coeficientes.

Explicación

Considere la entrada [1 5 6]como un ejemplo.

|    % Implicit input. Absolute value
     % STACK: [1 5 6]
s    % Sum
     % STACK: 12
t    % Duplicate
     % STACK: 12, 12
E    % Multiply by 2
     % STACK: 12, 24
:    % Range
     % STACK: 12, [1 2 ... 23 24]
-    % Subtract, elemet-wise
     % STACK: [11 10 ... -11 -12]
G    % Push input again
     % STACK: [11 10 ... -11 -12], [1 5 6]
y    % Duplicate from below
     % STACK: [11 10 ... -11 -12], [1 5 6], [11 10 ... -11 -12]
ZQ   % Polyval: values of polynomial at specified inputs
     % STACK: [11 10 ... -11 -12], [182 156 ... 72 90]
~    % Logical negation: turns nonzero into zero
     % STACK: [11 10 ... -11 -12], [0 0 ... 0] (contains 1 for roots)
)    % Index: uses second input as a mask for the first. Implicit display
     % STACK: [-3 -2]

Casco , 10 9 bytes

-1 byte gracias a Zgarb

uSȯf¬`Bṁṡ

Pruébalo en línea!

Explicación

       ṁṡ   Concatenate together the symmetric ranges of each coefficient
            (It is guaranteed that the integer roots lie in the range [-n..n],
                        where n is the coefficient with the largest magnitude)
 Sȯf        Find all the values in that range which
    ¬       are zero
     `B     when plugged through the polynomial
            (Base conversion acts as polynomial evaluation)
u           De-duplicate the roots

Haskell , 54 bytes

f l|t<-sum$abs<$>l=[i|i<-[-t..t],foldl1((+).(i*))l==0]

Pruébalo en línea!

Fuerza bruta y división sintética.

Ungolfed con UniHaskell y-XUnicodeSyntax

import UniHaskell

roots    ∷ Num a ⇒ [a] → [a]
roots xs = [r | r ← -bound … bound, foldl1 ((+) ∘ (r ×)) xs ≡ 0]
             where bound = sum $ abs § xs

Solución alternativa, 44 bytes.

Crédito a nimi.

f l=[i|i<-[minBound..],foldl1((+).(i*))l==0]

Buena suerte al intentarlo en línea , ya que esto verifica cada número en Intel rango de un.

Python 2 + numpy, 95 93 91 103 93 91 82 bytes

^{-2 bytes gracias a ovs
gracias Luis Mendo por los límites superior / inferior de las raíces
-10 bytes gracias al Sr. Xcoder}

from numpy import*
def f(r):s=sum(fabs(r));q=arange(-s,s);print q[polyval(r,q)==0]

Pruébalo en línea!

Wolfram Language (Mathematica) , 50 47 42 25 27 bytes

{}⋃Select[x/.Solve[#~FromDigits~x==0],IntegerQ]&

Pruébalo en línea!

Actualización: usando el hecho de Luis Mendo, jugó otros 3 bytes

Pick[r=Range[s=-Tr@Abs@#,-s],#~FromDigits~r,0]&

Volviendo más descuidado con los límites, podemos reducir estos 5 bytes más por @No la sugerencia de un árbol:

Pick[r=Range[s=-#.#,-s],#~FromDigits~r,0]&

Después de publicar esto, OP comentó que permite "polinomios nativos", así que aquí hay una solución de 25 bytes que acepta el polinomio como entrada. Esto funciona porque por defecto Mathematica factoriza polinomios sobre los enteros, y cualquier raíz racional aparece en una forma como m*x+besa falla la coincidencia de patrones.

Cases[Factor@#,b_+x:>-b]&

Como señaló @alephalpha, esto fallará en el caso de que cero sea una raíz, por lo que para solucionarlo podemos usar el Optionalsímbolo:

Cases[Factor@#,b_:0+x:>-b]&

Esto analiza Mathematica 11.0.1 pero falla y requiere un conjunto adicional de paréntesis b_:0en la versión 11.2. Esto ocupa una copia de seguridad de hasta 27 bytes, más dos más después de la versión 11.0.1. Parece que se puso una "solución" aquí

Pruébalo en línea!

Wolfram Language (Mathematica) , 33 26 31 bytes

Se corrigió un error observado por Kelly Lowder en los comentarios.

x/.{}⋃Solve[#==0,x,Integers]&

Pruébalo en línea!

Soluciones incorrectas anteriores:

Me acabo de dar cuenta de que para una solución sin número entero, la salida no está definida en lugar de una lista vacía; eso permite eliminar algunos bytes.

x/.Solve[#==0,x,Integers]&

Pruébalo en línea!

Ahora, si no existe una solución entera, la función devuelve x .

Previamente:

x/.Solve[#==0,x,Integers]/.x->{}&

Pruébalo en línea!

R , 61 59 bytes

¡Un agradecimiento especial a @mathmandan por señalar mi enfoque (incorrecto) podría salvarse y jugar golf!

function(p)(x=-(t=p[!!p][1]):t)[!outer(x,seq(p)-1,"^")%*%p]

Pruébalo en línea!

Toma la entrada como una lista de coeficientes en orden creciente , es decir, c(-1,0,1)representa-1+0x+1x^2 .

Usando el teorema de la raíz racional, el siguiente enfoque casi funciona, para 47 bytes:

function(p)(x=-p:p)[!outer(x,seq(p)-1,"^")%*%p]

Pruébalo en línea!

-p:pgenera un rango simétrico (con una advertencia) usando sólo el primer elemento de p, a_0. Según el teorema de la raíz racional , todas las raíces racionales Pdeben tener la forma p/qen que pdivide a_0y qdividea_n (más o menos). Por lo tanto, usando sólo a_0es suficiente para |a_0|>0, como para cualquier q, |p/q|<=a_0. Sin embargo, cuando a_0==0, como entonces, cualquier entero se divide 0, y por lo tanto esto falla.

Sin embargo, Mathmandan señala que realmente, en este caso, esto significa que hay un factor constante x^kque puede ser factorizado, y, suponiendo que ksea ​​máximo, vemos que

P(x) = x^k(a_k + a_{k+1}x + ... a_n x^{n-k}) = x^k * Q(x)

Luego aplicamos el teorema de la raíz racional a Q(x), y comoa_k se garantiza que no es cero por la maximidad de k, a_kproporciona un límite ordenado para las raíces enteras de Q, y las raíces de Pson las raíces deQ junto con cero, por lo que tendremos todo el entero raíces deP mediante la aplicación de este método.

Esto es equivalente a encontrar el primer coeficiente distinto de cero del polinomio t=p[!!p][1]y usarlo en lugar de lo ingenuo p[1]como límites. Además, desde el rango-t:t siempre contiene cero, se aplicaP a este rango aún nos daría cero como raíz, si es que lo es.

sin golf:

function(polynom) {
 bound <- polynom[polynom != 0][1]             #first nonzero value of polynom
 range <- -bound:bound                         #generates [-bound, ..., bound]
 powers <- outer(range,seq_along(p) - 1, "^")  #matrix where each row is [n^0,n^1,n^2,...,n^deg(p)]
 polyVals <- powers %*% polynom                #value of the polynomial @ each point in range
 return(range[polyVals == 0])                  #filter for zeros and return
}

Jalea , 8 bytes

ASŒRḅ@Ðḟ

Pruébalo en línea! o como una suite de prueba!

¿Cómo?

ASŒRḅ @ Ðḟ || Programa completo (enlace monádico).

AS || Suma los valores absolutos.
  ŒR || Y cree el rango simétrico inclusivo a partir de su valor negativo.
       Ðḟ || Y descarte aquellos que producen un valor verdadero ...
     ḅ @ || Al conectarlos al polinomio (usa conversión de base).

Basado en la respuesta de Luis . Una alternativa .

Octava , 59 49 bytes

@(p)(x=-(t=p(~~p)(end)):sign(t):t)(!polyval(p,x))

Pruébalo en línea!

Este es un puerto de mi R respuesta . La única diferencia es que tengo que usar explícitamente sign(t)y endgenerar el rango, y que tiene polyvalque calcular el polinomio.

Toma la entrada como un vector fila de coeficientes en orden decreciente.

Pari / GP , 31 bytes

p->[x-a|a<-factor(p)[,1],a'==1]

Factores del polinomio, y selecciona los factores cuyas derivadas son 1.

Pruébalo en línea!

C (gcc) , 127 126 123 bytes

• Salvado un byte gracias a Kevin Cruijssen ; golf l+~j++a l-++j.
• Gracias a ceilingcat por guardar tres bytes.

x,X,j,m,p;f(A,l)int*A;{for(m=j=0;j<l;m+=abs(A[j++]));for(x=~m;X=x++<m;p||printf("%d,",x))for(p=j=0;j<l;X*=x)p+=A[l-++j]*X;}

Pruébalo en línea!

Explicación

C (gcc) , 517 bytes

x,X,j,m,p;                      // global integer variables
f(A,l)int*A;{                   // define function, takes in integer array pointer and length
 for(m=j=0;j<l;m+=abs(A[j++])); // loop through array, sum up absolute values
  for(x=~m;X=x++<m;             // loop through all values x in [-m, m], prime X
   p||printf("%d,",x))          // at loop's end, print x value if polynomial value is zero
    for(p=j=0;j<l;X*=x)         // loop through coefficients
     p+=A[l-++j]*X;}            // build polynomial

Pruébalo en línea!

Java 8, 141 140 bytes

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

Inspirado por la respuesta Python 2 de @Rod (su versión de 82 bytes) .

Desafío divertido! Ciertamente aprendí mucho al investigar sobre polinomios y ver cómo otros aquí lo han hecho.

Explicación:

Pruébalo en línea.

a->{                   // Method with integer-array parameter and no return-type
  int l=a.length,      //  The length of the input-array
      s=0,             //  Sum-integer, starting at 0
      i,               //  Index integer
      r,               //  Range-integer
      f,               //  Factor-integer
      p;               //  Polynomial-integer
  for(int n:a)         //  Loop over the input-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)
      System.out.print(p==0?r+",":""))
                       //    After every iteration: print the current `r` if `p` is 0
    for(p=i=0,         //   Reset `p` to 0
        f=1;           //   and `f` to 1
        i<l;           //   Loop over the input-array 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[l-++i]      //     The value of the input at index `l-i-1`,
                 *f;}  //     multiplied with the current factor `f`

Octava con paquete simbólico, 63 bytes

@(p)(s=double(solve(poly2sym(p)==0)))(s==(t=real(s))&~mod(t,1))

Pruébalo en línea!

05AB1E , 8 bytes

ÄOD(Ÿʒβ>

Pruébalo en línea!

JavaScript (ES6), 97 bytes

a=>[...Array((n=Math.max(...a.map(Math.abs)))-~n)].map(_=>n--).filter(i=>!a.reduce((x,y)=>x*i+y))

Toma coeficientes en orden decreciente de potencia y produce resultados en orden descendente.

Limpio , 110 91 bytes

import StdEnv
?p#s=sum p
=[i\\i<-[~s..s]|i<>0&&sum[e*i^t\\t<-reverse(indexList p)&e<-p]==0]

Pruébalo en línea!

Python 2 , 89 bytes

def f(a):s=sum(map(abs,a));return[n for n in range(-s,s)if reduce(lambda v,c:v*n+c,a)==0]

Pruébalo en línea!