9
\$\begingroup\$

The challenge is to write the shortest function/program to find a polynomial given the roots. The function or program should take valid input; that is, a list of integers representing the roots of the polynomial, and return valid output.

Output should return a sequence of numbers representing the polynomial. For example:

2, 3 represents 2x^1 - 3x^0 = 0

1, 6, 1, 8, 0, 3, 3 represents 1x^6 + 6x^5 + 1x^4 + 8x^3 + 0x^2 + 3x^1 + 3x^0 = 0

-1 0 5, -3 represents -1x^3 + 0x^2 + 5x^1 + -3x^0 = 0

I hope you get the idea.

Example Usage

For an input of 1, 2, the output should be 1, -3, 2, which represents the equation 1x^2 + -3x^1 + 2x^0 = 0, or x^2 - 3x + 2 = 0.

For an input of 1, -1, 0, the output should be 1, 0, -1, 0.

For the input, duplicate values should be removed and order does not matter. For example, the result with input 3, 3, 6 should be the same as the result with input 6, 3.

Float arguments are optional.

As this is code golf, the shortest entry in characters wins. Good luck!

\$\endgroup\$
7
  • 2
    \$\begingroup\$ 1. "duplicate values should be removed" interesting. I would have said the roots 3,3,6 correspond to the cubic (x-3)(x-3)(x-6) and the roots 3,6 to the quadratic (x-6)(x-3) 2. What does "float arguments are optional" mean? that we can support them only if we want to? Or that they definitely may occur? 3. (in practice only applicable to float arguments) It seems the simplest way to output is to express in monic form (that is, with the term of highest x having a coefficient of 1) \$\endgroup\$ Aug 20 '15 at 0:26
  • 1
    \$\begingroup\$ @ steveverrill What I intended was to find the smallest polynomial given a set of solutions, and (x-3)(x-3)(x-6) is larger than (x-6)(x-3). I do see your argument though. \$\endgroup\$
    – The Turtle
    Aug 20 '15 at 0:37
  • 7
    \$\begingroup\$ Most code-golf contests are scored by bytes and not characters. I would advise the former. The latter encourages weird base256/unicode compression of the source, which IMO don't really add anything to the contest, and merely serve to obfuscate the code, making less accessible answers, thus decreasing the overall quality of the site. meta.codegolf.stackexchange.com/questions/2364/… \$\endgroup\$ Aug 20 '15 at 1:35
  • \$\begingroup\$ You speak of input and output, and represent them as comma separated strings... is this the format we must use, or can we use, for instance, arrays? [1,2,3] rather than "1, 2, 3"? \$\endgroup\$
    – Glen O
    Aug 20 '15 at 4:15
  • \$\begingroup\$ what is the size of the largest integer that may appear? otherwise I guess all these answers don't live up to the spec unless they are using big integers \$\endgroup\$
    – Chris Beck
    Aug 20 '15 at 5:39

11 Answers 11

10
\$\begingroup\$

J, 8 bytes

A series of verbs:

|.p.1;~.

Call it like this:

   |.p.1;~. 1 2
1 _3 2

J has a built-in verb p. (Roots). It converts between polynomials like 2 _3 1 (reverse order from the problem) and a multiplier/root pair like (1; 1 2).

From right-to-left, ~. takes the unique elements, 1; pairs the list with 1, meaning we want the smallest integer polynomial, p. does the actual work, and |. reverses the resulting list.

\$\endgroup\$
6
\$\begingroup\$

Python 2, 71

P=[1]
for r in set(input()):P=map(lambda a,b:a-r*b,P+[0],[0]+P)
print P

Iteratively updates the polynomial P to add one root at a time. Adding the root r multiplies the polynomial as P*(x-r). This requires shifting the polynomial list P by one index to represent multiplication by x, the subtracting r times the original list. This is handled by shifting a copy of the list, padding with zeroes, and mapping the function a,b -> a-r*b.

To remove duplicate roots, the input is made into a set.

Using reduce turned out one char longer (72):

lambda R:reduce(lambda P,r:map(lambda a,b:a-r*b,P+[0],[0]+P),set(R),[1])

Three lambdas though!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ {input()} saves a few chars \$\endgroup\$
    – gnibbler
    Aug 20 '15 at 6:45
  • 2
    \$\begingroup\$ @gnibbler I don't think that works; it makes a singleton set of the list or tuple of input elements. Python 3.5 would allow {*_}, but the characters saved are lost in needing to unpack the map. \$\endgroup\$
    – xnor
    Aug 20 '15 at 16:59
  • \$\begingroup\$ right I was thinking of Python3, but then you'd also need to eval input anyway. \$\endgroup\$
    – gnibbler
    Aug 20 '15 at 23:36
3
\$\begingroup\$

Haskell, 70

Basically a port of the reduce version of my Python solution.

import Data.List
foldr(\x p->zipWith(\a b->a-b*x)(p++[0])(0:p))[1].nub

I tried to shorten the lambda expression \a b->a-b*x by making it point-free, but best I have is (+).(*(-x)) on switched inputs (thanks to @isaacg), which is the same length.

The lengthy import for nub is for the requirement to ignore duplicate roots. Without it, we'd have 49:

foldr(\x p->zipWith(\a b->a-b*x)(p++[0])(0:p))[1]
\$\endgroup\$
3
\$\begingroup\$

Matlab, 56 bytes

Polynomial multiplication is convolution of their coefficients:

function y=f(R)
y=1;for r=unique(R);y=conv(y,[1 -r]);end

