TopCoder problem "Partial" used in SRM 188 (Division I Level Two)

Problem Statement


Given a polynomial function of the variables x, y, and z, write a program to compute the mixed partial derivative with respect to a given list of variables.

The function will be expressed as a sum of terms. Each term will be a product of factors. Each factor will be either:

  • * an integer coefficient between 2 and 9, inclusive
  • * the variable x, y, or z, optionally raised to an integer power between 2 and 9, inclusive
Each term will contain at least one factor. Multiple factors will be separated by a '*' character. Multiple terms will be separated by a space, a '+' character, and another space. Within a term, there will not be more than one integer coefficient, and there will not be more than one factor with the same variable. However, the factors can be in any order. Examples of terms are:


Examples of functions are:

    z + 6
    y + y + 2*y
    3 + y^3*2 + z^4*7*x^3

Given a String of the characters 'x', 'y', and 'z', compute the mixed partial derivative with respect to the variables in the string. To compute a mixed partial derivative, repeatedly take the partial derivative with respect to each variable in the string in turn, using the result of each step as the input to the next. (Incidentally, because we are working with nice polynomial functions, the order in which you compute the partial derivatives does not matter.)

To compute a partial derivative:

  • * The derivative of a sum of terms is equal to the sum of the derivatives of each term.
  • * The derivative of a term with respect to a variable not contained in the term is zero.
  • * The derivative of a term with respect to a variable contained in the term can be computed by multiplying the term by the power of that variable, and then decreasing the power of that variable by 1.

Examples of taking the partial derivatives of functions with respect to y:

    3                    ->  0
    x^2                  ->  0
    y                    ->  1
    4*y                  ->  4
    2*y^5                ->  10*y^4
    7*y*z^3              ->  7*z^3
    x^2*y^3 + 9*y^4*z^5  ->  3*x^2*y^2 + 36*y^3*z^5

Your program should return the result as a String, formatted the same way as the input string, with the following additional constraints. Terms with the same powers of all three variables should be combined into a single term, by adding their coefficients. The terms should be sorted with the terms of higher degree (sum of powers of x, y, and z) before terms of lower degree. If two terms have the same degree, output the term with the higher power of x first. If two terms have the same degree and same power of x, output the term with the higher power of y first. Within a term, output the integer coefficient first, followed by the x, y, and z factors, in that order.

As with the input String, exponents should only be included only if greater than 1. If as the result of differentiation the power of a variable is reduced to zero, that factor should be omitted. Similarly, integer coefficients of 1 should be omitted. Exception: if a term consists of only the integer coefficient 1, with no x, y, or z factors, that term should be output as "1". Entire terms reduced to zero should be completely omitted.

If the result contains no terms, return the String "0".



Parameters:String, String
Method signature:String derivative(String expr, String vars)
(be sure your method is public)


-Pay careful attention to the instructions regarding formatting of the output string.
-The only spaces in the input and output are immediately before and after all '+' characters.
-If the vars String is empty, return the given function, subject to the output formatting rules specified in the problem.


-expr will contain between 1 and 50 characters, inclusive.
-vars will contain between 0 and 5 characters, inclusive.
-vars will contain only the characters 'x', 'y', and 'z', in any order, possibly with multiple occurrences of the same character.
-No term in expr will contain more than one constant factor.
-No term in expr will contain the same variable more than once.
-expr will be formatted as described in the problem statement.


Returns: "7"
The derivative of 7x with respect to x is 7.
"x + z + 9*z^2 + y*z^3"
Returns: "3*y*z^2 + 18*z + 1"
The partial derivative of x with respect to z is 0, z with respect to z is 1, 9z2 with respect to z is 18z, and yz3 is 3yz2.
Returns: "4*x*y*z^2"
The partial derivative of x2y2z2 with respect to x is 2xy2z2. The partial derivative of 2xy2z2 with respect to y is 4xyz2.
"y*8*z*x^3 + x^5 + y*2*x^4 + 9*x^4*z + x^5*5"
Returns: "6*x^5 + 2*x^4*y + 9*x^4*z + 8*x^3*y*z"
Variables and constant factors can appear in any order in the input. The vars string can be empty. Terms must be sorted in the correct order. Terms with equal powers of all variables must be added together.
"9*x^9*y^9*z^9 + x^2*y^2*z^2"
Returns: "419904*x^8*y^7*z^7 + 8*x"
"x + y + z"
Returns: "0"
"9*x^9 + 9*x^9 + 9*x^9 + 9*x^9 + 9*x^9 + 9*x^9"
Returns: "54*x^9"

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

String Parsing