Polinomialcepção

22

Dados dois polinômios f,gde grau arbitrário sobre os números inteiros, seu programa / função deve avaliar o primeiro polinômio no segundo polinômio. f(g(x))(aka a composição (fog)(x) dos dois polinômios)

Detalhes

Builtins são permitidos. Você pode assumir qualquer formatação razoável como entrada / saída, mas o formato de entrada e saída deve corresponder. Por exemplo, formatação como uma string

x^2+3x+5

ou como lista de coeficientes:

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

Além disso, os polinômios de entrada podem ser assumidos como totalmente expandidos e as saídas também devem ser totalmente expandidas.

Exemplos

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
flawr
fonte
e quanto aos embutidos?
Maltysen
1
@Maltysen "Detalhes: Builtins são permitidos. (...)" : D
flawr
2
Eu acho que "qualquer formato razoável" pode ser um pouco elástico. Se uma função que avalia o polinômio é permitida, a função de composição (.)é uma resposta em Haskell. Você provavelmente quer dizer alguma representação da lista de coeficientes.
Xnor
1
O título! Eu só tenho que :-D
Luis Mendo
2
@LuisMendo Quick thinker = P
flawr

Respostas:

10

Haskell, 86 72 bytes

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

Define uma função otal que o g fcalcula a composição f ∘ g. Polinômios são representados por uma lista não vazia de coeficientes começando no termo constante.

Demo

*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]

Como funciona

Nenhum built-in ou bibliotecas relacionadas a polinômios. Observe as recorrências semelhantes

(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 multiplicação polinomial e composição, respectivamente. Ambos assumem a forma

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

O operador !resolve uma recorrência desse formulário para W, dado U e C, usando zipWith(+).(++[0,0..])para adição polinomial (assumindo que o segundo argumento seja mais longo - para nossos propósitos, sempre será). Então,

(0:)multiplica um argumento polinomial por x (acrescentando um coeficiente zero);
(<$>g).(*)multiplica um argumento escalar pelo polinômio g;
(0:)!((<$>g).(*))multiplica um argumento polinomial pelo polinômio g;
pureeleva um argumento escalar para um polinômio constante (lista de singleton);
(0:)!((<$>g).(*))!purecompõe um argumento polinomial com o polinômio g.

Anders Kaseorg
fonte
9

Mathematica, 17 bytes

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

Exemplo 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
fonte
7

TI-Basic 68k, 12 bytes

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

O uso é direto, por exemplo, para o primeiro exemplo:

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

Que retorna

y^2+5y+9
flawr
fonte
Parece-me trapaça exigir que as entradas estejam em variáveis ​​diferentes. Isso importa para esta resposta?
feersum
Sinta-se à vontade para fazê-lo, eu permiti explicitamente qualquer formato de entrada conveniente e razoável.
flawr
Em relação à edição do seu comentário: sim, isso importa.
flawr
Não estou muito familiarizado com as regras deste site. Está correto para ter 1 byte no TI-BASIC?
asmeurer
@asmeurer De fato: o TI-Basic é pontuado pela codificação usada nas calculadoras correspondentes. Se você estiver interessado nos detalhes, pode ler isso aqui na meta . Uma tabela de tokens pode ser encontrada aqui em ti-basic-dev .
flawr
6

Python 2, 138 156 162 bytes

As entradas devem ser listas inteiras com os menores poderes primeiro.

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

Ungolfed:

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

Neste cálculo, os coeficientes polinomiais são vistos como dígitos (que podem ser negativos) de um número em uma base muito grande. Depois que os polinômios estão nesse formato, a multiplicação ou adição é uma operação inteira única. Desde que a base seja suficientemente grande, não haverá carregamentos que se espalhem para os dígitos vizinhos.

-18 de melhorar o limite, Bconforme sugerido por @xnor.

feersum
fonte
Bom método. Pois B, seria o 10**len(`a+b`)suficiente?
Xnor
@ xnor Talvez ... seja difícil para mim dizer.
feersum
+1 Esta é uma solução realmente criativa e um bom uso de bigints !!!
flawr
@xnor Agora eu consegui me convencer de que o comprimento do coeficiente de hte é linear no comprimento de entrada :)
feersum
5

