19
\$\begingroup\$

Challenge

The challenge is to write a program that takes the coefficients of any n-degree polynomial equation as input and returns the integral values of x for which the equation holds true. The coefficients will be provided as input in the order of decreasing or increasing power. You can assume all the coefficients to be integers.

Input And Output

The input will be the coefficients of the equation in decreasing or increasing order of power. The degree of the equation, i.e, maximum power of x, is always 1 less than the total no of elements in the input.

For example:

[1,2,3,4,5] -> represents x^4 + 2x^3 + 3x^2 + 4x + 5 = 0 (degree = 4, as there are 5 elements)
[4,0,0,3] -> represents 4x^3 + 3 = 0 (degree = 3, as there are 3+1 = 4 elements)

Your output should be only the distinct integral values of x which satisfy the given equation. All the input coefficients are integers and the input polynomial will not be a zero polynomial. If there is no solution for the given equation, then the output is undefined.

If an equation has repeated roots, display that particular root only once. You can output the values in any order. Also, assume that the input will contain at-least 2 numbers.

Examples

[1,5,6] -> (-3,-2)
[10,-42,8] -> (4)
[1,-2,0] -> (0,2)
[1, 1, -39, -121, -10, 168] -> (-4, -3, -2, 1, 7)
[1, 0, -13, 0, 36] -> (-3, -2, 2, 3)
[1,-5] -> (5)
[1,2,3] -> -

Note that the equation in the second example also has the root 0.2, but it is not displayed as 0.2 is not an integer.

Scoring

This is , so the shortest code (in bytes) wins!

\$\endgroup\$
  • 7
    \$\begingroup\$ Note: Before voting to close, please consider that this question is not a duplicate of this one. I can think of at least one approach to this problem which will not be trivially modifiable for the other challenge (although I'm not saying what; that's left to you ;P). \$\endgroup\$ – Erik the Outgolfer Jan 24 '18 at 14:51
  • \$\begingroup\$ Can we assume we only need to return roots inside the integer bounds of our language? Or should the algorithm work even if the languages integer type range was increased, but the behaviour stayed the same. \$\endgroup\$ – Οurous Jan 24 '18 at 20:22
  • 1
    \$\begingroup\$ Can we also use a native polynomial type if your language supports those? \$\endgroup\$ – flawr Jan 24 '18 at 21:56
  • 1
    \$\begingroup\$ Are programs that run forever if there are no solutions accepted? \$\endgroup\$ – Jack M Jan 25 '18 at 8:29
  • 1
    \$\begingroup\$ That's to keep things simple. \$\endgroup\$ – Manish Kundu Jan 27 '18 at 16:46

17 Answers 17

6
\$\begingroup\$

MATL, 13 12 bytes

|stE:-GyZQ~)

Try it online!

This uses the fact that, for integer coefficients, the absolute value of any root is strictly less than the sum of absolute values of the coefficients.

Explanation

Consider input [1 5 6] as an example.

|    % Implicit input. Absolute value
     % STACK: [1 5 6]
s    % Sum
     % STACK: 12
t    % Duplicate
     % STACK: 12, 12
E    % Multiply by 2
     % STACK: 12, 24
:    % Range
     % STACK: 12, [1 2 ... 23 24]
-    % Subtract, elemet-wise
     % STACK: [11 10 ... -11 -12]
G    % Push input again
     % STACK: [11 10 ... -11 -12], [1 5 6]
y    % Duplicate from below
     % STACK: [11 10 ... -11 -12], [1 5 6], [11 10 ... -11 -12]
ZQ   % Polyval: values of polynomial at specified inputs
     % STACK: [11 10 ... -11 -12], [182 156 ... 72 90]
~    % Logical negation: turns nonzero into zero
     % STACK: [11 10 ... -11 -12], [0 0 ... 0] (contains 1 for roots)
)    % Index: uses second input as a mask for the first. Implicit display
     % STACK: [-3 -2]
