Simplifique y tome derivadas parciales a una cadena polinómica

8

Introducción

Escriba un programa para calcular la derivada parcial de un polinomio (posiblemente multivariante) con respecto a una variable.

Desafío

Los derivados son herramientas matemáticas muy importantes que se han aplicado ampliamente en física, química, biología, economía, psicología y más para manejar todo tipo de problemas. Las expresiones con múltiples variables también son muy comunes.

En el alcance de este desafío, el siguiente BNF (forma Backus-Naur) define una cadena polinómica ("polystr" ):

<polystr> ::= <term> | <term><plusminus><polystr>

<plusminus> ::= "+" | "-"

<term> ::= <coeff> | <coeff><baseterm> | <baseterm>

<baseterm> ::= <variable> | <variable><exponent> | <baseterm><baseterm>

<coeff> ::= positive_integer

<exponent> ::= positive_integer

<variable> ::= lowercase_ASCII_letters

Donde positive_integery lowercase_ASCII_lettersson bastante autoexplicativos.

Por ejemplo, La cadena 3x2y-x3y-x2y+5significa 3*(x^2)*y-(x^3)*y-(x^2)*y+5. Los términos dados en la entrada pueden aparecer en cualquier orden, y las variables en cada término también pueden aparecer en cualquier orden. Entonces, por ejemplo, 5-yx2-x3y+y3x2también es una entrada válida y, de hecho, es la misma que en el ejemplo anterior.

La regla para tomar derivadas parciales es hacerlo término por término. Si la variable aparece no aparece en el término, la derivada es cero. De lo contrario, el coeficiente del término se multiplica por el exponente de esa variable, y luego el exponente de la variable se reduce en uno. Los exponentes para otras variables no cambian. Esto solo sigue la definición en matemáticas. Además, si el exponente resultante es cero, elimine la variable del término.

Por ejemplo, para tomar la derivada parcial de 5z-z2y2-5w3ycon respecto a y. Se realiza el siguiente proceso (de acuerdo con el BNF definido anteriormente, todos los "coeficientes" se consideran números positivos, es decir, los signos se consideran por separado)

          5z          -   z2y2        - 5w3y

Coeff                 1->1*2=2      5->5*1=5
Expon                 2->2-1=1      1->1-1=0
Term                  -   2yz2         - 5w3 
      (y is not here            (expon 0->y removed)
     so the term is 0)

El resultado es -2yz2-5w3y.

Por otro lado, si la expresión anterior se toma derivada parcial con respecto a a, el resultado es 0porque no aestá en ninguno de los términos.

Su tarea es escribir una función o un programa completo para calcular esta derivada. Debe tomar una cadena polinómica y un solo carácter (la variable a tomar derivada con respecto a), y devolver la derivada en la forma más simple.

"Forma más simple" significa tres cosas.

  1. El número 0(no el dígito) no debe aparecer en la salida a menos que la salida en sí sea justa 0. Por lo tanto, 0+10yni 3-y0zserá una salida válida y debe transformarse en 10yy 3-z, respectivamente.

  2. El número 1no debe aparecer como un exponente o un coeficiente, sino que puede aparecer como un término independiente en sí mismo.

  3. Los términos con exactamente el mismo conjunto de variables y exponentes deben fusionarse, lo que significa que 3a2b5-4b5a2no es una salida válida, y debería serlo -a2b5. Se puede encontrar más información sobre la entrada y la salida en la sección "Especificaciones".

Casos de prueba

Input
Output

2xy+4ax-5+7mx4-4-7x4m, x
2y+4a

4upv+5u2v3w4-4w4u2v3+qr-v,v
4up+3u2v2w4-1

12ux-7x2m3+ab5,q
0

-a+10ca11y-1nv3rt3d-poly, a
-1+110ca10y

1y+1x3y, y
1+x3

Especificaciones

  • La entrada se puede tomar a través de formularios estándar . En otras palabras, puede tomar la entrada como una cadena, una lista de caracteres, una matriz anidada de coeficientes, variables (posiblemente denotadas por su valor ASCII menos 'a' o algo similar) y exponentes, etc. También puede cambiar libremente la cadena 2*x^3y^2ao igual en lugar de 2x3y2.

