Polinomialcepción

22

Dados dos polinomios f,gde grado arbitrario sobre los enteros, su programa / función debe evaluar el primer polinomio en el segundo polinomio. f(g(x))(también conocida como la composición (fog)(x) de los dos polinomios)

Detalles

Las construcciones están permitidas. Puede asumir cualquier formato razonable como entrada / salida, pero el formato de entrada y salida debe coincidir. Ej. Formatear como una cadena

x^2+3x+5

o como una lista de coeficientes:

[1,3,5] or alternatively [5,3,1]

Además, se puede suponer que los polinomios de entrada están completamente expandidos, y también se espera que las salidas estén completamente expandidas.

Ejemplos

A(x) = x^2 + 3x + 5, B(y) = y+1
A(B(y)) = (y+1)^2 + 3(y+1) + 5 = y^2 + 5y + 9

A(x) = x^6 + x^2 + 1, B(y) = y^2 - y
A(B(y))= y^12 - 6y^11 + 15y^10 - 20y^9 + 15y^8 - 6y^7 + y^6 + y^4 - 2 y^3 + y^2 + 1

A(x) = 24x^3 - 144x^2 + 288x - 192, B(y) = y + 2
A(B(y)) = 24y^3

A(x) = 3x^4 - 36x^3 + 138x^2 - 180x + 27, B(y) = 2y + 3
A(B(y)) = 48y^4 - 96y^2
falla
fuente
¿Qué pasa con los builtins?
Maltysen
1
@Maltysen "Detalles: las construcciones están permitidas. (...)" : D
flawr
2
Creo que "cualquier formato razonable" podría ser un poco estirable. Si se permite una función que evalúa el polinomio, entonces la función de composición (.)es una respuesta en Haskell. Probablemente se refiera a alguna representación de la lista de coeficientes.
xnor
1
¡El título! Lo acabo de recibir :-D
Luis Mendo
2
@LuisMendo Pensador rápido = P
error

Respuestas:

10

Haskell, 86 72 bytes

u!c=foldr1((.u).zipWith(+).(++[0,0..])).map c
o g=(0:)!((<$>g).(*))!pure

Define una función otal que o g fcalcula la composición f ∘ g. Los polinomios están representados por una lista no vacía de coeficientes que comienza en el término constante.

Manifestación

*Main> o [1,1] [5,3,1]
[9,5,1]
*Main> o [0,-1,1] [1,0,1,0,0,0,1]
[1,0,1,-2,1,0,1,-6,15,-20,15,-6,1]
*Main> o [2,1] [-192,288,-144,24]
[0,0,0,24]
*Main> o [3,2] [27,-180,138,-36,3]
[0,0,-96,0,48]

Cómo funciona

No hay bibliotecas o bibliotecas integradas relacionadas con el polinomio. Observe las recurrencias similares.

f (x) = a + f₁ (x) x ⇒ f (x) g (x) = ag (x) + f₁ (x) g (x) x,
f (x) = a + f₁ (x) x ⇒ f (g (x)) = a + f₁ (g (x)) g (x),

para multiplicación polinómica y composición, respectivamente. Ambos toman la forma

f (x) = a + f₁ (x) x ⇒ W (f) (x) = C (a) (x) + U (W (f₁)) (x).

El operador !resuelve una recurrencia de esta forma para W dado U y C, utilizando zipWith(+).(++[0,0..])para la suma polinómica (suponiendo que el segundo argumento sea más largo, para nuestros propósitos, siempre lo será). Luego,

(0:)multiplica un argumento polinómico por x (anteponiendo un coeficiente cero);
(<$>g).(*)multiplica un argumento escalar por el polinomio g;
(0:)!((<$>g).(*))multiplica un argumento polinómico por el polinomio g;
purelevanta un argumento escalar a un polinomio constante (lista única);
(0:)!((<$>g).(*))!purecompone un argumento polinomial con el polinomio g.

Anders Kaseorg
fuente
9

Mathematica, 17 bytes

