Problema

¡Tengo un GRAN programa nuevo que cambiará la forma en que pensamos sobre las matemáticas en la informática, tomando cadenas de funciones algebraicas y haciendo cosas INCREÍBLES con ellas! El único problema es que solo soy capaz de analizar álgebra específica, de lo contrario, el universo se pliega en sí mismo, lo cual es malo. Afortunadamente, solo necesito algunas operaciones básicas en la increíble entrada de este nuevo programa, ¡pero todavía necesito que se expanda!

Reglas

• Una respuesta debe poder simplificar las siguientes expresiones

  • 2+2 debería reducir a 4
  • (5+x)+6 debería reducir a x+11
  • (x+2)^2 debería reducir a x^2+4*x+4
  • (x-5)*(3+7*x) debería reducir a 7*x^2-32*x-15
  • 5*x+9*x debería reducir a 14*x
  • (2*x^2)*x^3 debería reducir a 2*x^5

• Las respuestas deben poder COMPLETAMENTE eliminar el paréntesis, lo que implica que toda la distribución debe tener lugar.

• Las respuestas deberían poder manejar todos los siguientes operadores y tokens estándar:

  • + (La función de suma)
  • - (La función de resta)
  • * (La función de multiplicación)
  • ( (El paréntesis izquierdo, usado para indicar un grupo)
  • ) (El paréntesis derecho, usado para indicar el final del último grupo iniciado)
  • x (La variable estándar)
  • [0-9]+ (números literales no negativos)

• Las respuestas deben ser capaces de al menos cuadrar, usando la notación expr ^ 2, incluyendo (expr) ^ 2 recursivamente, ya que (expr) es en sí misma una expresión;)

• Una solución debe estar en una notación infija estándar, ¡ninguna de las tonterías RPN!

• No hay funciones de biblioteca como Mathematica Simplifypara hacer esto por usted.

• La solución debe ser una función que tome un solo argumento y devuelva la versión expandida

Como se trata de código de golf, la respuesta con la menor cantidad de golpes (clave) gana, 1 semana desde OP.

Notas

¡No hay espacios en este mundo de las matemáticas, por supuesto! Solo paréntesis.

Por lo tanto, no se requiere división para salvar del factoring

Se aplica el orden estándar de operaciones.

Soy consciente de que parte de lo que estoy pidiendo es simplificación (por ejemplo 2+2=4) donde otras partes son realmente lo opuesto, como expandirse (x+1)^2para ser x^2+2x+1. Esto es intencional :)

-25 trazos para una solución que puede hacer (expr) ^ n en lugar de solo (expr) ^ 2

-15 trazos para una solución capaz de evaluar la multiplicación yuxtapuesta, como 4x+5x== 9xo 4(x+1)=4x+4

-5 trazos para una solución capaz de manejar múltiples variables (una variable es exactamente un carácter minúsculo del alfabeto)

-5 golpes para una solución capaz de eliminar los ceros a la izquierda ( 007a solo 7[¡No hoy, Bond!] [Por Dios, ahora siento que estoy escribiendo Lisp])

J - 350 caracteres - 25 = 325 pts

Perdóname, Roger Hui, porque he pecado.

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.)&;:])

La monstruosidad anterior define una serie de variables, de las cuales la variable fes una función que satisface las restricciones en la pregunta anterior. Reclamo el bono "expr ^ n" por 25 puntos.

Aquí está el golf en acción en el 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

Aquí está la esencia de lo que está sucediendo.

• '()'...@([-.~;@]<@(p^:(1<#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&;:- Descomponga recursivamente la expresión en función de sus subexpresiones entre paréntesis y evalúelas (el ...bit, que se describirá a continuación) cuando estén listas. ;:realiza la tokenización.
• (([^:(''-:])". ::])&.>)- Evaluar átomos. Si el átomo es numérico, se convierte en un número escalar. Si el átomo es un operador, se deja como está. Si el átomo es la variable x, se convierte en el vector 0 1. (Es por eso que definimos x=:0 1al principio). En general, almacenamos el polinomio a*x^n + b*x^(n-1) + ... + c*x + dcomo la n+1lista de elementos d c ... b a.
• e=:2 :'(<@; ::({:u/&.>{.)/.~i.@#([->+>:){.@i.&(<,v))^:_'- Esta curiosa conjunción toma un verbo a la izquierda y un carácter a la derecha. Encuentra la primera instancia de ese personaje en su entrada tokenizada, sin par, y la evalúa con los argumentos a su alrededor, y se repite hasta que no haya más caracteres para encontrar. Por lo tanto, simplificamos iterativamente la expresión, con el orden de las operaciones controlado por el orden de aplicación de e.
• Y luego, todo lo que está en el frente es solo una impresión bonita. rplces una función de biblioteca estándar para el reemplazo de subcadenas. Podemos guardar otros tres caracteres si se nos permite poner primero los términos de grado más bajo en lugar de los más altos, eliminando el @|..

Sinceramente, no estoy seguro de si puedo sacar más personajes de este golf. No puedo pensar en ningún otro enfoque que no requiera una cantidad similar de ingeniería excesiva, pero eso no significa que no haya ninguno. De cualquier manera, estoy bastante seguro de que he exprimido a todos los personajes obvios de esta versión.

JavaScript (EcmaScript 6) 698 (748-50 bonus) 725780 1951

Para jugar al golf . Pero estoy orgulloso de que funcione.
(Edición: corrección de errores, problemas con paréntesis y menos)
(Edición2: golf más, error corregido en la salida)
(Edición3: golf una vez más, la última vez lo prometo)

Comentario

Básicamente, la función X es una calculadora infija que opera en polinomios literales.
Cada polinomio se almacena como un objeto js, ​​la clave es el término (x ^ 3y ^ 2) y el valor es el coeficiente numérico. Las funciones A, M y E son sumar, multiplicar y exponente.

Código de golf

(Probablemente no se pueda jugar más al golf ...) Nota: sin contar las nuevas líneas agregadas para (ehm ...) legibilidad

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)

Prueba en la consola FireFox

['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')

Salida

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

Bonos

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

Código sin golf

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())
}

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

Por supuesto, ninguna biblioteca funciona como Expando Distribute, solo reemplazo de patrones. Mathematica hace casi todo por nosotros (¡hax!), Lo que queda son solo reglas de distribución y expansión de poder. Los únicos ejemplos no triviales, por lo tanto, son (x-5)*(3+7*x)y (x+2)^2.

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

Ejemplos

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

(x + 2)^2 // f
4 + 4 x + x^2