# Expand roots into a polynomial

## Challenge

Given the roots of a polynomial separated by spaces as input, output the expanded form of the polynomial.

For example, the input

1 2


represents this equation:

(x-1)(x-2)


And should output:

x^2-3x+2


The exact format of output is not important, it can be:

1x^2+-3x^1+2x^0


or:

0 0 0
1x^3+0x^2+0x^1+0


or:

3 14 15 92
1x^4+-124x^3+3241x^2+-27954x^1+57960


## Scoring/Rules

• eval and likes are disallowed.
• You may use any version of Python or any other language.
• What about built-ins like numpy.poly? – Dennis Mar 27 '16 at 5:41
• @Dennis numpy is not built-in i think! – aliqandil Mar 27 '16 at 6:40
• Python + NumPy answers are generally accepted, but that's beside the point. Can I use a function that turns roots into polynomial coefficients? I'm asking since you banned eval, and that's considerably more powerful than eval. – Dennis Mar 27 '16 at 6:42
• @Dennis That pretty much the whole think! But go ahead! Since the same function is built-in in most languages. – aliqandil Mar 27 '16 at 9:28
• can we assume the roots are integers? can we assume they are nonnegative integers? – proud haskeller Mar 27 '16 at 21:10

# Jelly, 15 bytes

Æṛ‘Ė’Uj€“x^”j”+


This uses Æṛ to construct the coefficients of a monic polynomial with given roots. Try it online!

### How it works

Æṛ‘Ė’Uj€“x^”j”+  Main link. Argument: A (list of roots)

Æṛ               Yield the coefficients of a monic polynomial with roots A.
‘              Increment each root by 1.
Ė             Enumerate the roots, yielding
[[1, coeff. of x^0 + 1], ... [n + 1, coeff. of x^n + 1]].
’            Decrement all involved integers, yielding
[[0, coeff. of x^0], ... [n, coeff. of x^n]].
U           Upend to yield [[coeff. of x^0, 0], ... [coeff. of x^n, n]].
j€“x^”     Join each pair, separating by 'x^'.
j”+  Join the pairs, separating by '+'.


## Alternate version, 24 bytes

1WW;ð0;_×µ/‘Ė’Uj€“x^”j”+


This uses no polynomial-related built-ins. Try it online!

### How it works

1WW;ð0;_×µ/‘Ė’Uj€“x^”j”+  Main link. Argument: A (list of roots)

1WW                       Yield [].
;                      Concatenate with A.
ð    µ/               Reduce [] + A by the following, dyadic chain:
0;                     Prepend a zero to the left argument (initially ).
This multiplies the left argument by "x".
×                   Take the product of both, unaltered arguments.
This multiplies the left argument by "r", where r is
the root specified in the right argument.
_                     Subtract.
This computes the left argument multiplied by "x-r".
‘Ė’Uj€“x^”j”+  As before.


# MATL, 29 bytes

ljU"1@_hX+]tn:Pqv'+%gx^%g'wYD


Input is an array with the roots.

EDITS:

• (May 20, 2016): the X+ function has been removed, as Y+ includes its functionality. So in the above code replace X+ by Y+.
• (September 29, 2017): due to changes in the YD function, w in the above code should be removed.

The following link includes those changes.

Try it online!

### Explanation

This applies repeated convolution with terms of the form [1, -r] where r is a root.

l          % push number 1
jU         % take input string. Convert to number array
"          % for each root r
1        %   push number 1
@_       %   push -r
h        %   concatenate horizontally
X+       %   convolve. This gradually builds array of coefficients
]          % end for each
tn:Pq      % produce array [n-1,n-2,...,0], where n is the number of roots
v          % concatenate vertically with array of coefficients
'+%gx^%g'  % format string, sprintf-style
w          % swap
YD         % sprintf. Implicitly display


# Ruby, 155 bytes

Anonymous function, input is an array of the roots.

Prints from lowest power first, so calling f[[1,2]] (assuming you assigned the function to f) returns the string "2x^0+-3x^1+1x^2".

->x{j=-1
x.map{|r|[-r,1]}.reduce{|a,b|q=a.map{|c|b=+b
b.map{|e|e*c}[1..-1]}
q.pop.zip(*q).map{|e|(e-[p]).reduce(:+)}}.map{|e|"#{e}x^#{j+=1}"}.join('+')}


## Python 3, 453 bytes (Spaces removed and more) -> 392 bytes

import functools
import operator
print([('+'.join(["x^"+str(len(R))]+[str(q)+"x^"+str(r)if r>0else"{0:g}".format(q)for r,q in enumerate([sum(functools.reduce(operator.mul,(-int(R[n])for n,m in enumerate(j)if int(m)==1),1)for j in[(len(R)-len(bin(i)[2:]))*'0'+bin(i)[2:]for i in range(1,2**len(R))]if sum(1-int(k) for k in j)==p)for p in range(len(R))]) ][::-1]))for R in[input().split()]])


Check This link, Will help understand the reason behind those two imports.

• You could get rid of a lot of extra whitespace – proud haskeller Mar 25 '16 at 9:46
• @proudhaskeller You're right! I changed the rules kinda forgot to change my own answer. – aliqandil Mar 25 '16 at 10:10
• from operator import*, from functools import* save a few bytes – shooqie Mar 25 '16 at 11:01
• import functools,operator – CalculatorFeline Mar 26 '16 at 22:11

l%r=zipWith(-)(0:l)\$map(r*)l++
f e='0':do(c,i)<-zip(foldl(%)e)[0..];'+':show c++"x^"++show i


prints the lower powers first, with an additional 0+ at the start. for example:

>f [1,1]
"0+1x^0+-2x^1+1x^2"


The function computes the coefficients by progressively adding more roots, like convolutions, but without the builtin.

Then we use the list monad to implicitly concat all of the different monomials.

## Sage, 38 bytes

lambda N:prod(x-t for t in N).expand()


Try it online

This defines an unnamed lambda that takes an iterable of roots as input and computes the product (x-x_n) for x_n in roots, then expands it.

# Mathematica, 26 bytes

Expand@Product[x-k,{k,#}]&


Mathematica has powerful polynomial builtins.

## Usage

  f = Expand@Product[x-k,{k,#}]&
f@{3, 14, 15, 92}
x^4 - 124 x^3 + 3241 x^2 - 27954 x + 57960


## JavaScript (ES6), 96 bytes

a=>a.map(x=>r.map((n,i)=>(r[i]-=x*a,a=n),++j,r.push(a=0)),r=[j=1])&&r.map(n=>n+x^+--j).join+