Expand[#/.x->#2]&

Ejemplo de uso:

In[17]:= Expand[#/.x->#2]& [27 - 180x + 138x^2 - 36x^3 + 3x^4, 3 + 2x]

              2       4
Out[17]= -96 x  + 48 x
Feersum
fuente
7

TI-Basic 68k, 12 bytes

a|x=b→f(a,b)

El uso es sencillo, por ejemplo, para el primer ejemplo:

f(x^2+3x+5,y+1)

Que vuelve

y^2+5y+9
falla
fuente
Me parece una trampa hacer que las entradas estén en diferentes variables. ¿Importa eso para esta respuesta?
feersum
Siéntase libre de hacerlo, permití explícitamente cualquier formato de entrada conveniente y razonable.
flawr
En cuanto a la edición de su comentario: sí, sí importa.
flawr
No estoy muy familiarizado con las reglas de este sitio. ¿Es correcto ser 1 byte en TI-BASIC?
asmeurer
@asmeurer De hecho: TI-Basic se puntúa mediante la codificación utilizada en las calculadoras correspondientes. Si está interesado en los detalles, puede leerlo aquí en meta . Puede encontrar una tabla de tokens aquí en ti-basic-dev .
flawr
6

Python 2, 138156162 bytes

Se espera que las entradas sean listas enteras con las potencias más pequeñas primero.

def c(a,b):
 g=lambda p,q:q>[]and q[0]+p*g(p,q[1:]);B=99**len(`a+b`);s=g(g(B,b),a);o=[]
 while s:o+=(s+B/2)%B-B/2,;s=(s-o[-1])/B
 return o

Sin golf:

def c(a,b):
 B=sum(map(abs,a+b))**len(a+b)**2
 w=sum(B**i*x for i,x in enumerate(b))
 s=sum(w**i*x for i,x in enumerate(a))
 o=[]
 while s:o+=min(s%B,s%B-B,key=abs),; s=(s-o[-1])/B
 return o

En este cálculo, los coeficientes polinómicos se ven como dígitos (que pueden ser negativos) de un número en una base muy grande. Una vez que los polinomios están en este formato, la multiplicación o suma es una operación entera única. Mientras la base sea lo suficientemente grande, no habrá ningún acarreo que se extienda a los dígitos vecinos.

-18 de mejorar el límite Bsegún lo sugerido por @xnor.

Feersum
fuente
Buen método Para B, sería 10**len(`a+b`)suficiente?
xnor
@xnor Quizás ... es difícil para mí decirlo.
feersum
+1 ¡Esta es una solución realmente creativa y un buen uso de bigints!
flawr
@xnor Ahora he logrado convencerme de que la longitud del coeficiente es lineal en la longitud de entrada :)
feersum
5

Python + SymPy, 59 35 bytes

from sympy import*
var('x')
compose

¡Gracias a @asmeurer por jugar golf en 24 bytes!

Prueba de funcionamiento

>>> from sympy import*
>>> var('x')
x
>>> f = compose
>>> f(x**2 + 3*x + 5, x + 1)
x**2 + 5*x + 9
Dennis
fuente
1
SymPy tiene una compose()función.
asmeurer
1
¿Dónde está la respuesta? Ya no define ninguna función ni hace nada ...
feersum
1
@feersum Ese nunca ha sido el caso. Acabas de editar esa meta publicación.
Mego
3
@feersum Editó una meta publicación aceptada para modificar la política de su propia agenda. Eso no esta bien.
Mego
3
@feersum Aunque haya pensado que su redacción era ambigua, claramente no era para el resto de la comunidad. Aceptamos el consenso de que from module import*;functionera una presentación válida. De todos modos, esta es una política más reciente, que permite importaciones y funciones auxiliares con lambdas sin nombre.
Mego
3

Sabio, 24 bytes

lambda A,B:A(B).expand()

A partir de Sage 6.9 (la versión que se ejecuta en http://sagecell.sagemath.org ), las llamadas a funciones sin asignación explícita de argumentos ( f(2) rather than f(x=2)) hacen que se imprima un mensaje molesto e inútil en STDERR. Debido a que STDERR puede ignorarse por defecto en el código de golf, esto todavía es válido.

Esto es muy similar a la respuesta SymPy de Dennis porque Sage está a) construido en Python, yb) usa Maxima , un sistema de álgebra computacional muy similar a SymPy en muchos aspectos. Sin embargo, Sage es mucho más poderoso que Python con SymPy y, por lo tanto, es un lenguaje lo suficientemente diferente como para merecer su propia respuesta.

