38
\$\begingroup\$

Introduction

Humans are a remarkable species, but we can be very awkward to understand sometimes—especially for computers. In particular, we seem to like writing polynomials in a very convoluted fashion with seemingly arbitrary rules.

What is the shortest program you can write to format a polynomial correctly using these rules?

Challenge

Input

A list of integers between -1000 and 1000 (inclusive), representing the coefficients of a polynomial, with the last entry being the coefficient of x^0 (the constant), the second last being the coefficient of x^1, etc.

Output

A string representing this polynomial in the correctly formatted mathematical notation of humans.

Rules:

  • The sign on the leading coefficient is only shown if it is negative.

Right: -x^2+3

Wrong: +x^2+3

  • Components with coefficient of 0 are not printed (except for the corner case where all coefficients are 0*).

Right: x^5-x^2+3

Wrong: x^5+0x^4+0x^3-x^2+0x+3

  • Coefficients -1 and +1 are to be displayed without the 1, unless they are the constant.

Right: x^5-x^2+1

Wrong: 1x^5-1x^2+1

  • The exponent is only shown if it is greater than 1 and the variable is only shown if the exponent is greater than 0.

Right: 3x^3-7x^2+2x+1

Wrong: 3x^3-7x^2+2x^1+1x^0

  • *Corner case: while zero values usually result in not printing that component, if all coefficients are zero the constant 0 should be printed.

Right: 0

Wrong: 0x+0

Wrong: (nothing)

  • This is code-golf so the winner will be the program with the fewest bytes.

Example Input and Output

Input:                  Output:
      [0]                      0
      [0,0]                    0
      [0,-1,35,0]             -x^2+35x
      [5,1,7,-9]               5x^3+x^2+7x-9
      [100,0,0,-1]             100x^3-1
      [931,21,-11,1]           931x^3+21x^2-11x+1

I look forward to seeing your solutions. Have fun!

EDIT:

  • You can surround operations by whitespace if you wish. So 3x+5 and 3x + 5 are both fine. 3x+ 5 and 3x +5 are not.
  • If you want to produce actual exponent characters (say in Tex) that is allowed as it is even closer to how humans write.
  • Coefficients must appear without any decimals e.g. 9x^2 is correct, 9.0x^2 is not.
\$\endgroup\$
  • 7
    \$\begingroup\$ A question which I should have asked in the sandbox but didn't, can we print with whitespace between the operators? So 3x^2 + 4 versus 3x^2+4? \$\endgroup\$ – Giuseppe Mar 15 '18 at 14:08
  • 1
    \$\begingroup\$ Do we need to output exponents using carets? Or would producing an actual superscript character be allowed (e.g. for an answer in TeX)? \$\endgroup\$ – Tutleman Mar 15 '18 at 15:12
  • 3
    \$\begingroup\$ @KevinCruijssen I'm not the OP but I would say not, because most humans don't write like that. \$\endgroup\$ – ShreevatsaR Mar 15 '18 at 16:39
  • 2
    \$\begingroup\$ @ManishKundu Yeah sure you can take the input as strings. \$\endgroup\$ – Oisín Moran Mar 15 '18 at 16:56
  • 1
    \$\begingroup\$ @OisínMoran Nothing funky, just making sure a simple 1x -> x replacement doesn't change 21x^2 into 2x^2. \$\endgroup\$ – DLosc Mar 16 '18 at 5:22

23 Answers 23

10
\$\begingroup\$

Retina 0.8.2, 56 bytes

(?=( \S+)+)
x^$#1
\b0x.\d+ 

\b1x
x
x.1 
x 
 0

 -
-
 
+

Try it online! Link includes test cases. Explanation:

(?=( \S+)+)
x^$#1

Insert all of the powers of x, including x^1 but not x^0.

\b0x.\d+ 

Delete all powers of x with zero coefficients, but not a trailing 0 (yet).

\b1x
x

Delete a multiplier of 1 (but not a constant 1).

x.1 
x 

Delete the ^1 of x^1.

 0

Delete a constant 0 unless it is the only thing left.

 -
-

