8
\$\begingroup\$

Problem

I've got a GREAT new program that will change the way we think about math in computing, taking in strings of algebraic functions and doing AMAZING things with them! The only problem, is that I am only able to parse specific algebra, otherwise the universe folds into itself, which is bad. Fortunately, I only need a few basic operations in this amazing new program's input, but I still need it expanded!

Rules

  • An answer must be able to simplify the following expressions

    • 2+2 should reduce to 4
    • (5+x)+6 should reduce to x+11
    • (x+2)^2 should reduce to x^2+4*x+4
    • (x-5)*(3+7*x) should reduce to 7*x^2-32*x-15
    • 5*x+9*x should reduce to 14*x
    • (2*x^2)*x^3 should reduce to 2*x^5
  • Answers must be able to COMPLETELY remove parenthesis, which implies that all distribution must take place.

  • Answers should be able to handle all of the following operators and standard tokens:

    • + (The addition function)
    • - (The subtraction function)
    • * (The multiplication function)
    • ( (The left parenthesis, used to indicate a group)
    • ) (The right parenthesis, used to indicate the end of the last started group)
    • x (The standard variable)
    • [0-9]+ (literal nonnegative numbers)
  • Answers must be capable of at least squaring, using the notation expr^2, including (expr)^2 recursively, since (expr) is itself an expression ;)

  • A solution must be in a standard infix notation, none of the RPN nonsense!

  • No library functions such as Mathematica's Simplify to do this for you.

  • Solution should be a function that takes in a single argument and return the expanded version

As this is code-golf, the answer with the fewest (key)strokes wins, 1 week from OP.

Notes

There are no spaces in this world of math, of course! Only parenthesis.

So no division is required to save from factoring

Standard order of operations apply.

I'm aware that some of what I'm asking is simplification (e.g. 2+2=4) where other parts are actually the opposite, such as expanding (x+1)^2 to be x^2+2x+1. This is intentional. :)

-25 strokes for a solution that can do (expr)^n instead of just (expr)^2

-15 strokes for a solution able to evaluate juxtaposed multiplication, such as 4x+5x == 9x, or 4(x+1) = 4x+4

-5 strokes for a solution able to handle multiple variables (A variable being exactly one lowercase alphabet character)

-5 strokes for a solution able to remove leading 0's (007 to just 7 [Not today, Bond!] [Jeez now I feel like I'm writing Lisp])

\$\endgroup\$
  • \$\begingroup\$ I do believe that (x-5)*(3+7*x) is (1*x + -5)*(7*x + 3) is 7*x^2 + (3-35)*x + -15 or 7*x^2-32*x-15 \$\endgroup\$ – Jeff Grigg Jul 9 '14 at 22:19
  • \$\begingroup\$ How should input be provided? Command line arguments? Standard input? Should probably be specified. \$\endgroup\$ – Frxstrem Jul 9 '14 at 22:26
  • \$\begingroup\$ @JeffGrigg This is why I need the program ;) Hehe I actually added the 7*x to display more complexity and forgot to update the solution. Thanks! And I could have sworn I included that they should be taken as an argument to a function \$\endgroup\$ – Christopher Wirt Jul 9 '14 at 22:38
  • 1
    \$\begingroup\$ I nearly have a working solution for this in J, I just need to parse negative numbers correctly. It's probably the ugliest, hackiest thing I've ever written, but thankfully it's almost over. \$\endgroup\$ – algorithmshark Jul 13 '14 at 10:51
  • 1
    \$\begingroup\$ @ssdecontrol without division, we are speaking of polynomials. Add the division and it's a very different thing \$\endgroup\$ – edc65 Jul 18 '14 at 18:44
2
\$\begingroup\$

J - 350 char - 25 = 325 pts

Forgive me, Roger Hui, for I have sinned.

