# Polynomialception

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
• what about builtins? Apr 23, 2016 at 22:15
• @Maltysen "Details: Builtins are allowed.(...)" :D Apr 23, 2016 at 22:17
• I think "any reasonable format" might be a bit stretchable. If a function that evaluates the polynomial is allowed, then the composition function (.) is an answer in Haskell. You probably mean some representation of the list of coefficients.
– xnor
Apr 24, 2016 at 0:03
• The title! I just got it :-D Apr 24, 2016 at 11:46
• @LuisMendo Quick thinker =P Apr 24, 2016 at 11:53

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.

# 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

# 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
• It seems like cheating to me to require the inputs to be in different variables. Does that matter for this answer? Apr 23, 2016 at 22:43
• Feel free to do so, I explicitly allowed any reasonable convenient input format. Apr 23, 2016 at 22:45
• Concerning the edit of your comment: yes it does matter. Apr 23, 2016 at 23:06
• I'm not too familiar with the rules on this site. Is it correct for to be 1 byte in TI-BASIC? Apr 25, 2016 at 17:33
• @asmeurer Indeed: TI-Basic is scored by the encoding used on the corresponding calculators. If you are interested in the details, you can read that here on meta. A table of tokens can be found here on ti-basic-dev. Apr 25, 2016 at 19:35

# 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.

• Nice method. For B, would 10**len(a+b) be enough?
– xnor
Apr 24, 2016 at 1:30
• @xnor Maybe... it's hard for me to tell. Apr 24, 2016 at 1:50
• +1 This is a really creative solution, and a nice use of bigints!!! Apr 24, 2016 at 9:56
• @xnor Now I've managed to convince myself that hte coefficient length is linear in the input length :) Apr 24, 2016 at 14:14

# 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
• SymPy has a compose() function. Apr 24, 2016 at 16:30
• Where's the answer? It no longer defines any functions or does anything... Apr 24, 2016 at 19:11
• @feersum That has never been the case. You just edited that meta post.
– user45941
Apr 24, 2016 at 21:19
• @feersum You edited an accepted meta post to modify the policy for your own agenda. That's not ok.
– user45941
Apr 24, 2016 at 21:22
• @feersum Though you may have thought your wording was ambiguous, it clearly was not for the rest of the community. We accepted the consensus that from module import*;function was a valid submission. Regardless, this is a more recent policy, which allows imports and helper functions with unnamed lambdas.
– user45941
Apr 24, 2016 at 21:55

## 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

# 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

# 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

# Python 2, 239232 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.

• Is m([c],e(m,[[1]]+[g]*k)) not the same as e(m,[[c]]+[g]*k)?
– Neil
Apr 24, 2016 at 20:28
• @Neil Good call, can squash two in one with that!
– orlp
Apr 24, 2016 at 20:48
• a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l) Apr 24, 2016 at 20:59
• @AndersKaseorg Right, I added it, thanks :)
– orlp
Apr 24, 2016 at 21:12
• It might be possible to simplify your polynomial addition, since I think one list will always be longer than the other, so you don't need the ( or 0) in that version.
– Neil
Apr 25, 2016 at 0:04

## 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 = [a0, a1, a2, ...] that represents a0 + a1*x + a2*x2 ...

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 gh, which starts at one. p is multiplied by each fh 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

# Pyth, 51 34 bytes

AQsM.t*LVG.usM.t.e+*]0k*LbHN0tG]1Z
• when python outgolfs pyth Apr 24, 2016 at 19:14
• @downrep_nation not anymore :) Aug 4, 2017 at 5:52

# 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}