8
\$\begingroup\$

Introduction

Write a program to calculate the partial derivative of a polynomial (possibly multivariate) with respect to a variable.

Challenge

Derivatives are very important mathematical tools that has been widely applied in physics, chemistry, biology, economics, psychology and more to handle all kinds of problems. Expressions with multiple variables are also very common.

In the scope of this challenge, a polynomial string ("polystr") is defined by the following BNF (Backus–Naur form):

<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

Where positive_integer and lowercase_ASCII_letters are quite self-explanatory.

For example, The string 3x2y-x3y-x2y+5 means 3*(x^2)*y-(x^3)*y-(x^2)*y+5. The terms given in the input may appear in any order, and the variables in each term also may appear in any order. So for example 5-yx2-x3y+y3x2 is also a valid input and is in fact the same as the previous example.

The rule for taking partial derivative is just doing it term by term. If the variable appears does not appear in the term, the derivative is zero. Otherwise, the coefficient of the term is multiplied by the exponent of that variable, and then the exponent of the variable is decreased by one. The exponents for other variables do not change. This is just following the definition in mathematics. In addition, if the resulting exponent is zero, remove the variable from the term.

For example, to take the partial derivative of 5z-z2y2-5w3y with respect to y. The following process is done (in accordance with the BNF defined above, the "coefficient" are all taken to be positive numbers, i.e. the signs are considered separately)

          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)

The result is -2yz2-5w3y.

On the other hand, if the above expression is taken partial derivative with respect to a, the result is 0 because a is in none of the terms.

Your task is to write a function or a full program to calculate this derivative. It should take a polynomial string and a single character (the variable to take derivative with respect to), and return the derivative in the simplest form.

"Simplest form" means three things.

  1. The number 0 (not the digit) should not appear in the output unless the output itself is just 0. So neither 0+10y nor 3-y0z will be valid output and should be transformed to 10y and 3-z, respectively.

  2. The number 1 should not appear as an exponent or a coefficient, but can appear as a standalone term itself.

  3. The terms with exactly the same set of variables and exponents should be merged, which means 3a2b5-4b5a2 is not a valid output, and it should be -a2b5 instead. More information about the input and output can be found in the "Specs" section.

Test Cases

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

Specs

  • Input can be taken through standard forms. In other words, you can take input as a string, a list of characters, a nested array of coefficients, variables (possibly denoted by their ASCII value minus 'a' or something alike) and exponents, etc. You are also free to change the string to 2*x^3y^2 or alike instead of 2x3y2.

However, please do not use the input [2,0,0,0,1,0,0,3,0,0,...0] (an array of 27 elements) for the term 2dg, or any other verbose format that enumerates the 26 letters like this. Your input format should also be able to treat ab and ba as different inputs (so the 27-element array format is invalid due to this restriction as well).

  • Each variable (letter) will only appear once in each term of the input, that means xx will not appear and will always be presented as x2, nor will something like a3b4a2 appear.

  • To reiterate, the terms in the input may appear in any order.

  • You are also free to choose the output format provided that the verbose format mentioned above is avoided. The output should however always be in the simplest form as defined above. Just like the input, the terms in the output can appear in any order, and the variables in each term can also appear in any order and does not have to be consistent between terms. That means pu+2up2 is a valid output. The sign for the leading term can be either positive or negative and -y+3x and 3x-y are both valid, so is +3x-y.

  • The input are always given such that all the coefficients and exponents in the output will be less than 232-1, or the largest integer your language can handle, whichever is smaller. Claiming that the largest integer your language can handle is unreasonably small and trivializing the challenge falls into the category of default loopholes.

  • This is , the lowest number of bytes wins.

  • As usual, default loopholes apply here.

Edit: Since most of the answers so far turn out to be internals that do the whole challenge, and despite knowing there are builtins I don't have the intention to ban such internals from the very beginning, nor do I have now. I will make the winning criteria one that is based on a per-language basis, i.e. the submission with the least bytes in each language wins in that language. I will add a standard snippet for a catalogue if there are enough submissions. Feel free to go on submitting builtins to showcase the power of your language but please do not hesitate to submit your non-builtin answers even if it's way longer and your language does not have a builtin. Happy code golfing in your favorite language!

\$\endgroup\$
  • \$\begingroup\$ @JonathanFrech The second and the third term in the input can be merged. Together they give the second term in the output. \$\endgroup\$ – Weijun Zhou Feb 27 '18 at 21:14
  • \$\begingroup\$ Ah, okay. In your first example, why does -9 appear in the output? \$\endgroup\$ – Jonathan Frech Feb 27 '18 at 21:18
  • 1
    \$\begingroup\$ The only reason you can merge in the output is because the input could already be merged. That makes this really a combination of 2 independent problems take derivative and merge \$\endgroup\$ – Ton Hospel Feb 27 '18 at 22:15
  • \$\begingroup\$ I assume simplest form also implies no exponent 1, though you don't seem to state this \$\endgroup\$ – Ton Hospel Feb 27 '18 at 22:17
  • \$\begingroup\$ @JonathanFrech That's a typo. Fixed. \$\endgroup\$ – Weijun Zhou Feb 27 '18 at 23:07