\$\endgroup\$
  • 3
    \$\begingroup\$ As an alternative to Rouche's Theorem, the Rational Roots Theorem would also suffice to justify the bound you used. By the Rational Roots Theorem, all integer roots are bounded in absolute value by the maximum of the absolute values of the coefficients, a tighter bound than the sum. Or even tighter, by the absolute value of the "last" nonzero coefficient--i.e. the coefficient of the smallest power of x which has a nonzero coefficient. (Probably doesn't help save any bytes, just an alternative proof since the RRT is probably more familiar than Rouche to most folks.) :) \$\endgroup\$ – mathmandan Jan 24 '18 at 21:14
  • 1
    \$\begingroup\$ @mathmandan that approach is three bytes longer: Try it here, although I'm sure I've missed a trick or two \$\endgroup\$ – Giuseppe Jan 24 '18 at 22:37
  • \$\begingroup\$ @Giuseppe Thanks to both. Maybe X>t_w&:GyZQ~), but still 13 bytes \$\endgroup\$ – Luis Mendo Jan 24 '18 at 22:44
  • 1
    \$\begingroup\$ ... but I found a shorter alternative for the range \$\endgroup\$ – Luis Mendo Jan 24 '18 at 22:59
5
\$\begingroup\$

Husk, 10 9 bytes

-1 byte thanks to Zgarb

uSȯf¬`Bṁṡ

Try it online!

Explanation

       ṁṡ   Concatenate together the symmetric ranges of each coefficient
            (It is guaranteed that the integer roots lie in the range [-n..n],
                        where n is the coefficient with the largest magnitude)
 Sȯf        Find all the values in that range which
    ¬       are zero
     `B     when plugged through the polynomial
            (Base conversion acts as polynomial evaluation)
u           De-duplicate the roots
\$\endgroup\$
  • \$\begingroup\$ You could do ṁṡ instead of oṡ►a if you deduplicate later. \$\endgroup\$ – Zgarb Jan 24 '18 at 18:45
  • \$\begingroup\$ @Zgarb Very nice! Thanks \$\endgroup\$ – H.PWiz Jan 24 '18 at 18:54
5
\$\begingroup\$

Haskell, 54 bytes

f l|t<-sum$abs<$>l=[i|i<-[-t..t],foldl1((+).(i*))l==0]

Try it online!

Brute force and synthetic division.

Ungolfed with UniHaskell and -XUnicodeSyntax

import UniHaskell

roots    ∷ Num a ⇒ [a] → [a]
roots xs = [r | r ← -bound … bound, foldl1 ((+) ∘ (r ×)) xs ≡ 0]
             where bound = sum $ abs § xs

Alternate solution, 44 bytes

Credit to nimi.

f l=[i|i<-[minBound..],foldl1((+).(i*))l==0]

Good luck with trying it online, as this checks every number in an Int's range.

\$\endgroup\$
  • \$\begingroup\$ You can iterate i over [minBound..] and drop the whole t thing. Call f with explicit Int lists, e.g. f [1::Int,5,6]. Of course this doesn't finish in reasonable time. \$\endgroup\$ – nimi Jan 24 '18 at 16:08
  • \$\begingroup\$ @nimi Why would that ever stop? Wouldn't it infinitely loop? \$\endgroup\$ – totallyhuman Jan 24 '18 at 16:14
  • \$\begingroup\$ No, Bounded types stop at maxBound, e.g. print [minBound::Bool ..]. \$\endgroup\$ – nimi Jan 24 '18 at 16:16
4
\$\begingroup\$

Python 2 + numpy, 95 93 91 103 93 91 82 bytes

-2 bytes thanks to ovs
thanks Luis Mendo for the upper/lower bounds of the roots
-10 bytes thanks to Mr. Xcoder

from numpy import*
def f(r):s=sum(fabs(r));q=arange(-s,s);print q[polyval(r,q)==0]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 91 bytes \$\endgroup\$ – ovs Jan 24 '18 at 15:27
  • \$\begingroup\$ @LuisMendo yes. \$\endgroup\$ – Rod Jan 24 '18 at 16:01
  • 3
    \$\begingroup\$ Our current consensus seems to be that programs must always terminate, unless the challenge states otherwise. \$\endgroup\$ – Zgarb Jan 24 '18 at 17:11
  • \$\begingroup\$ @Zgarb there, fixed! \$\endgroup\$ – Rod Jan 24 '18 at 17:25
  • \$\begingroup\$ Using numpy.polyval saves quite a few bytes \$\endgroup\$ – Mr. Xcoder Jan 24 '18 at 18:31
