Polynomialception

Question

Given two polynomials f,g of arbitrary degree over the integers, your program/function should evaluate the first polynomial in the second polynomial. f(g(x)) (a.k.a. the composition (fog)(x) of the two polynomials)

Details

Builtins are allowed. You can assume any reasonable formatting as input/output, but the input and output format should match. E.g. formatting as a string

x^2+3x+5

or as as list of coefficients:

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

Furthermore the input polynomials can be assumed to be fully expanded, and the outputs are also expected to be fully expanded.

Examples

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

Answer 1

Haskell, 86 72 bytes

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

Defines a function o such that o g f computes the composition f ∘ g. Polynomials are represented by a nonempty list of coefficients starting at the constant term.

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]

How it works

No polynomial-related builtins or libraries. Observe the similar recurrences

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

for polynomial multiplication and composition, respectively. They both take the form

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

The operator ! solves a recurrence of this form for W given U and C, using zipWith(+).(++[0,0..]) for polynomial addition (assuming the second argument is longer—for our purposes, it always will be). Then,

(0:) multiplies a polynomial argument by x (by prepending a zero coefficient);
(<$>g).(*) multiplies a scalar argument by the polynomial g;
(0:)!((<$>g).(*)) multiplies a polynomial argument by the polynomial g;
pure lifts a scalar argument to a constant polynomial (singleton list);
(0:)!((<$>g).(*))!pure composes a polynomial argument with the polynomial g.

Answer 2

Mathematica, 17 bytes

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

Example usage:

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

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

Answer 3

TI-Basic 68k, 12 bytes

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

The usage is straightforward, e.g. for the first example:

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

Which returns

y^2+5y+9

Answer 4

Python 2, 138 156 162 bytes

The inputs are expected to be integer lists with smallest powers first.

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

In this computation, the polynomial coefficients are seen as digits (which may be negative) of a number in a very large base. After polynomials are in this format, multiplication or addition is a single integer operation. As long as the base is sufficiently large, there won't be any carries that spill over into neighboring digits.

-18 from improving bound on B as suggested by @xnor.

Answer 5

Python + SymPy, 59 35 bytes

from sympy import*
var('x')
compose

Thanks to @asmeurer for golfing off 24 bytes!

Test run

>>> from sympy import*
>>> var('x')
x
>>> f = compose
>>> f(x**2 + 3*x + 5, x + 1)
x**2 + 5*x + 9

Answer 6

Sage, 24 bytes

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

As of Sage 6.9 (the version that runs on http://sagecell.sagemath.org), function calls without explicit argument assignment (f(2) rather than f(x=2)) causes an annoying and unhelpful message to be printed to STDERR. Because STDERR can be ignored by default in code golf, this is still valid.

This is very similar to Dennis's SymPy answer because Sage is a) built on Python, and b) uses Maxima, a computer algebra system very similar to SymPy in many ways. However, Sage is much more powerful than Python with SymPy, and thus is a different enough language that it merits its own answer.

Verify all test cases online

Answer 7

PARI/GP, 19 bytes

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

which lets you do

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

to get

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

Answer 8

Ruby 2.4 + polynomial, 41+12 = 53 bytes

Uses flag -rpolynomial. Input is two Polynomial objects.

If someone outgolfs me in vanilla Ruby (no polynomial external library), I will be very impressed.

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

Answer 9

MATLAB with Symbolic Toolbox, 28 bytes

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

This is an anonymous function. To call it assign it to a variable or use ans. Inputs are strings with the format (spaces are optional)

x^2 + 3*x + 5

Example run:

>> @(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

Answer 10

Pyth, 51 34 bytes

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

Test suite.

Answer 11

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

A 'proper' implementation that does not abuse bases. Least significant coefficient first.

a is polynomial addition, m is polynomial multiplication, and o is composition.

Answer 12

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

Accepts and returns polynomials as an array a = [a₀, a₁, a₂, ...] that represents a₀ + a₁*x + a₂*x² ...

Edit: Saved 47 bytes by switching from recursive to iterative polynomial multiplication, which then allowed me to merge two map calls.

Explanation: r is the result, which starts at zero, represented by an empty array, and p is g^h, which starts at one. p is multiplied by each f_h in turn, and the result accumulated in r. p is also multiplied by g at the same time.

(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