7
\$\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\$
  • 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\$ – Level River St 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\$ – Digital Trauma 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
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\$
  • 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\$

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\$
2
\$\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\$
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\$
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
\$\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.