13
\$\begingroup\$

Description

All cubic equations can be solved, and every cubic has at least one solution. The goal of this challenge is to find the real solutions to a given cubic using inputs, and (obviously) the smallest program size.

Rules

The solution must find the real solutions of a cubic correctly, using any method. The cubic must be in the standard form $$ax^3 + bx^2 + cx + d = 0$$

The first coefficient cannot be zero, as then it would be a quadratic. There must a different output if it is zero, and outputting nothing at all is acceptable.

Scoring

The score is based on the size of the program alone.

Inputs

The four coefficients of the cubic, a, b, c, and d.

The input may be formatted however you like.

Outputs

Every real solution to the cubic. There will either be three, or one for every cubic.

Example

With 3 solutions

Input:

1
3
0
-1

Output:

-2.879
-0.653
0.532

With 1 solution

Input:

1
1
1
1

Output:

-1

Additional Info

While you can use any method, you can find an image with the cubic equation (similar to the quadratic equation, can solve any cubic every time) equation can be found here.

You can learn more about cubics here.

\$\endgroup\$
18
  • 7
    \$\begingroup\$ Welcome to Code Golf! The problem with requiring answers to use a certain method is that it's "unobservable": you can't tell without looking at the code, and making a subjective judgement on what's close enough. You can get closer to requiring using rhe cubic formula by requiring outputting some intermediate values. \$\endgroup\$ Sep 28 at 14:57
  • 2
    \$\begingroup\$ Also it's implicit in your post, but you don't seem to count quadratics as cubics (implicit because quadratics can have zero real solutions). Maybe you should mention that the first coefficient can never be 0. \$\endgroup\$
    – Wheat Wizard
    Sep 28 at 15:20
  • 4
    \$\begingroup\$ If a cubic has a multiple root, should it be in the output just once or with correct multiplicit or either way? For example x(x-1)^2=x^3-2x^2+x has real roots 0, 1, 1. \$\endgroup\$
    – quarague
    Sep 29 at 7:01
  • 3
    \$\begingroup\$ The first coefficient cannot be zero, as then it would be a quadratic. There must a different output if it is zero That's a strange requirement. It would have been better to restrict the input to have non-zero leading coefficient, or to allow answers to output the real solutions also when the leading coefficient is zero. I removed my upvote (didn't downvote) because of this \$\endgroup\$
    – Luis Mendo
    Sep 29 at 19:10
  • 3
    \$\begingroup\$ @LuisMendo the requirements "first coefficient cannot be zero..." and "there must be a different output if it is zero" are contradictory. \$\endgroup\$
    – qwr
    Sep 29 at 23:26

12 Answers 12

9
\$\begingroup\$

R, 42 41 bytes

function(c,a=polyroot(c))a[!Im(a)]/!!c[4]

Try it online!

Input is vector of d,c,b,a. Outputs Inf if the cubic coefficient (a) is zero.

Using a[!Im(a)] to select only real solutions is very susceptible to floating-point rounding errors; the TIO header rounds values less than 0.0000000001 to zero to prevent this. Including rounding in the code costs 5 3 more bytes.


R, 111 bytes

function(e,z=1i^(1:3)){for(i in 1:99)z=z-e%*%rbind(z^3,z^2,z,1)/(z-(x=c(z,z))[2:4])/(z-x[3:5]);if(e)z[!Im(z)]}	

Try it online!

Non-builtin Durant-Kerner strategy copied from 97.100.97.109's answer (upvote that!). Using this approach to find all the roots in parallel works very nicely with R's vectorized operations.

\$\endgroup\$
7
\$\begingroup\$

Python, 143 134 133 bytes

f=lambda a,b,c,d,R=[-1,1j,1]:[R:=[(z:=R[2])-(((a*z+b)*z+c)*z+d)/(z-R[0])/(z-R[1])]+R for i in" "*99]and[x for x in R[:3]if x.imag==0]

Attempt This Online!

This is the first solution that doesn't use a builtin, and it suffers greatly for it. Instead, I'm using the Durant-Kerner method to find all approximations, then filtering for whether they're complex.


-9 bytes from @Steffan for various small changes.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Your editor converted the tabs to spaces again, so this is only 137 bytes \$\endgroup\$
    – Steffan
    Sep 29 at 0:08
  • \$\begingroup\$ you can save another byte by not using the walrus operator (it's often shorter): ATO \$\endgroup\$
    – Steffan
    Sep 29 at 0:09
  • \$\begingroup\$ and 0.0 can be 0., which can be just 0 \$\endgroup\$
    – Steffan
    Sep 29 at 0:09
6
\$\begingroup\$

MATL, 12 bytes

1)?G&ZQ&Zj~)