Delete the space before a -.

 
+

Change any remaining spaces to +s.

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

JavaScript (ES6), 107 106 bytes

a=>a.map(c=>c?s+=(c>0&&s?'+':_)+(!--e|c*c-1?c:c<0?'-':_)+(e?e-1?'x^'+e:'x':_):e--,e=a.length,_=s='')&&s||0

Try it online!

How?

The output is built by applying the following formulas to each coefficient c of the input array a[ ] while keeping track of the current exponent e.

1st formula: plus sign

If the coefficient is strictly positive and this is not the first term in the output expression, we append a +. Otherwise, we append nothing.

c > 0 && s ? '+' : _

2nd formula: minus sign and coefficient

If the exponent is zero or the absolute value of the coefficient is not equal to 1, we append the coefficient (which may include a leading -). Otherwise, we append either a - (if the coefficient is negative) or nothing.

!--e | c * c - 1 ? c : c < 0 ? '-' : _

3rd formula: variable and exponent

If the exponent is 0, we append nothing. If the exponent is 1, we append x. Otherwise, we append x^ followed by the exponent.

e ? e - 1 ? 'x^' + e : 'x' : _
\$\endgroup\$
  • \$\begingroup\$ This fails in this case: [0,1,35,0] , it will lead with +x^2 \$\endgroup\$ – Makotosan Mar 15 '18 at 18:09
  • 2
    \$\begingroup\$ @Makotosan Thanks for reporting this! Should be OK now. \$\endgroup\$ – Arnauld Mar 15 '18 at 18:21
5
\$\begingroup\$

Stax, 37 bytes

┴₧↕ê♦•Vªâÿσ9s╘dσ■à@@ⁿ■o─╦ñºº┌x╡ER▓ δ¿

Run and debug it online

Here's the unpacked, ungolfed version.