Sin embargo, no use la entrada [2,0,0,0,1,0,0,3,0,0,...0](una matriz de 27 elementos) para el término 2dg, ni ningún otro formato detallado que enumere las 26 letras como esta. Su formato de entrada también debe ser capaz de tratar aby bacomo entradas diferentes (por lo que el formato de matriz de 27 elementos no es válido debido a esta restricción también).

  • Cada variable (letra) solo aparecerá una vez en cada término de la entrada, eso significa xxque no aparecerá y siempre se presentará como x2, ni aparecerá algo parecido a3b4a2.

  • Para reiterar, los términos en la entrada pueden aparecer en cualquier orden.

  • También puede elegir el formato de salida siempre que se evite el formato detallado mencionado anteriormente. Sin embargo, la salida siempre debe estar en la forma más simple como se definió anteriormente. Al igual que la entrada, los términos en la salida pueden aparecer en cualquier orden, y las variables en cada término también pueden aparecer en cualquier orden y no tiene que ser coherente entre los términos. Eso significa que pu+2up2es una salida válida. La señal para el término principal puede ser positivo o negativo y -y+3xy 3x-yson ambos válidos, por lo que es +3x-y.

  • Las entradas siempre se dan de modo que todos los coeficientes y exponentes en la salida sean menores que 2 32 -1, o el número entero más grande que pueda manejar su idioma, el que sea menor. Afirmar que el número entero más grande que puede manejar su idioma es irracionalmente pequeño y trivializar el desafío cae en la categoría de lagunas predeterminadas.

  • Este es el , gana el menor número de bytes.

  • Como de costumbre, las lagunas predeterminadas se aplican aquí.

Editar: dado que la mayoría de las respuestas hasta ahora resultan ser internas que hacen todo el desafío, y a pesar de saber que hay incorporadas, no tengo la intención de prohibirlas desde el principio, ni lo tengo ahora. Haré que los criterios ganadores se basen por idioma, es decir, el envío con la menor cantidad de bytes en cada idioma gana en ese idioma. Agregaré un fragmento estándar para un catálogo si hay suficientes envíos. Siéntase libre de seguir enviando mensajes incorporados para mostrar el poder de su idioma, pero no dude en enviar sus respuestas no incluidas, incluso si es mucho más tiempo y su idioma no tiene un mensaje incorporado. ¡Feliz código de golf en tu idioma favorito!

Weijun Zhou
fuente
@JonathanFrech El segundo y el tercer término en la entrada se pueden fusionar. Juntos dan el segundo término en la salida.
Weijun Zhou
Ah bien. En su primer ejemplo, ¿por qué -9aparece en la salida?
Jonathan Frech
1
La única razón por la que puede fusionarse en la salida es porque la entrada ya podría estar fusionada. Eso hace que esto sea realmente una combinación de 2 problemas independientes take derivativeymerge
Ton Hospel
Supongo que la forma más simple también implica no exponent 1, aunque no pareces decir esto
Ton Hospel
@ JonathanFrech Eso es un error tipográfico. Fijo.
Weijun Zhou

Respuestas:

2

Python 2 , 252 245 bytes

o,d=input()
D={};s=''
for c,t in o:T=`sorted(t)`;D[T]=D.get(T,0)+c
for t in D:
 c,t=D[t],dict(eval(t))
 if(d in t)*c:e=t[d];c*=e;t[d]=e-1;s+=('%+d '%c)[:~((-2<c<2)*sum(t.values())>0)]+''.join((v+`t[v]`*(t[v]>1))*(t[v]>0)for v in t)
print s or'0'

Pruébalo en línea!

Toma datos como una lista anidada de coeficientes y términos:

[
 [coeff1, [[var1_1,exp1_1],
           [var1_2,exp1_2],
           ... ]
 ],
 [coeff2, [[var2_1,exp2_1], ...]],
 ...
]

Por ejemplo, el primer ejemplo ( 5z-z2y2-5w3y) se da como:

[
 [ 5, [['z', 1]          ] ], 
 [-1, [['z', 2], ['y', 2]] ],
 [-5, [['w', 3], ['y', 1]] ]
]

El pie de página contiene una función que analiza una entrada de cadena con el formato de entrada deseada: parse(s).


Editar:

  • Toma entrada en lugar de función
TFeld
fuente
2

Retina , 249 233 bytes

(.)(?=.*¶\1$)
$&_
L`.\w*
G`_
^\b
+
%O`._?\d*
_\d+
*
\b[a-z]
1$&
\b(\d+)(?=.*?(_+))
$1*$2
O$`(.)_+(.+)
$2$1
+`((\+|-)_+)(.*)¶\2(_+\3)\b
$1$4
+`\+_(_*(.*)¶-)_(_*\2\b)
+$1$3
G`\b_
\b_+
$.&
_(__+)
$.1
^\+|¶|(.)__|._
$1
\b1([a-z])
$1
^$
0

Pruébalo en línea! El enlace incluye casos de prueba. Explicación:

(.)(?=.*¶\1$)
$&_

Agregue un _después de cada ocurrencia de la variable dada.

L`.\w*

Divide la entrada en términos.

G`_

Mantenga solo los términos que hacen referencia a la variable.

^\b
+

Prefijo a +si el primer término no tiene signo.

%O`._?\d*