Try it online!

How it works

       % Implicit input
1)     % Get the first element
?      % If non-zero
  G    %   Push input again
  &ZQ  %   Implicit input. Roots of polynomial. Gives a numeric vector
  &Zj  %   Push real and imaginary parts
  ~    %   Negate. Gives "true" if imaginary part is zero, or "false" otherwise
  )    %   Keep only real parts corresponding to "true".
       % Implicit end
       % Implicit display
\$\endgroup\$
0
4
+100
\$\begingroup\$

Vyxal P, 4 bytes

hß∆P

Try It Online!

Good old built-ins. This may not work on some interpreters until the SymPy ACE vulnerabilities are fixed. Input as a list [a,b,c,d].

Edit: Changed output to the input if leading coefficient is 0.

\$\endgroup\$
2
  • 5
    \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ Sep 29 at 20:12
  • 1
    \$\begingroup\$ by the way, https://lyxal.pythonanywhere.com/ is the old version of Vyxal (the link you're using is too), but on the same type of interpreter that vyxal.pythonanywhere.com is on (the latest), with syntax highlighting, etc. \$\endgroup\$
    – Steffan
    Sep 30 at 0:54
4
\$\begingroup\$

Both functions below take a polynomial in x.

PARI/GP, 27 bytes

p->if(#p>3,polrootsreal(p))

Attempt This Online!

Returns 0 for quadratics and below.

PARI/GP, 101 bytes

p->k=[Pi,I,2];for(q=1,99,k-=[subst(p,x,k[i])/vecprod([k[i]-z|z<-k[^i]])|i<-[1..3]]);[r|r<-k,!imag(r)]

Attempt This Online!

Yet another implementation of the Durand–Kerner method.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think the all-builtin one (polrootsrreal) needs a bit more to prevent it from trying to solve quadratic equations when the coefficient a is zero (from the challenge: "There must a different output if it is zero") \$\endgroup\$ Sep 29 at 15:00
  • \$\begingroup\$ @DominicvanEssen OK, is this good? \$\endgroup\$ Sep 29 at 15:06
  • \$\begingroup\$ Looks good to me now. \$\endgroup\$ Sep 29 at 15:26
2
\$\begingroup\$

Jelly, 8? 11 bytes

ṛ/ȧÆr,N+AƲƇ

A monadic Link that accepts a list of the coefficients ([d,c,b,a]) and yields a list of the (one or three) real roots, unless a is zero in which case it yields an empty list.

Try it online! Or see the test-suite.

...\$8\$ bytes if we can handle a being zero (in which case it works for all polynomials):

Ær,NċAƲƇ

Try it online!

How?

The heavy lifting is done by a built-in...

ṛ/ȧÆr,N+AƲƇ - Link: coefficients, P = [d,b,c,a]
 /          - reduce (P) by:
ṛ           -   right
               -> a
   Ær       - polynomial roots (of P)
  ȧ         - logical AND
               -> [d,c,b,a] or 0
          Ƈ - keep those for which (with 0, keep those of range(0)=[]):
         Ʋ  -   last four links as a monad - f(x):
      N     -     negate (x)
     ,      -     (P) paired with (that)
        A   -     absolute value (of x)
       ċ    -     count occurrences (of that in the pair)
                    -> Truthy (1 or 2*) if x is real, falsey (0) if not
                                  * when x=0
\$\endgroup\$
3
  • 1
    \$\begingroup\$ @infinitezero: Would it make sense to ask the OP change that requirement to a guarantee that answers are allowed to assume a non-zero first coefficient? Unfortunately there are some answers that spend bytes dealing with that strange requirement, but other answers like this one which don't. (It's "strange" because it's basically separate, a different mode of operation, forbidding finding any real roots that do exist. Maybe intended to discourage builtin polynomial solvers?) \$\endgroup\$ Sep 29 at 19:10
  • 1
    \$\begingroup\$ @PeterCordes I agree. I think it'd be more in the spirit of codegolf to focus on the task and not on unnecessary restrictions. \$\endgroup\$ Sep 29 at 21:15
  • \$\begingroup\$ @infinitezero fixed it up to adhere to the rules, odd as they are :) \$\endgroup\$ Sep 30 at 0:48
