8
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ What about built-ins like numpy.poly? \$\endgroup\$ – Dennis Mar 27 '16 at 5:41
  • \$\begingroup\$ @Dennis numpy is not built-in i think! \$\endgroup\$ – aliqandil Mar 27 '16 at 6:40
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Mar 27 '16 at 6:42
  • \$\begingroup\$ @Dennis That pretty much the whole think! But go ahead! Since the same function is built-in in most languages. \$\endgroup\$ – aliqandil Mar 27 '16 at 9:28
  • \$\begingroup\$ can we assume the roots are integers? can we assume they are nonnegative integers? \$\endgroup\$ – proud haskeller Mar 27 '16 at 21:10
3
\$\begingroup\$

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 [[1]].
   ;                      Concatenate with A.
    ð    µ/               Reduce [[1]] + A by the following, dyadic chain:
     0;                     Prepend a zero to the left argument (initially [1]).
                            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.
\$\endgroup\$
4
\$\begingroup\$

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

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=[0]+b
b.map{|e|e*c}[1..-1]}
q.pop.zip(*q).map{|e|(e-[p]).reduce(:+)}}.map{|e|"#{e}x^#{j+=1}"}.join('+')}
\$\endgroup\$
1
\$\begingroup\$

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()]][0])

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

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

Haskell, 99

l%r=zipWith(-)(0:l)$map(r*)l++[0]
f e='0':do(c,i)<-zip(foldl(%)[1]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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

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`+`
\$\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.