22
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ what about builtins? \$\endgroup\$ – Maltysen Apr 23 '16 at 22:15
  • 1
    \$\begingroup\$ @Maltysen "Details: Builtins are allowed.(...)" :D \$\endgroup\$ – flawr Apr 23 '16 at 22:17
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – xnor Apr 24 '16 at 0:03
  • 1
    \$\begingroup\$ The title! I just got it :-D \$\endgroup\$ – Luis Mendo Apr 24 '16 at 11:46
  • 2
    \$\begingroup\$ @LuisMendo Quick thinker =P \$\endgroup\$ – flawr Apr 24 '16 at 11:53

12 Answers 12

10
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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
\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ It seems like cheating to me to require the inputs to be in different variables. Does that matter for this answer? \$\endgroup\$ – feersum Apr 23 '16 at 22:43
  • \$\begingroup\$ Feel free to do so, I explicitly allowed any reasonable convenient input format. \$\endgroup\$ – flawr Apr 23 '16 at 22:45
  • \$\begingroup\$ Concerning the edit of your comment: yes it does matter. \$\endgroup\$ – flawr Apr 23 '16 at 23:06
  • \$\begingroup\$ I'm not too familiar with the rules on this site. Is it correct for to be 1 byte in TI-BASIC? \$\endgroup\$ – asmeurer Apr 25 '16 at 17:33
  • \$\begingroup\$ @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. \$\endgroup\$ – flawr Apr 25 '16 at 19:35
6
\$\begingroup\$

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.

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

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
\$\endgroup\$
  • 1
    \$\begingroup\$ SymPy has a compose() function. \$\endgroup\$ – asmeurer Apr 24 '16 at 16:30
  • 1
    \$\begingroup\$ Where's the answer? It no longer defines any functions or does anything... \$\endgroup\$ – feersum Apr 24 '16 at 19:11
  • 1
    \$\begingroup\$ @feersum That has never been the case. You just edited that meta post. \$\endgroup\$ – Mego Apr 24 '16 at 21:19
  • 3
    \$\begingroup\$ @feersum You edited an accepted meta post to modify the policy for your own agenda. That's not ok. \$\endgroup\$ – Mego Apr 24 '16 at 21:22
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – Mego Apr 24 '16 at 21:55
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is m([c],e(m,[[1]]+[g]*k)) not the same as e(m,[[c]]+[g]*k)? \$\endgroup\$ – Neil Apr 24 '16 at 20:28
  • \$\begingroup\$ @Neil Good call, can squash two in one with that! \$\endgroup\$ – orlp Apr 24 '16 at 20:48
  • \$\begingroup\$ a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l) \$\endgroup\$ – Anders Kaseorg Apr 24 '16 at 20:59
  • \$\begingroup\$ @AndersKaseorg Right, I added it, thanks :) \$\endgroup\$ – orlp Apr 24 '16 at 21:12
  • \$\begingroup\$ 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. \$\endgroup\$ – Neil Apr 25 '16 at 0:04
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Pyth, 51 34 bytes

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

Test suite.

\$\endgroup\$
  • 2
    \$\begingroup\$ when python outgolfs pyth \$\endgroup\$ – downrep_nation Apr 24 '16 at 19:14
  • \$\begingroup\$ @downrep_nation not anymore :) \$\endgroup\$ – Leaky Nun Aug 4 '17 at 5:52
1
\$\begingroup\$

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}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.