Python + SymPy, 59 35 bytes

from sympy import*
var('x')
compose

Obrigado a @asmeurer por jogar fora 24 bytes!

Execução de teste

>>> from sympy import*
>>> var('x')
x
>>> f = compose
>>> f(x**2 + 3*x + 5, x + 1)
x**2 + 5*x + 9
Dennis
fonte
1
SymPy tem uma compose()função.
Asmeurer #
1
Onde está a resposta? Já não define quaisquer funções ou faz alguma coisa ...
feersum
1
@feersum Esse nunca foi o caso. Você acabou de editar essa meta postagem.
Mego
3
@feersum Você editou uma meta post aceita para modificar a política de sua própria agenda. Isso não está bem.
Mego 24/04
3
@feersum Embora você tenha pensado que sua redação era ambígua, claramente não era para o resto da comunidade. Aceitamos o consenso de que from module import*;functionera um envio válido. Independentemente disso, essa é uma política mais recente, que permite funções de importação e auxiliar com lambdas sem nome.
Mego
3

Sábio, 24 bytes

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

A partir do Sage 6.9 (a versão que é executada em http://sagecell.sagemath.org ), as chamadas de função sem atribuição explícita de argumentos ( f(2) rather than f(x=2)) fazem com que uma mensagem irritante e inútil seja impressa no STDERR. Como STDERR pode ser ignorado por padrão no código golf, isso ainda é válido.

Isso é muito semelhante à resposta SymPy de Dennis porque o Sage é a) construído em Python eb) usa o Maxima , um sistema de álgebra computacional muito semelhante ao SymPy de várias maneiras. No entanto, o Sage é muito mais poderoso que o Python com o SymPy e, portanto, é uma linguagem suficientemente diferente para merecer sua própria resposta.

Verifique todos os casos de teste online

Mego
fonte
2

PARI / GP , 19 bytes

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

o que permite fazer

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

para obter

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

Charles
fonte
1

MATLAB com caixa de ferramentas simbólica, 28 bytes

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

Esta é uma função anônima. Para chamá-lo, atribua a uma variável ou use ans. As entradas são cadeias de caracteres com o formato (os espaços são opcionais)

x^2 + 3*x + 5

Exemplo de execução:

>> @(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
fonte
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)])

Uma implementação 'adequada' que não abuse das bases. Coeficiente menos significativo primeiro.

aé adição polinomial, mé multiplicação polinomial e oé composição.

orlp
fonte
Não m([c],e(m,[[1]]+[g]*k))é o mesmo que e(m,[[c]]+[g]*k)?
24416 Neil
@ Neil Boa chamada, pode esmagar dois em um com isso!
orlp
a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
precisa saber é o seguinte
@AndersKaseorg direito, eu adicionei-o, graças :)
orlp
Talvez seja possível simplificar sua adição polinomial, pois acho que uma lista sempre será mais longa que a outra, portanto, você não precisa ( or 0)dessa versão.
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

Aceita e retorna polinômios como uma matriz a = [a 0 , a 1 , a 2 , ...] que representa um 0 + a 1 * x + a 2 * x 2 ...

Editar: salvou 47 bytes alternando da multiplicação polinomial recursiva para iterativa, o que me permitiu mesclar duas mapchamadas.

Explicação: r é o resultado, que começa em zero, representado por uma matriz vazia ep é g h , que começa em uma. p é multiplicado por cada f h por sua vez, e o resultado acumulado em r . p também é multiplicado por g ao mesmo tempo.

(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
fonte
1

Pyth, 51 34 bytes

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

Suíte de teste .

Freira Furada
fonte
2
quando pyth python outgolfs
downrep_nation
@downrep_nation não é mais :) #
Leaky
1

Ruby 2.4 + polinomial , 41 + 12 = 53 bytes

Usa sinalizador -rpolynomial. Entrada é doisPolynomial objetos.

Se alguém me derrotar em baunilha Ruby (nenhuma biblioteca externa polinomial), ficarei muito impressionado.

->a,b{i=-1;a.coefs.map{|c|c*b**i+=1}.sum}
Value Ink
fonte