| Bytes | Lang | Time | Link |
|---|---|---|---|
| 036 | Julia 1.11 | 150820T042939Z | Glen O |
| 1342 | ☾ | 250321T205802Z | Used_Bra |
| 063 | Janet | 250320T092014Z | xigoi |
| 121 | Javascript | 210518T113659Z | Hannesh |
| 050 | Ruby 2.7+ | 210518T091037Z | user1007 |
| 003 | Jelly | 210517T205950Z | caird co |
| 013 | Husk | 171215T001508Z | ბიმო |
| 056 | Matlab | 150820T215734Z | Luis Men |
| 017 | Pyth | 150820T053828Z | isaacg |
| 021 | CJam | 150820T040604Z | Reto Kor |
| 008 | J | 150820T030336Z | lynn |
| 070 | Haskell | 150820T012502Z | xnor |
| 071 | Python 2 | 150819T235818Z | xnor |
Julia 1.11, 39 36 bytes
It's been fun revisiting this after almost 10 years, ended up being able to compress it even with some Julia changes that made it harder.
s->(i=1;s∪s.|>k->i=[0;i]k-[i;0];i)
Note that s∪s, as suspicious as it may seem, is the most length-efficient way to get unique(s), as ∪ is a binary infix operator that performs union, which inherently performs unique as part of its operation.
Saved 3 bytes thanks to MarcMush
Julia (~0.4), 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))
☾, 13 chars (42 bytes)
ᚤᑀ🃌ᴍ⟞⫚⬤ᐵᴍ⨀⨁
Note: ☾ uses a custom font, but you can run this code in the Web UI
The input is a list of zeros; the output is a list of coefficients starting with the highest term.
For n roots, the xᵏ coefficient is the sum of all possible products of n-k of the roots.
Janet, 63 bytes
|(reduce(fn[p x](map|(- $(* $1 x))[;p 0][0;p]))[1](distinct $))
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;
}
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.
Jelly, 3 bytes
QÆṛ
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
Husk, 13 bytes
FȯmΣ∂Ṫ*moe1_u
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]
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
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).
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.
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.
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.
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]
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!