2
\$\begingroup\$

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'

Try it online!

Takes input as a nested list of coefficients and terms:

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

For instance the first example (5z-z2y2-5w3y) is given as:

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

The footer contains a function which parses a string input to the desired input format: parse(s).


Edit:

  • Takes input instead of function
\$\endgroup\$
2
\$\begingroup\$

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

Try it online! Link includes test cases. Explanation:

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

Add a _ after each occurence of the given variable.

L`.\w*

Split the input into terms.

G`_

Keep only the terms that referenced the variable.

^\b
+

Prefix a + if the first term doesn't have a sign.

%O`._?\d*

Sort each term alphabetically. (The sign matches, but that's not a problem; it sorts at the start anyway.)

_\d+
*

Convert all exponents of the variable into unary.

\b[a-z]
1$&

Temporarily prefix 1 to those terms without a multiplier.

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

Multiply the multiplier by the exponent of the variable, leaving the result in unary.

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

Sort all of the terms.

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

Add terms of the same sign.

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

Subtract terms of different signs.

G`\b_

Remove terms that were cancelled by a term of a different sign.

\b_+
$.&

Convert the multiplier back to decimal.

_(__+)
$.1

Decrement exponents greater than three and convert back to decimal.

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

a) Remove a leading + sign b) Join all the terms back together c) convert squares of the variable to the plain variable d) remove the variable if it didn't have an exponent.

\b1([a-z])
$1

Remove the temporary 1 unless it's no longer got anything to multiply.

^$
0

If there were no terms left then the result is zero.

Supporting duplicate terms cost almost half of my byte count. Previous 123 byte solution that didn't deduplicate terms:

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

Try it online! Explanation:

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

Add a _ after each occurence of the given variable.

L`.\w*

Split the input into terms.

G`_

Keep only the terms that referenced the variable.

_\d+
*

Convert all exponents of the variable into unary.

\b[a-z]
1$&

Temporarily prefix 1 to those terms without a multiplier.

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

Multiply the multiplier by the exponent of the variable.

_(__+)
$.1

Decrement exponents greater than three and convert back to decimal.

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

a) Remove a leading + sign b) Join all the terms back together c) convert squares of the variable to the plain variable d) remove the variable if it didn't have an exponent.

\b1([a-z])
$1

Remove the temporary 1 unless it's no longer got anything to multiply.

^$
0

If there were no terms left then the result is zero.

\$\endgroup\$
  • \$\begingroup\$ Impressive, but you need to merge those two terms in your TIO example. \$\endgroup\$ – Weijun Zhou Mar 10 '18 at 12:53
  • 1
    \$\begingroup\$ @WeijunZhou Sorry, I'd overlooked that bit of the spec. Let me think about it... \$\endgroup\$ – Neil Mar 10 '18 at 14:23
  • \$\begingroup\$ @WeijunZhou Ugh, it cost me far too many bytes, but I think I've got it working. \$\endgroup\$ – Neil Mar 10 '18 at 23:59
  • \$\begingroup\$ Thank you very much for your impressive hard work. I guess this is an good point for me to start learning Retina from. \$\endgroup\$ – Weijun Zhou Mar 11 '18 at 0:09
1
\$\begingroup\$

Wolfram Language (Mathematica), 21 20 bytes

-1 byte thanks to Jonathan Frech!

ToExpression@#~D~#2&

Try it online!

The input is formatted so that every term follows coeff * var1 ^ exp1 * var2 ^ exp2 .... If the input can be taken as an expression rather than a string, the solution is 1 byte: D.

\$\endgroup\$
  • \$\begingroup\$ #1 can be #. \$\endgroup\$ – Jonathan Frech Feb 28 '18 at 2:49
0
\$\begingroup\$

Physica, 3 bytes

This doesn't use any new feature. and its ASCII-only alternative, Differentiate have been introduced more than 10 days ago.

Demo

Assumes that both the expression and the variable are passed as a string. Testing code:

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']]

Exact output:

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

Expression format: * for multiplication, ** for exponentiation, + and - for addition and subtraction accordingly.

Physica – Visual Demo

\$\endgroup\$
0
\$\begingroup\$

Python 3 + SymPy, 23 bytes

from sympy import*
diff

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 5 bytes

deriv

Try it online!

\$\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.