2
\$\begingroup\$

Python 3, 99 bytes

import numpy
f=lambda a,b,c,d:[float(i)for i in numpy.roots([a,b,c,d])if round(float(i))!=0if a!=0]

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ Is rounding to the the nearest integer really required? It seems like an unnecessary calculation. I can see the second round is required, but the first seems unnecessary. I am no expert of python, so my analysis could be incorrect. \$\endgroup\$
    – cs1349459
    Oct 1 at 2:13
  • \$\begingroup\$ This does not seem to satisfy "There must a different output if [the cubic coefficient] is zero", and instead outputs solutions to quadratic equations if there are any real ones... \$\endgroup\$ Oct 1 at 13:54
  • \$\begingroup\$ @DominicvanEssen But my code doesn't output anything! \$\endgroup\$
    – DialFrost
    Oct 1 at 13:57
  • \$\begingroup\$ With coefficients 0,1,1,0 it seems to output -1, which is the solution to x^2+x=0. Try it \$\endgroup\$ Oct 1 at 14:47
  • \$\begingroup\$ @DominicvanEssen Fixed! Thanks my bad \$\endgroup\$
    – DialFrost
    Oct 1 at 14:53
2
\$\begingroup\$

J, 32 bytes

[:{:^:([:-.*./@(=+)){:@:>@p.^:{:

I am pretty bad at conditionals in J, but after some finagling, this was the best I could come up with. Expects coefficients as d,c,b,a

Attempt This Online!

[:{:^:([:-.*./@(=+)){:@:>@p.^:{:
                    {:@:>@p.^:{:  : u^:v executes u if v is true, else return x
                              {:  : is last item 0?
                    {:@:>@p.      : if non-zero
                          p.      : converts coefficient form to multiplier-roots form
                        >         : unbox the results
                    {:            : take the roots, not the multiplier
  {:^:([:-.*./@(=+))              : The check for only one real
      ([:-.*./@(=+))              : u(v(x)) where u is -. and v is *./@(=+)
               (=+)               : each x equal to its complex conjugate?
           *./                    : AND reduce result
         -.                       : negate result
  {:                              : if roots are not all reals, take the last value

extra:
u@v -> apply u monadically to v(x) for every application of v
u@:v -> apply u to the entire result of v(x)
[:u v -> strictly u(v(x))
\$\endgroup\$
2
\$\begingroup\$

J, 20 bytes

1(#~]=+)@{::[:p.]*{:

Attempt This Online!

Takes d c b a, and returns the array of real roots, or an empty array if a is 0.

1(#~]=+)@{::[:p.]*{:
                ]*{:    multiply the entire polynomial with `a`
                        which doesn't change the roots if `a` is nonzero
                        but gives 0 0 0 0 otherwise, which has zero roots according to `p.`
            [:p.    convert to multipler-roots form
1        {::        extract the roots
 (     )@      filter real roots:
  #~]=+        filter the list by "complex conjugate equals self"
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 50 bytes

Try it online!

g[k_]/;k[[4]]!=0:=Solve[x^Range[0,3].k==0,x,Reals]

Input is the number of coefficients in reverse order {d, c, b, a}. This defines a function g only if the 4th argument is unequal 0. Otherwise this function remains undefined and returns the function call as output. Uses the built-in Solve function over the Reals domain.

\$\endgroup\$
3
  • \$\begingroup\$ 38 bytes \$\endgroup\$
    – att
    Oct 2 at 8:00
  • \$\begingroup\$ 35 returning as many {Indeterminate}s as the non-cubic has roots \$\endgroup\$
    – att
    Oct 2 at 8:07
  • \$\begingroup\$ @att since this is so majorly different, you might as well post this as your own solution? :) \$\endgroup\$ Oct 2 at 8:27
1
\$\begingroup\$

Wolfram Language (Mathematica), 35 bytes

#^0NSolve[x#+#2&~Fold~!##,x,Reals]&

Try it online!

Input [a, b, c, d]. If \$a=0\$, returns a list of as many {Indeterminate}s as there would be solutions.

When given non-equation expressions, NSolve finds their roots.

          x#+#2&~Fold~!##           convert to a polynomial in x
   NSolve[               ,x,Reals]  get real solutions
#^0                                 invalidate solutions if a=0
\$\endgroup\$
1
\$\begingroup\$

MATLAB, 29 bytes

syms a b c d;roots([a b c d])
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Oct 4 at 17:41

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.