Ordenar cada término alfabéticamente. (El signo coincide, pero eso no es un problema; de todos modos se ordena al principio).

_\d+
*

Convierta todos los exponentes de la variable en unarios.

\b[a-z]
1$&

Temporalmente prefijo 1 a esos términos sin un multiplicador.

\b(\d+)(?=.*?(_+))
$1*$2

Multiplique el multiplicador por el exponente de la variable, dejando el resultado en unario.

O$`(.)_+(.+)
$2$1

Ordenar todos los términos.

+`((\+|-)_+)(.*)¶\2(_+\3)\b
$1$4

Agregar términos del mismo signo.

+`\+_(_*(.*)¶-)_(_*\2\b)
+$1$3

Restar términos de diferentes signos.

G`\b_

Elimine los términos que fueron cancelados por un término de un signo diferente.

\b_+
$.&

Convierta el multiplicador de nuevo a decimal.

_(__+)
$.1

Disminuya exponentes mayores que tres y vuelva a convertir a decimal.

^\+|¶|(.)__|._
$1

a) Eliminar un +signo inicial b) Unir todos los términos nuevamente c) convertir cuadrados de la variable a la variable simple d) eliminar la variable si no tuviera un exponente.

\b1([a-z])
$1

Elimine el 1 temporal a menos que ya no tenga nada que multiplicar.

^$
0

Si no quedaban términos, el resultado es cero.

El respaldo de términos duplicados cuesta casi la mitad de mi recuento de bytes. Solución anterior de 123 bytes que no deduplicaba términos:

(.)(?=.*¶\1$)
$&_
L`.\w*
G`_
_\d+
*
\b[a-z]
1$&
\b(\d+)(?=.*?(_+))
$.($1*$2
_(__+)
$.1
^\+|¶|(.)__|._
$1
\b1([a-z])
$1
^$
0

Pruébalo en línea! Explicación:

(.)(?=.*¶\1$)
$&_

Agregue un _después de cada ocurrencia de la variable dada.

L`.\w*

Divide la entrada en términos.

G`_

Mantenga solo los términos que hacen referencia a la variable.

_\d+
*

Convierta todos los exponentes de la variable en unarios.

\b[a-z]
1$&

Temporalmente prefijo 1 a esos términos sin un multiplicador.

\b(\d+)(?=.*?(_+))
$.($1*$2

Multiplica el multiplicador por el exponente de la variable.

_(__+)
$.1

Disminuya exponentes mayores que tres y vuelva a convertir a decimal.

^\+|¶|(.)__|._
$1

a) Eliminar un +signo inicial b) Unir todos los términos nuevamente c) convertir cuadrados de la variable a la variable simple d) eliminar la variable si no tuviera un exponente.

\b1([a-z])
$1

Elimine el 1 temporal a menos que ya no tenga nada que multiplicar.

^$
0

Si no quedaban términos, el resultado es cero.

Neil
fuente
Impresionante, pero necesita fusionar esos dos términos en su ejemplo de TIO.
Weijun Zhou
1
@WeijunZhou Lo siento, había pasado por alto esa parte de las especificaciones. Déjame pensarlo ...
Neil
@WeijunZhou Ugh, me costó demasiados bytes, pero creo que lo tengo funcionando.
Neil
Muchas gracias por su impresionante trabajo duro. Creo que este es un buen punto para comenzar a aprender Retina.
Weijun Zhou
1

Wolfram Language (Mathematica) , 21 20 bytes

-1 byte gracias a Jonathan Frech !

ToExpression@#~D~#2&

Pruébalo en línea!

La entrada está formateada para que cada término siga coeff * var1 ^ exp1 * var2 ^ exp2 .... Si la entrada se puede tomar como una expresión en lugar de una cadena, la solución es de 1 byte: D.

notjagan
fuente
#1puede ser #.
Jonathan Frech
0

Physica , 3 bytes

Esto no usa ninguna característica nueva. y su alternativa solo ASCII, Differentiatese introdujo hace más de 10 días .

Manifestación

Asume que tanto la expresión como la variable se pasan como una cadena. Código de prueba:

f = ∂

Print[f['2*x*y+4*a*x-5+7*m*x^4-4-7*x^4*m'; 'x']]
Print[f['4*u*p*v+5*u^2*v^3*w^4-4*w^4*u^2*v^3+q*r-v'; 'v']]
Print[f['-a+10*c*a^11*y-1*n*v^3*r*t^3*d-p*o*l*y'; 'a']]

Salida exacta:

4*a + 2*y
4*p*u + 3*u**2*v**2*w**4 - 1
110*a**10*c*y - 1

Formato de expresión: *para multiplicación, **para exponenciación +y -para suma y resta en consecuencia.

Physica - Demo visual

Sr. Xcoder
fuente