x=:0 1
f=:(('+_';'-';'_';'-')rplc~' '-.~'+'}.@,@|.@,.s(}.@]`(,&":)@.t'*x'"_`('*x^',":)`(''"_)@.t=.*@<:@[)/"1@#~0~:0{|:@s=.,.i.@#)@p=:(0{::'()'+/@,:&,e'+'@((+/@,:&,-)~e'-')@(*/a e'*')@('^'(*/(a=.+//.@)/@#,:e=:2 :'(<@; ::({:u/&.>{.)/.~i.@#-i.@#(>+>:)(<,v){.@i.~])^:_'))@:(([^:(''-:])". ::])&.>)@([-.~;@]<@(p^:(1<#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&;:])

The above monstrosity defines a number of variables, of which the variable f is a function satisfying the constraints in the question above. I claim the "expr^n" bonus for 25 points.

Here's the golf in action at the J REPL.

   x=:0 1
   f=:(('+_';'-';'_';'-')rplc~' '-.~'+'}.@,@|.@,.s(}.@]`(,&":)@.t'*x'"_`('*x^',":)`(''"_)@.t=.*@<:@[)/"1@#~0~:0{|:@s=.,.i.@#)@p=:(0{::'()'+/@,:&,e'+'@((+/@,:&,-)~e'-')@(*/a e'*')@('^'(*/(a=.+//.@)/@#,:e=:2 :'(<@; ::({:u/&.>{.)/.~i.@#-i.@#(>+>:)(<,v){.@i.~])^:_'))@:(([^:(''-:])". ::])&.>)@([-.~;@]<@(p^:(1<#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&;:])

   f '2+2'
4
   f '(5+x)+6'
x+11
   f '(x+2)^2'
x^2+4*x+4
   f '(x-5)*(3+7*x)'
7*x^2-32*x-15
   f '5*x+9*x'
14*x
   f '(2*x^2)*x^3'
2*x^5
   f '(2*x+3)^(2+3)*2^3'   NB. bonus
256*x^8+1920*x^7+5760*x^6+8640*x^5+6480*x^4+1944*x^3

Here's the gist of what's going on.

  • '()'...@([-.~;@]<@(p^:(1<#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&;: - Recursively break down the expression based on its parenthesized subexpressions, and evaluate them (the ... bit, to be described below) as they are ready. ;: performs the tokenizing.
  • (([^:(''-:])". ::])&.>) - Evaluate atoms. If the atom is numeric, it is turned into a scalar number. If the atom is an operator, it is left as-is. If the atom is the variable x, it is turned into the vector 0 1. (That's why we define x=:0 1 at the start.) In general we store the polynomial a*x^n + b*x^(n-1) + ... + c*x + d as the n+1-item list d c ... b a.
  • e=:2 :'(<@; ::({:u/&.>{.)/.~i.@#([->+>:){.@i.&(<,v))^:_' - This curious conjunction takes a verb on the left and a character on the right. It finds the first instance of that character in its tokenized, paren-less input, and evaluates it with the arguments around it, and repeats until there are no more such characters to find. Thus, we iteratively simplify the expression, with order of operations controlled by order of application of e.
  • And then all the stuff in the front is just pretty-printing output. rplc is a standard library function for substring replacement. We can save another three chars if we're allowed to put the lowest degree terms first instead of the highest, by removing the @|..

I am honestly uncertain whether I can squeeze any more characters out of this golf. I can't think of any other approach that doesn't require a similar amount of overengineering, but that doesn't mean there isn't one. Either way, I'm pretty sure I've squeezed all the obvious characters out of this version.

\$\endgroup\$
  • \$\begingroup\$ Bravo! And you can get rid of the negative number fix, since the - token is only noted as the subtraction function. :) \$\endgroup\$ – Christopher Wirt Jul 16 '14 at 19:15
  • \$\begingroup\$ @ChristopherWirt Didn't catch that. Either way, done. \$\endgroup\$ – algorithmshark Jul 16 '14 at 19:25
  • \$\begingroup\$ (2*x+3)^(2+3)*2^3 should give 256x^5+1920x^4+5760x^3+8640x^2+6480x+1944 or I am missing something? \$\endgroup\$ – edc65 Jul 18 '14 at 17:50
2
\$\begingroup\$

JavaScript (EcmaScript 6) 698 (748-50 bonus) 725 780 1951

To be golfed. But I'm proud it works.
(Edit: bug fix, problems with brackets and minus)
(Edit2: golfed more, fixed bug in output)
(Edit3: golfed once more, last time I promise)

Comment

Basically, function X is an infix calculator that operates on literal polynomials.
Each polynomial is stored as a js object, the key being the term (x^3y^2) and the value being the numeric coefficient. Function A,M and E are add, multiply and exponent.

Golfed Code

(It cannot probably be golfed more...) Note: not counting newlines added for (ehm...) readability

K=x=>Object.keys(x).sort(),
A=(p,q,s,t,c)=>[(c=(s+1)*q[t]+~~p[t])?p[t]=c:delete(p[t])for(t in q)],
M=(p,q,t,c,o,u,f,r,v={})=>([A(v,(r={},[(c=p[f]*q[t])&&(r[o={},(u=f+t)&&(u.match(/[a-z]\^?\d*/ig).map(x=>o[x[0]]=~~o[x[0]]+(~~x.slice(2)||1)),K(o,u=k).map(i=>u+=o[i]>1?i+'^'+o[i]:i)),u]=c)for(f in p)],r),k)for(t in q)],v),
E=(p,n)=>--n?M(p,E(p,n)):p,
O=n=>{for(l=0;h(o=s.pop())>=h(n);)a=w.pop(b=w.pop()),o=='*'?a=M(a,b):o>d?a=E(a,b[k]):A(a,b,o),w.push(a);s.push(o,n)},
X=e=>(l=k='',w=[],s=[d='@'],h=o=>'@)+-*^('.indexOf(o),
(e+')').match(/\D|\d+/g).map(t=>(u=h(t))>5?(l&&O('*'),s.push(d)):u>1?O(t):~u?s.pop(s.pop(O(t)),l=1):(l&&O('*'),l=1,w.push(v={}),t<d?v[k]=t|0:v[t]=1)),
K(p=w.pop()).map(i=>(k+=(c=p[i])>1?s+c+i:c<-1?c+i:(c-1?'-':s)+(i||1),s='+')),k||0)

Test In FireFox console

['2+2','(5+x)+6','(x+2)^2','(a+b)(a-b)','(a+b)*(a-b)','(a-b)(a-b)', '(x-5)*(3+7*x)','5*x+9*x','(2*x^2)*x^3','(2*x+3)^(2+3)*2^3']
.map(x => x + ' => ' + X(x)).join('\n')

Output

2+2 => 4
(5+x)+6 => 11+x
(x+2)^2 => 4+4x+x^2
(a+b)(a-b) => a^2-b^2
(a+b)*(a-b) => a^2-b^2
(a-b)(a-b) => a^2-2ab+b^2
(x-5)*(3+7*x) => -15-32x+7x^2
5*x+9*x => 14x
(2*x^2)*x^3 => 2x^5
(2*x+3)^(2+3)*2^3 => 1944+6480x+8640x^2+5760x^3+1920x^4+256x^5

Bonuses

25: 2*x+3)^(2+3)*2^3 => 1944+6480x+8640x^2+5760x^3+1920x^4+256x^5
15: 4x+5x => 9x
5: 007x+05x^(06+2) => 7x+5x^8
5: (a+b)(a-b) => a^2-b^2

Ungolfed Code

Show=(p)=>(
  Object.keys(p).sort().map(i=>(c=p[i])-1?c+1?c+i:'-'+i:i).join('+').replace(/\+-/g,'-')
)
AddMonoTo=(poly, term, coeff, c)=>(
  (c = coeff + ~~poly[term]) ? poly[term]= c : delete(poly[term])
)
AddPolyTo=(p1, p2, s, t)=>(
  [ AddMonoTo(p1, t, (s+1)*p2[t]) for (t in p2)]
)
MulTerm=(t1, t2, o={})=>(
  (t1+=t2)&&
  (t1.match(/[a-z](\^\d+)?/g).every(x=>o[x[0]]=(~~x.slice(2)||1)+(~~o[x[0]])),
  Object.keys(o,t1='').sort().every(i=>t1+=o[i]>1?i+'^'+o[i]:i)),
  t1  
)
MulMono=(poly, term, coeff, c, r={}, t)=>(
  [(c = poly[p]*coeff) && (r[MulTerm(p,term)] = c) for (p in poly) ],r
)  
MulPoly=(p1, p2, r={}, p)=>(
  [AddPolyTo(r,MulMono(p2, p, p1[p]),'') for (p in p1)],r
)
ExpPoly=(p,n,r=p)=>{
  for(;--n;)r=MulPoly(r,p);
  return r
}
Expand=ex=>
{
  var tokens = ex.match(/\D|\d+/g).push(')')
  var t,a,b,v,LastV=0
  var vstack=[]
  var ostack=['_']
  var op={ '+': 3, '-':3, '*':4, '^':6, '(':8, _: 1, ')':2}
  var OPush=o=>ostack.push(o)
  var OPop=_=>ostack.pop()
  var VPush=v=>vstack.push(v)
  var VPop=v=>vstack.pop()

  var Scan=i=>
  {
    LastV=0 ;
    for (; (t=tokens[i++]) && (t != ')'); )
    {
      if (t == '(')  
      {
        if (LastV) CalcOp('*')
        OPush('_'), i=Scan(i)
      }
      else if (op[t])
        LastV=0, CalcOp(t)
      else
      {
        if (LastV) CalcOp('*')
        LastV = 1
        VPush(v={})
        t < 'a' ? v[''] = t|0 : v[t] = 1
      }
    }
    CalcOp(t);
    OPop();
    OPop();
    LastV=1;
    return i;
  }
  var CalcOp=nop=>
  {
    for (; op[po = OPop()] >= op[nop];)
      b=VPop(), a=VPop(), CalcV(a,b,po);
    OPush(po), OPush(nop);
  }
  var CalcV=(a,b,o)=>
  {
    if (op[o] < 4) 
      AddPolyTo(a,b,o)
    else if (o == '*')
      a=MulPoly(a,b)
    else // ^
      a=ExpPoly(a,b['']) // only use constant term for exp
    VPush(a)
  }
  Scan(0)

  return Show(vstack.pop())
}
\$\endgroup\$
  • \$\begingroup\$ y u use semi-colons only in some places? Is it because the lack of frame that you need them? I'm not very EcmaScript compliant with my JS ;) \$\endgroup\$ – Christopher Wirt Jul 22 '14 at 15:14
  • \$\begingroup\$ Commas separate expression, semicolons separate statements. It's clearer in for(i1,i2,i3; c1,c2; s1,s2,s3). I have just a semicolon in golfed colde to close a statement inside a for (function O). Why commas? two stamenents must be grouped with {} while two or more expressions can be simply listed. \$\endgroup\$ – edc65 Jul 22 '14 at 15:20
1
\$\begingroup\$

Mathematica: 56 - 25 - 15 - 5 - 5 = 6

Of course no library functions as Expand or Distribute, just pattern replacement. Mathematica does almost everything for us (hax!), what is left are just rules for distribution and power expansion. The only non-trivial examples therefore are (x-5)*(3+7*x) and (x+2)^2.

f=#//.{x_ y_Plus:>(x #&/@y),x_Plus^n_:>(x #&/@x)^(n-1)}&

Examples

(x-5)*(3+7*x) // f
-15 - 32 x + 7 x^2

(x + 2)^2 // f
4 + 4 x + x^2
\$\endgroup\$
  • \$\begingroup\$ You have some very strange characters in both your examples. Can you clean it up? \$\endgroup\$ – edc65 Jul 19 '14 at 16:18
  • \$\begingroup\$ @edc65 M10 acting strange with copy/paste I guess. \$\endgroup\$ – swish Jul 19 '14 at 16:43
  • \$\begingroup\$ I probably should have banned mathematica all tofether ;) good work, though \$\endgroup\$ – Christopher Wirt Jul 19 '14 at 17:06

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.