Verifique todos los casos de prueba en línea

Mego
fuente
2

PARI / GP , 19 bytes

(a,b)->subst(a,x,b)

que te permite hacer

%(x^2+1,x^2+x-1)

Llegar

% 2 = x ^ 4 + 2 * x ^ 3 - x ^ 2 - 2 * x + 2

Charles
fuente
1

MATLAB con caja de herramientas simbólica, 28 bytes

@(f,g)collect(subs(f,'x',g))

Esta es una función anónima. Para llamarlo, asígnelo a una variable o use ans. Las entradas son cadenas con el formato (los espacios son opcionales)

x^2 + 3*x + 5

Ejemplo de ejecución:

>> @(f,g)collect(subs(f,'x',g))
ans = 
    @(f,g)collect(subs(f,'x',g))
>> ans('3*x^4 - 36*x^3 + 138*x^2 - 180*x + 27','2*x + 3')
ans =
48*x^4 - 96*x^2
Luis Mendo
fuente
1

Python 2, 239 232 223 bytes

r=range
e=reduce
a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
m=lambda p,q:[sum((p+k*[0])[i]*(q+k*[0])[k-i]for i in r(k+1))for k in r(len(p+q)-1)]
o=lambda f,g:e(a,[e(m,[[c]]+[g]*k)for k,c in enumerate(f)])

Una implementación 'adecuada' que no abusa de las bases. Coeficiente menos significativo primero.

aes una suma polinómica, mes una multiplicación polinómica y oes composición.

orlp
fuente
¿ m([c],e(m,[[1]]+[g]*k))No es lo mismo que e(m,[[c]]+[g]*k)?
Neil
@Neil Good call, ¡puedes aplastar dos en uno con eso!
orlp
a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
Anders Kaseorg
@AndersKaseorg Correcto, lo agregué, gracias :)
orlp
Podría ser posible simplificar su adición polinómica, ya que creo que una lista siempre será más larga que la otra, por lo que no necesita la ( or 0)en esa versión.
Neil
1

Javascript (ES6), 150 103 bytes

(f,g)=>f.map(n=>r=p.map((m,i)=>(g.map((n,j)=>p[j+=i]=m*n+(p[j]||0)),m*n+(r[i]||0)),p=[]),r=[],p=[1])&&r

Acepta y devuelve polinomios como una matriz a = [a 0 , a 1 , a 2 , ...] que representa a 0 + a 1 * x + a 2 * x 2 ...

Editar: guardé 47 bytes al cambiar de multiplicación polinómica recursiva a iterativa, lo que me permitió fusionar dos mapllamadas.

Explicación: r es el resultado, que comienza en cero, representado por una matriz vacía, y p es g h , que comienza en uno. p se multiplica por cada f h a su vez, y el resultado se acumula en r . p también se multiplica por g al mismo tiempo.

(f,g)=>f.map(n=>            Loop through each term of f (n = f[h])
 r=p.map((m,i)=>(           Loop through each term of p (m = p[i])
  g.map((n,j)=>             Loop though each term of g (n = g[j])
   p[j+=i]=m*n+(p[j]||0)),  Accumulate p*g in p
  m*n+(r[i]||0)),           Meanwhile add p[i]*f[h] to r[i]
  p=[]),                    Reset p to 0 each loop to calculate p*g
 r=[],                      Initialise r to 0
 p=[1]                      Initialise p to 1
)&&r                        Return the result
Neil
fuente
1

Pyth, 51 34 bytes

AQsM.t*LVG.usM.t.e+*]0k*LbHN0tG]1Z

Banco de pruebas .

Monja permeable
fuente
2
cuando Python supera a pyth
downrep_nation
@downrep_nation ya no :)
Leaky Nun
1

Ruby 2.4 + polinomio , 41 + 12 = 53 bytes

Usa bandera -rpolynomial. La entrada es dos Polynomialobjetos.

Si alguien me supera en vainilla Ruby (sin biblioteca externa polinomial), quedaré muy impresionado.

->a,b{i=-1;a.coefs.map{|c|c*b**i+=1}.sum}
Tinta de valor
fuente