Floating-point roots are supported.

Example:

>> f([1 2])
ans =
     1    -3     2
>> f([1 2 1])
ans =
     1    -3     2
>> f([1 2.1 -3.2])
ans =
    1.0000    0.1000   -7.8200    6.7200
\$\endgroup\$
3
\$\begingroup\$

Ruby 2.7+, 60 58 57 50 bytes

->i{p=*1;(i&i).map{|x|p<<z=0;p.map!{-x*z+z=_1}};p}

Requires ruby 2.7+ for numbered arguments to work. Based on xnor's python answer

Takes input as an array of roots, and returns an array of coefficients.

Thanks to @Martin Ender for -2 bytes!

Thanks to Lydxn for -1 byte

Thanks to JoKing for -7 bytes.

\$\endgroup\$
2
  • \$\begingroup\$ you can use i.&i here for -1 i think \$\endgroup\$
    – Razetime
    May 18 at 10:14
  • \$\begingroup\$ @Razetime, no, that wouldnt work because technically its i.&(i.map{|x|.......) \$\endgroup\$ May 18 at 10:42
2
\$\begingroup\$

Julia, 41 bytes

Note: this is assuming the list is what matters, not the input/output format.

s->foldl((i,j)->[0,i]j+[i,0],1,unique(s))
\$\endgroup\$
2
\$\begingroup\$

Pyth, 17 bytes

u-V+G0*LH+0GS{Q]1

17 bytes. A reduce over the input set. +G0 is essentially *x, and *LH+0G is essentially *r, and -V performs element by element subtraction to perform *(x-r).

Demonstration.

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

Jelly, 3 bytes

QÆṛ

Try it online!

Outputs them in order from the zero coefficient first. +1 byte to go the other way

It would just be a builtin (Æṛ) aside from the fact that duplicates shouldn't matter. Therefore we deduplicate the input first with Q, then use the builtin

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

CJam, 24 21 bytes

1al~_&{W*1$f*0\+.+}/`

Input format is a list in square brackets (e.g. [1 2]). Output format is the same. This is a full program. It might get slightly shorter if I package it as an anonymous function.

The approach is fairly straightforward: It starts out with 1 for the polynom, which is described by a coefficient array of [1]. It then multiplies it with x - a for each root a. This results in two arrays of coefficients:

  • One from the multiplication with -a, which simply multiplies each previous coefficient by this value.
  • One from the multiplication with x, which shifts the array of coefficients by 1, padding the open position with 0.

The two are then combined with a vector addition. I actually don't have to do anything for the second array, since CJam uses remaining array elements of the longer array unchanged if the other array is shorter, so padding the second array with a 0 is redundant.

Try it online

Explanation:

1a      Put starting coefficient array [1] on stack.
l~      Get and interpret input.
_&      Uniquify input array, using setwise and with itself.
{       Loop over roots given in input.
  W*      Negate value.
  1$      Get a copy of current coefficient array to top.
  f*      Multiply all values with root.
  0\+     Add a leading zero to align it for vector addition.
  .+      Vector add for the two coefficient array.
}/      End loop over roots.
`       Convert array to string for output.
\$\endgroup\$
0
1
\$\begingroup\$

Javascript, 121 bytes

r=>{o=[...r,0].fill(0);for(i=2**r.length;i--;)e=r.length,a=r.reduce((a,q,j)=>a*(i&1<<j?q:(e--,-1)),1),o[e]+=a;return o;}

Explantation

Similar to other answers, we imagine a polynomial of the form:

 (r_1 - x) * (r_2 - x) * ... * (r_n - x)

And we want to multiply it out to get the polynomial:

 a_0 * x^n + ... + a_n * x^0

This program does that by looping over every permutation of the input brackets. We can do this by counting in binary from 0 to 2^n. The i-th bit of that count tells us whether to multiply by r_i, or by -x.

Ungolfed:

function make_poly(roots) {
  o = [...roots, 0].fill(0);
  for (i = 0; i < 2 ** roots.length; i++) {
    a = 1;
    t_index = roots.length;
    for (j = 0; j < roots.length; j++) {
      if (i & (1 << j)) {
        a *= roots[j];
      } else {
        a *= -1;
        t_index--;
      }
    }
    o[t_index] += a;
  }
  return o;
}
\$\endgroup\$
2
  • \$\begingroup\$ It's “polynomial”, not “polygon” ;) \$\endgroup\$
    – xigoi
    May 19 at 9:58
  • \$\begingroup\$ Oops, thanks! Been thinking about polygons too much recently. \$\endgroup\$
    – Hannesh
    May 19 at 22:04
0
\$\begingroup\$

Husk, 13 bytes

FȯmΣ∂Ṫ*moe1_u

Try it online!

Explanation

The idea is to generate the polynomials (x-r0),…,(x-rN) for the roots r0,…,rN and simply multiply them out:

F(mΣ∂Ṫ*)m(e1_)u  -- accepts a list of roots, example: [-1,1,-1]
              u  -- remove duplicates: [-1,1]
        m(   )   -- map the following (eg. on 1):
            _    --   negate: -1
          e1     --   create list together with 1: [1,-1]
F(     )         -- fold the following function (which does polynomial multiplication),
                 -- one step with [1,-1] and [1,1]:
     Ṫ*          --   compute outer product: [[1,1],[-1,-1]]
    ∂            --   diagonals: [[1],[1,-1],[-1]]
  mΣ             --   map sum: [1,0,1]
\$\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.