4
\$\begingroup\$

Wolfram Language (Mathematica), 50 47 42 25 27 bytes

{}⋃Select[x/.Solve[#~FromDigits~x==0],IntegerQ]&

Try it online!

Update: using Luis Mendo's fact, golfed off another 3 bytes

Pick[r=Range[s=-Tr@Abs@#,-s],#~FromDigits~r,0]&

Getting sloppier with the bounds, we can reduce this 5 more bytes per @Not a tree's suggestion:

Pick[r=Range[s=-#.#,-s],#~FromDigits~r,0]&

After posting this, OP commented allowing "native polynomials", so here's a 25 byte solution that accepts the polynomial as input. This works because by default Mathematica factors polynomials over the integers, and any rational roots show up in a form like m*x+b that fails the pattern match.

Cases[Factor@#,b_+x:>-b]&

As @alephalpha pointed out this will fail for the case where zero is a root, so to fix that we can use the Optional symbol :

Cases[Factor@#,b_:0+x:>-b]&

This parses fine Mathematica 11.0.1 but fails and requires an extra set of parentheses around b_:0 in version 11.2. This takes up back up to 27 bytes, plus two more after version 11.0.1. It looks like a "fix" was put in here

Try it Online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can use #.# instead of Tr@Abs@#: it's a worse bound but fewer bytes. \$\endgroup\$ – Not a tree Jan 25 '18 at 0:32
  • 1
    \$\begingroup\$ OP said in a comment that you could use your language's native polynomial type if one exists. I don't know Mathematica well but I imagine there is one... Would that save bytes? \$\endgroup\$ – No don't shown my real name Jan 25 '18 at 2:48
  • 1
    \$\begingroup\$ It fails when 0 is a root. \$\endgroup\$ – alephalpha Jan 27 '18 at 4:15
  • 1
    \$\begingroup\$ @alephalpha, fixed. \$\endgroup\$ – Kelly Lowder Jan 29 '18 at 15:48
  • \$\begingroup\$ 24 bytes with a Default pattern and an operator right-composition \$\endgroup\$ – Roman Aug 6 at 22:29
3
\$\begingroup\$

Wolfram Language (Mathematica), 33 26 31 bytes

Fixed an error noted by Kelly Lowder in the comments.

x/.{}⋃Solve[#==0,x,Integers]&

Try it online!

Previous incorrect solutions:

I just noticed that for no integer solution, the output is undefined instead of empty list; that allows to remove a few bytes.

x/.Solve[#==0,x,Integers]&

Try it online!

Now if no integer solution exists, the function returns x.

Previously:

x/.Solve[#==0,x,Integers]/.x->{}&

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This fails as currently stated with 1,2,1 as it repeats the root and the OP said they had to be distinct. You need Union to fix that. \$\endgroup\$ – Kelly Lowder Jan 25 '18 at 21:09
  • \$\begingroup\$ @KellyLowder: Ah, I missed that. But then, it was also missing in the given test cases. \$\endgroup\$ – celtschk Jan 25 '18 at 22:11
  • \$\begingroup\$ @KellyLowder: I've now fixed it. In case you downvoted because of this, can you please revert it? \$\endgroup\$ – celtschk Jan 25 '18 at 22:20
  • \$\begingroup\$ @cellschk, yep done. \$\endgroup\$ – Kelly Lowder Jan 25 '18 at 22:21
  • \$\begingroup\$ 29 bytes by using an undocumented feature of Solve: the list of variables can be omitted. \$\endgroup\$ – Roman Aug 6 at 22:25
3
\$\begingroup\$

R, 61 59 bytes

A special thanks to @mathmandan for pointing out my (incorrect) approach could be saved, and golfed!

function(p)(x=-(t=p[!!p][1]):t)[!outer(x,seq(p)-1,"^")%*%p]

Try it online!

Takes input as a list of coefficients in increasing order, i.e., c(-1,0,1) represents -1+0x+1x^2.

Using the rational root theorem, the following approach very nearly works, for 47 bytes:

function(p)(x=-p:p)[!outer(x,seq(p)-1,"^")%*%p]

Try it online!

-p:p generates a symmetric range (with a warning) using only the first element of p, a_0. By the Rational Root Theorem, all rational roots of P must be of the form p/q where p divides a_0 and q divides a_n (plus or minus). Hence, using just a_0 is sufficient for |a_0|>0, as for any q, |p/q|<=a_0. However, when a_0==0, as then any integer divides 0, and thus this fails.

However, mathmandan points out that really, in this case, this means that there's a constant factor of x^k that can be factored out, and, assuming k is maximal, we see that

P(x) = x^k(a_k + a_{k+1}x + ... a_n x^{n-k}) = x^k * Q(x)

We then apply the Rational Root Theorem to Q(x), and as a_k is guaranteed to be nonzero by the maximality of k, a_k provides a tidy bound for the integer roots of Q, and the roots of P are the roots of Q along with zero, so we will have all the integer roots of P by applying this method.

This is equivalent to finding the first nonzero coefficient of the polynomial, t=p[!!p][1] and using it instead of the naive p[1] as the bounds. Moreover, since the range -t:t always contains zero, applying P to this range would still give us zero as a root, if indeed it is.

ungolfed:

function(polynom) {
 bound <- polynom[polynom != 0][1]             #first nonzero value of polynom
 range <- -bound:bound                         #generates [-bound, ..., bound]
 powers <- outer(range,seq_along(p) - 1, "^")  #matrix where each row is [n^0,n^1,n^2,...,n^deg(p)]
 polyVals <- powers %*% polynom                #value of the polynomial @ each point in range
 return(range[polyVals == 0])                  #filter for zeros and return
}

\$\endgroup\$
  • \$\begingroup\$ (I think you could use the max of the absolute values instead of the sum; this wouldn't change the byte count, but it ought to improve performance.) Anyway, yes, pity the shorter version doesn't work with a_0==0. Is there some short way in R to search for the first (with powers ascending) nonzero coefficient, and use that instead? This would correspond to factoring out as many x's as possible first (of course, then you'd have to remember to output 0 also, which would presumably cost some bytes.) \$\endgroup\$ – mathmandan Jan 24 '18 at 21:14
  • \$\begingroup\$ @mathmandan max would be more efficient, but to your second point, as I don't have to worry about outputting 0 since it's generated by the range -t:t (where t is the first nonzero coefficient), it saves 2 bytes! \$\endgroup\$ – Giuseppe Jan 24 '18 at 21:39
  • \$\begingroup\$ Oh, very nice! (And a beautiful explanation as well.) \$\endgroup\$ – mathmandan Jan 24 '18 at 22:01
2
\$\begingroup\$

Jelly, 8 bytes

ASŒRḅ@Ðḟ

Try it online! or as a test-suite!

How?

ASŒRḅ@Ðḟ || Full program (monadic link).

AS        || Sum the absolute values.
  ŒR      || And create the symmetric inclusive range from its negative value.
       Ðḟ || And discard those that yield a truthy value...
     ḅ@   || When plugging them into the polynomial (uses base convertion).

Based off Luis' answer. An alternative.

\$\endgroup\$
  • \$\begingroup\$ Is there something I'm missing about taking the (allowed) reverse order and doing Ær+.Ḟ? \$\endgroup\$ – Jonathan Allan Jan 24 '18 at 19:31
  • \$\begingroup\$ I'm slightly confused since the Python answer with numpy isn't doing so either, and am thinking I've missed some edge case. \$\endgroup\$ – Jonathan Allan Jan 24 '18 at 19:34
  • \$\begingroup\$ @JonathanAllan As I expected, yours fails for [1,2,3]. \$\endgroup\$ – Mr. Xcoder Jan 24 '18 at 19:37
  • \$\begingroup\$ "If there is no solution for the given equation, then the output is undefined" \$\endgroup\$ – Jonathan Allan Jan 24 '18 at 19:40
  • \$\begingroup\$ @JonathanAllan But it does fail for [10,-42,8], right? \$\endgroup\$ – Mr. Xcoder Jan 24 '18 at 19:43
2
\$\begingroup\$

Octave, 59 49 bytes

@(p)(x=-(t=p(~~p)(end)):sign(t):t)(!polyval(p,x))

Try it online!

This is a port of my R answer. The only difference is that I have to explicitly use sign(t) and end to generate the range, and that it has polyval to compute the polynomial.

Takes input as a row vector of coefficients in decreasing order.

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

Pari/GP, 31 bytes

p->[x-a|a<-factor(p)[,1],a'==1]

Factors the polynomial, and picks out the factors whose derivatives are 1.

Try it online!

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

C (gcc), 127 126 123 bytes

x,X,j,m,p;f(A,l)int*A;{for(m=j=0;j<l;m+=abs(A[j++]));for(x=~m;X=x++<m;p||printf("%d,",x))for(p=j=0;j<l;X*=x)p+=A[l-++j]*X;}

Try it online!


Explanation

C (gcc), 517 bytes

x,X,j,m,p;                      // global integer variables
f(A,l)int*A;{                   // define function, takes in integer array pointer and length
 for(m=j=0;j<l;m+=abs(A[j++])); // loop through array, sum up absolute values
  for(x=~m;X=x++<m;             // loop through all values x in [-m, m], prime X
   p||printf("%d,",x))          // at loop's end, print x value if polynomial value is zero
    for(p=j=0;j<l;X*=x)         // loop through coefficients
     p+=A[l-++j]*X;}            // build polynomial

Try it online!

\$\endgroup\$
  • \$\begingroup\$ l+~j++ can be golfed to l-++j \$\endgroup\$ – Kevin Cruijssen Jan 31 '18 at 19:58
  • \$\begingroup\$ @KevinCruijssen Thanks a lot. \$\endgroup\$ – Jonathan Frech Jan 31 '18 at 22:11
  • \$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$ – Jonathan Frech Aug 6 at 20:01
1
\$\begingroup\$

Java 8, 141 140 bytes

a->{int l=a.length,s=0,i,r,f,p;for(int n:a)s+=n<0?-n:n;for(r=~s;r++<s;System.out.print(p==0?r+",":""))for(p=i=0,f=1;i<l;f*=r)p+=a[l-++i]*f;}

Inspired by @Rod's Python 2 answer (his 82 bytes version).

Fun challenge! I certainly learned a lot of it when investigating about polynomials and seeing how some others here have done it.

Explanation:

Try it online.

a->{                   // Method with integer-array parameter and no return-type
  int l=a.length,      //  The length of the input-array
      s=0,             //  Sum-integer, starting at 0
      i,               //  Index integer
      r,               //  Range-integer
      f,               //  Factor-integer
      p;               //  Polynomial-integer
  for(int n:a)         //  Loop over the input-array
    s+=n<0?-n:n;       //   And sum their absolute values
  for(r=~s;r++<s;      //  Loop `r` from `-s` up to `s` (inclusive) (where `s` is the sum)
      System.out.print(p==0?r+",":""))
                       //    After every iteration: print the current `r` if `p` is 0
    for(p=i=0,         //   Reset `p` to 0
        f=1;           //   and `f` to 1
        i<l;           //   Loop over the input-array again, this time with index (`i`)
        f*=r)          //     After every iteration: multiply `f` with the current `r`
      p+=              //    Sum the Polynomial-integer `p` with:
         a[l-++i]      //     The value of the input at index `l-i-1`,
                 *f;}  //     multiplied with the current factor `f`
\$\endgroup\$
0
\$\begingroup\$

Octave with Symbolic Package, 63 bytes

@(p)(s=double(solve(poly2sym(p)==0)))(s==(t=real(s))&~mod(t,1))

Try it online!

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

05AB1E, 8 bytes

ÄOD(Ÿʒβ>

Try it online!

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

JavaScript (ES6), 97 bytes

a=>[...Array((n=Math.max(...a.map(Math.abs)))-~n)].map(_=>n--).filter(i=>!a.reduce((x,y)=>x*i+y))

Takes coefficients in decreasing order of power and outputs results in descending order.

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

Clean, 110 91 bytes

import StdEnv
?p#s=sum p
=[i\\i<-[~s..s]|i<>0&&sum[e*i^t\\t<-reverse(indexList p)&e<-p]==0]

Try it online!

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

Python 2, 89 bytes

def f(a):s=sum(map(abs,a));return[n for n in range(-s,s)if reduce(lambda v,c:v*n+c,a)==0]

Try it online!

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