r{          reverse the input and map using block ...
  |c        skip this coefficient if it's falsy (zero)
  0<.+-@    sign char; e.g. '+'
  _|aYv i!+ abs(coeff)!=1 || i>0
    y$      str(abs(coeff)); e.g. '7'
    z       ""
  ?+        if-then-else, concatenate; e.g. '+7'
  "x^`i"    string template e.g. 'x^3' or 'x^0'
  iJ(T+     truncate string at i*i and trim. e.g. 'x^3' or ''
mr$         re-reverse mapped array, and flatten to string
c43=t       if it starts with '+', drop the first character
c0?         if the result is blank, use 0 instead

Run this one

\$\endgroup\$
5
\$\begingroup\$

Python 3, 279 277 258 251 bytes

k=str.replace
def f(x):
 z=len(x)
 y='--'*(['-1']==[c for c in x if'0'!=c][:1])
 for i,v in enumerate(x):
  p=str(z+~i)
  if v in'-1'and~i+z:y+='+x^'+p
  elif'0'!=v:y+='+'+v+'x^'+p
 return y and k(k(k(k(y[1:],'+-','-'),'^1',''),'x^0',''),'-+','-')or 0

Takes input as a list of strings. This solution is not highly golfed yet. This basically works by replacing things to suit the output format, which highly increases the byte count.

Try It Online!

Special thanks to ovs and NK1406.

\$\endgroup\$
4
\$\begingroup\$

Pari/GP, 41 bytes

p->concat([c|c<-Vec(Str(Pol(p))),c!="*"])

Try it online!


If an * between the coefficient and the variable is allowed:

Pari/GP, 3 bytes

Pol

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Even Mathematica didn't seem to have a builtin for this one! \$\endgroup\$ – Nonny Moose Mar 16 '18 at 21:55
4
\$\begingroup\$

APL (Dyalog Classic), 114 113 109 107 106 bytes

{{⍵≡'':⍕0⋄⍵↓⍨'+'=⊃⍵}∊⍵{{'1x'≡2↑1↓⍵:¯1⌽1↓1⌽⍵⋄⍵}('-0+'[1+×⍺]~⍕0),∊(U/⍕|⍺),(U←⍺≠0)/(⍵>⍳2)/¨'x'('^',⍕⍵)}¨⌽⍳⍴⍵}

Try it online!

-4 bytes thanks to @dzaima!

This can definitely be golfed down further. This requires ⎕IO←0

\$\endgroup\$
  • \$\begingroup\$ I finally shaved those two bytes off... \$\endgroup\$ – Zacharý Mar 15 '18 at 23:37
3
\$\begingroup\$

Pip, 78 bytes

(RV(B."x^"._MERVg)J'+)R[`\b0[^+]+``x.0|\^1|^\++|\++$``\b1x``\++-?`][xx'x_@v]|0

Takes the coefficients as command-line arguments. Try it online!

Uses ME (map-enumerate) and J (join) to generate something of the form 0x^3+-1x^2+35x^1+0x^0, and then a bunch of regex replacements to transform this into the proper format.

\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Classic), 79 76 bytes

{'^$' '\b1x' '\+?¯' '^\+'⎕r('0x-',⊂⍬)∊⍕¨(0≠⍵)⌿'+',⍵,⊖⍪((⊢↓⍨2≤⊢)↑'x^',⍕)¨⍳≢⍵}

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python 3, 161 162 bytes

Fixed a bug thanks to ovs.

l=len
lambda p:''.join(['+'*(i>0)*(c>0)+(str(c)[:-1],str(c))[abs(c)!=1or i==l(p)-1]+'x'*(i!=l(p)-1)+('^%d'%(l(p)+~i))*(i<l(p)-2)for i,c in enumerate(p)if c])or'0'

Expanded:

l=len # Alias the len function since we use it a lot
lambda p: ''.join([ # Join a list of strings
    '+'*(i>0)*(c>0) # Prepend a + if this isn't the first term and the coefficient is positive
    + (str(c)[:-1], str(c))[abs(c) != 1 or i == l(p) - 1] # If the coefficient is 1 and this isn't the last term, delete the '1' from the string representation, otherwise just use the string representation
    + 'x' * (i != l(p) - 1) # If this isn't the last term, append an x
    + ('^%d' % (l(p) + ~i)) * (i < l(p) - 2) # If this isn't one of the last two terms, append the exponent
for i, c in enumerate(p) if c]) # Iterating over each coefficient with its index, discarding the term if the coefficient is zero
or '0' # If all of the above resulted in an empty string, replace it with '0'
\$\endgroup\$
3
\$\begingroup\$

C#, 237 bytes

c=>{var b=1>0;var r="";int l=c.Length;var p=!b;for(int i=0;i<l;i++){int n=c[i];int e=l-1-i;var o=p&&i>0&&n>0?"+":n==-1&&e!=0?"-":"";p=n!=0?b:p;r+=n==0?"":o+(e==0?$"{n}":e==1?$"{n}x":n==1||n==-1?$"x^{e}":$"{n}x^{e}");}return r==""?"0":r;}
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Mar 16 '18 at 21:00
3
\$\begingroup\$

Clean, 172 bytes

import StdEnv,Text
r=reverse
@""="0"
@a|a.[size a-1]<'0'=a+"1"=a
? -1="-"
?1=""
?a=a<+""
$l=join"-"(split"+-"(join"+"(r[?v+e\\v<-r l&e<-["","x":map((<+)"x^")[1..]]|v<>0])))

Try it online!

\$\endgroup\$
  • \$\begingroup\$ @BMO fixed temporarily pending more golfing. \$\endgroup\$ – Οurous Mar 17 '18 at 0:06
3
\$\begingroup\$

Wolfram Language/Mathematica, 39 bytes

TraditionalForm@Expand@FromDigits[#,x]&

Try it online!

Turns out there is a built-in to get in in the right order.

Previous solution:

Wolfram Language/Mathematica, 93 bytes

StringReplace[StringRiffle[ToString/@InputForm/@MonomialList@FromDigits[#,x],"+"],"+-"->"-"]&

At least to me, this is suprisingly long for a language designed for mathematical manipulation. It seems like Expand@FromDigits[#,x]& should work, but the default ordering for polynomials is the reverse of what the question requires, so some extra finagling is required.

Explanation

FromDigits[#,x]               converts input list to polynomial (technically converts to a number in base x)
MonomialList@                 gets list of terms of polynomial
InputForm/@                   converts each term to the form a*x^n
ToString/@                    then to a string version of that
StringRiffle[...,"+"]         joins using +'s
StringReplace[...,"+-"->"-"]& replaces +-'s with -'s
\$\endgroup\$
  • \$\begingroup\$ Shouldn't SringReplace be StringReplace? \$\endgroup\$ – Scott Milner Mar 16 '18 at 18:38
  • \$\begingroup\$ @ScottMilner Must've been a mistake when I was copying it over. Thanks for noticing it! \$\endgroup\$ – DanTheMan Mar 16 '18 at 18:39
3
\$\begingroup\$

Python3: 150 146 bytes

f=lambda l:''.join('+-'[a<0]+str(a)[a<0:5*((abs(a)!=1)|(1>i))]+'x^'[:i]+str(i)[:i-1]for i,a in zip(range(len(l)-1,-1,-1),l)if a).lstrip('+')or '0'

(previous implementations):

f=lambda l: ''.join('+-'[a<0]+str(a)[a<0:5*((abs(a)!=1)|(1>i))]+'x^'[:i]+str(i)[:i-1] for i,a in zip(range(len(l)-1,-1,-1),l) if a).lstrip('+') or '0'

You can try it online

Kudos to: @Benjamin

\$\endgroup\$
  • 1
    \$\begingroup\$ Arhg, got me! You bring it down by 4 by removing some spaces: f=lambda l:''.join('+-'[a<0]+str(a)[a<0:5*((abs(a)!=1)|(1>i))]+'x^'[:i]+str(i)[:i-1]for i,a in zip(range(len(l)-1,-1,-1),l)if a).lstrip('+')or '0' \$\endgroup\$ – Benjamin Mar 17 '18 at 4:55
3
\$\begingroup\$

Perl 5 -a, 94 bytes

($_=shift@F)&&push@a,@a*!/-/>0&&'+',@F?s/\b1\b//r:$_,@F>0&&'x',@F>1&&'^'.@F while@F;say@a?@a:0

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Doesn't seem to work correctly if the final (constant) coefficient is 1 or -1. \$\endgroup\$ – nwellnhof Mar 17 '18 at 18:14
  • \$\begingroup\$ Dang. Must have broken that while I was golfing it. Fixed it with a few more bytes. \$\endgroup\$ – Xcali Mar 17 '18 at 20:58
2
\$\begingroup\$

Retina 0.8.2, 113 bytes

\w+
a$'b$&
a( [^b ]*)*?b(\d+)
$2x^$#1
(\^1|x\^0)(?!\d)

(?<= |-|^)(1(?=x)|0[^ -]*)

([ -])*
$1
[ -]$|^ 

^$
0
 
+

Try it online!

I'm sure there is a lot to golf here...

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

Haskell, 166 163 bytes

g s|l<-length s,v:w:r<-id=<<["- +"!!(1+signum m):(id=<<[show$abs m|abs m>1||e==0]++["x"|e>0]++['^':show e|e>1])|(e,m)<-zip[l-1,l-2..]s,m/=0]=[v|v>'+']++w:r|1<3="0"

Try it online! Example usage: g [0,-1,35,0] yields "-x^2+35x".


Previous 166 byte solution, which is slightly better readable:

0#n=show n
m#n=id=<<[show n|n>1]++"x":['^':show m|m>1]
m%0=""
m%n|n<0='-':m#(-n)|1<3='+':m#n
g s|l<-length s,v:m:r<-id=<<zipWith(%)[l-1,l-2..]s=[v|v>'+']++m:r|1<3="0"

Try it online!

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

Ruby, 111 bytes

->a{i=a.size;s=a.map{|x|i-=1;"%+d"%x+[?x,"x^#{i}",""][i<=>1]if x!=0}*'';s[0]?s.gsub(/(?<!\d)1(?=x)|^\+/,""):?0}

Try it online!

Solving this in Ruby turned out to be a bit frustrating, mainly due to the fact that unlike most languages, in Ruby (almost) everything is truthy, including 0-s and empty strings, so that even a simple check for zero becomes nowhere near as short as x?.

I played with various methods of constructing the string, and ultimately settled on a mix of several approaches:

  • Terms with 0 coefficients are dropped using a simple conditional
  • + and - signs are produced by formatting syntax with forced sign: %+d
  • The correct form or x^i is selected using rocket operator indexing [...][i<=>1]
  • Leading + and unnecessary 1-s are removed by regex replacements
\$\endgroup\$
2
\$\begingroup\$

Husk, 44 43 41 40 bytes

|s0Ψf¤|□ṁ`:'+f¹zμ+↓s²_&ε²¹↑□¹+"x^"s)¹m←ṡ

Try it online!

This feels a bit clunky; Husk is not optimized for string manipulation. I borrowed some ideas from the Stax answer.

Explanation

         Implicit input, say L = [2,-3,0,-1].
         First we compute the exponents.
ṡ        Reversed indices: [4,3,2,1]
m←       Decrement each: [3,2,1,0]
         Then we format the individual terms of the polynomial.
zμ...)¹  Zip with L using two-argument lambda:
          Arguments are coefficient and index, say C = -3 and I = 2.
+"x^"s    Convert I to string and concatenate to "x^": "x^2"
↑□¹       Take first I*I characters (relevant when I = 0 or I = 1): "x^2"
_&ε²¹     Check if abs(C) <= 1 and I != 0, negate; returns -1 if true, 0 if false.
↓s²       Convert C to string and drop that many elements (from the end, since negative).
          Result: "-3"
          The drop is relevant if C = 1 or C = -1.
+         Concatenate: "-3x^2"
         Result of zipping is ["2x^3","-3x^2","x","-1"]
f¹       Keep those where the corresponding element of L is nonzero: ["2x^3","-3x^2","-1"]
         Next we join the terms with + and remove extraneous +s.
ṁ        Map and concatenate
`:'+      appending '+': "2x^3+-3x^2+-1+"
Ψf       Adjacent filter: keep those chars A with right neighbor B
¤|□       where at least one of A or B is alphanumeric: "2x^3-3x^2-1"
|s0      Finally, if the result is empty, return "0" instead.
\$\endgroup\$
2
\$\begingroup\$

Perl 6, 97 bytes

{$!=+$_;.map({('+'x?($_&&$++&$_>0)~.substr(--$!&&2>.abs)~(<<''x>>[$!]//'x^'~$!))x?$_}).join||'0'}

Try it online!

Explanation:

$!=+$_;

$! keeps track of the current exponent.

'+'x?($_&&$++&$_>0)

Add + before positive coefficients, except if it's the first non-zero one. The $_&& short circuit makes sure that the anonymous state variable $ is only incremented for non-zero coefficients. The & junction is collapsed when coerced to Bool with ?.

.substr(--$!&&2>.abs)

Decrement $!. Chop 1 or -1 coefficient unless it's constant.

<<''x>>[$!]//'x^'~$!

Special-case linear and constant terms. Using the quote-protecting << >> construct is one byte shorter than the equivalent ('','x') or 2>$!??'x'x$!!!'x^'~$!.

x?$_

Hide zero terms, but always evaluate the preceding expression for the --$! side effect.

||'0'

Return 0 if all coefficients are zero.

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

Java 8, 202 176 174 173 bytes

a->{String r="";int j=a.length;for(int i:a)r+=i==0*j--?"":"+"+i+(j<1?"":j<2?"x":"x^"+j);return r.isEmpty()?"0":r.substring(1).replace("+-","-").replaceAll("(\\D)1x","$1x");}
  • 26 bytes thanks to @Nevay.

Explanation:

Try it online.

a->{                     // Method with String-array parameter and String return-type
  String r="";           //  Result-String, starting empty
  int j=a.length;        //  Power-integer, starting at the size of the input-array
  for(int i:a)           //  Loop over the array
    r+=i==0              //   If the current item is 0
           *j--?         //   (And decrease `j` by 1 at the same time)
        ""               //    Append the result with nothing
       :                 //   Else:
        "+"              //    Append the result with a "+",
        +i               //    and the current item,
        +(j<1?           //    +If `j` is 0:
           ""            //      Append nothing more
          :j<2?          //     Else-if `j` is 1:
           "x"           //      Append "x"
          :              //     Else:
           "x^"+j);      //      Append "x^" and `j`
  return r.isEmpty()?    //  If `r` is still empty
    "0"                  //   Return "0"
   :                     //  Else:
    r.substring(1)       //   Return the result minus the leading "+",
     .replace("+-","-")  //   and change all occurrences of "+-" to "-",
     .replaceAll("(\\D)1x","$1x");}
                         //   and all occurrences of "1x" to "x"
\$\endgroup\$
  • 1
    \$\begingroup\$ 176 bytes: a->{String r="";int j=a.length;for(int u:a)r+=u==(j^j--)?"":"+"+u+(j<1?"":j<2?"x":"x^"+j);return r.isEmpty()?"0":r.substring(1).replace("+-","-").replaceAll("([+-])1x","$1x");} \$\endgroup\$ – Nevay Mar 17 '18 at 14:44
  • 1
    \$\begingroup\$ @Nevay I only now realize all inputs are integers.. I used a String-input because I thought decimal inputs were allowed as well.. >.> Anyway, thanks for the -26 bytes. And I've been able to golf 2 more by changing (j^j--) to 0*j--. \$\endgroup\$ – Kevin Cruijssen Mar 17 '18 at 20:47
2
\$\begingroup\$

Python, 165 bytes

lambda a:"".join([("+"if c>0 and i+1<len(a)else"")+(str(c)if i==0 or abs(c)!=1 else "")+{0:"",1:"x"}.get(i,"x^"+str(i))for i,c in enumerate(a[::-1])if c][::-1])or"0"
\$\endgroup\$
1
\$\begingroup\$

PHP, 213 Bytes

$p=0;for($i=count($a=array_reverse(explode(',',trim($argv[1],'[]'))))-1;$i>=0;$i--)if(($b=(float)$a[$i])||(!$i&&!$p)){$k=abs($b);echo ($b<0?'-':($p?'+':'')).((($k!=1)||!$i)?$k:'').($i>1?'x^'.$i:($i?'x':''));$p=1;}

Command line argument as requested by OP (single argument with brackets and commas).

Pretty print and some explanation:

$p = false; /* No part of the polynomial has yet been printed. */
for ($i = count($a = array_reverse(explode(',',trim($argv[1],'[]')))) - 1; $i >= 0; $i--)
{
    $b = (float)$a[$i]; /* Cast to float to avoid -0 and numbers like 1.0 */
    if (($b != 0) or (($i == 0) and !$p)) /* Print, if $b != 0 or the constant if there is no part until here. */
    {
        $k = abs($b);
        echo ($b < 0 ? '-' : ( $p ? '+' : '')); /* Sign. The first sign is suppressed (if $p is false) if $b positive. */
        echo ((($k != 1) || ($i == 0)) ? $k : '');  /* Coefficient */
        echo ($i > 1 ? 'x^' . $i : (($i != 0) ? 'x' : ''));  /* x^3, x^2, x, constant with empty string. */
        $p = true; /* Part of the polynomial has been printed. */
    }
}
\$\endgroup\$
1
\$\begingroup\$

PowerShell, 295 bytes

$c=$args[0]
$p=$c.length-1
$i=0
$q=""
while($p -ge 0){$t="";$e="";$d=$c[$i];switch($p){0{$t=""}1{$t="x"}Default{$t="x^";$e=$p}}if($d-eq 0){$t=""}elseif($d-eq 1){$t="+$t$e"}elseif($d-eq-1){$t="-$t$e"}elseif($d-lt 0 -or$i -eq 0){$t="$d$t$e"}else{$t="+$d$t$e"}$q+=$t;$i++;$p--}if($q -eq""){$q=0}
$q
\$\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.