Statistics

Problem Statement for "TaylorAlgebra"

Problem Statement

You will be given a String formula that adheres to the folowing pseudo-grammar (quotes for clarity):
  <FORMULA> :== D(<FORMULA>) | I(<FORMULA>) | T(<NUM>,<FORMULA>) | 'f'
      <NUM> :== a positive integer between 1 and 100 inclusive with no leading zeros
The following congruences allow us to change a formula into an equivalent one (here F denotes some <FORMULA>):
      D(I(F)) == F
      I(D(F)) == F
    D(T(i,F)) == T(i-1,D(F))
    I(T(i,F)) == T(i+1,I(F))
Return a String describing a formula equivalent to the input such that the total number of 'D's and 'I's is minimized. The returned value must be formatted like the input. If there are multiple possible return values, choose the one where no 'D' or 'I' could be nested deeper using a single congruence. Remember that any number in the returned value, as well as in any intermediate formulae, must be between 1 and 100, inclusive.

Definition

Class:
TaylorAlgebra
Method:
getCanonical
Parameters:
String
Returns:
String
Method signature:
String getCanonical(String formula)
(be sure your method is public)

Constraints

  • formula will contain between 1 and 50 characters, inclusive.
  • formula will adhere to the grammar in the statement.

Examples

  1. "T(100,f)"

    Returns: "T(100,f)"

    None of the congruences are appropriate.

  2. "D(T(50,f))"

    Returns: "T(49,D(f))"

    The 'D' can be nested more deeply.

  3. "D(T(1,f))"

    Returns: "D(T(1,f))"

    We want to push the 'D' inward, but that would drop the number lower than 1.

  4. "I(T(100,f))"

    Returns: "I(T(100,f))"

    Pushing the 'I' inward would force the number above 100.

  5. "D(T(40,I(f)))"

    Returns: "T(39,f)"

  6. "I(T(40,D(f)))"

    Returns: "T(41,f)"

  7. "D(D(D(D(I(I(I(D(D(D(I(f)))))))))))"

    Returns: "D(D(D(f)))"

  8. "D(I(T(1,f)))"

    Returns: "T(1,f)"

  9. "I(D(T(1,f)))"

    Returns: "T(1,f)"

  10. "I(D(D(T(1,f))))"

    Returns: "D(T(1,f))"

  11. "D(D(D(D(D(D(D(D(D(D(D(D(D(D(T(10,f)))))))))))))))"

    Returns: "D(D(D(D(D(T(1,D(D(D(D(D(D(D(D(D(f)))))))))))))))"

  12. "I(I(I(I(I(I(I(I(I(I(I(I(I(I(T(90,f)))))))))))))))"

    Returns: "I(I(I(I(T(100,I(I(I(I(I(I(I(I(I(I(f)))))))))))))))"

  13. "D(D(D(D(D(D(D(T(97,D(D(T(98,f)))))))))))"

    Returns: "T(90,T(89,D(D(D(D(D(D(D(D(D(f)))))))))))"

  14. "D(D(D(D(D(D(D(T(4,D(D(T(3,f)))))))))))"

    Returns: "D(D(D(D(T(1,D(D(D(T(1,D(D(f)))))))))))"

  15. "T(10,T(10,T(10,T(10,T(10,T(10,T(10,f)))))))"

    Returns: "T(10,T(10,T(10,T(10,T(10,T(10,T(10,f)))))))"

  16. "D(T(10,T(10,T(10,T(10,T(10,T(10,T(10,f))))))))"

    Returns: "T(9,T(9,T(9,T(9,T(9,T(9,T(9,D(f))))))))"

  17. "D(T(10,T(10,T(10,T(10,T(1,T(10,T(10,f))))))))"

    Returns: "T(9,T(9,T(9,T(9,D(T(1,T(10,T(10,f))))))))"

  18. "I(T(10,T(10,T(10,T(10,T(10,T(10,T(10,f))))))))"

    Returns: "T(11,T(11,T(11,T(11,T(11,T(11,T(11,I(f))))))))"

  19. "I(T(10,T(10,T(10,T(100,T(10,T(10,T(10,f))))))))"

    Returns: "T(11,T(11,T(11,I(T(100,T(10,T(10,T(10,f))))))))"

  20. "f"

    Returns: "f"

  21. "D(f)"

    Returns: "D(f)"

  22. "D(D(D(D(D(D(D(D(D(I(I(I(I(I(I(I(f))))))))))))))))"

    Returns: "D(D(f))"

  23. "f"

    Returns: "f"

  24. "D(f)"

    Returns: "D(f)"

  25. "I(f)"

    Returns: "I(f)"

  26. "D(T(1,I(T(100,D(T(1,I(T(100,D(T(1,f))))))))))"

    Returns: "D(T(1,I(T(100,D(T(1,I(T(100,D(T(1,f))))))))))"

  27. "D(D(T(2,D(T(2,D(T(2,D(T(2,I(f))))))))))"

    Returns: "D(T(1,D(T(1,D(T(1,D(T(1,f))))))))"

  28. "D(D(D(D(D(D(D(D(D(I(I(I(I(I(I(I(f))))))))))))))))"

    Returns: "D(D(f))"

  29. "f"

    Returns: "f"

  30. "D(f)"

    Returns: "D(f)"

  31. "I(f)"

    Returns: "I(f)"

  32. "D(T(1,I(T(100,D(T(1,I(T(100,D(T(1,f))))))))))"

    Returns: "D(T(1,I(T(100,D(T(1,I(T(100,D(T(1,f))))))))))"

  33. "D(D(T(2,D(T(2,D(T(2,D(T(2,I(f))))))))))"

    Returns: "D(T(1,D(T(1,D(T(1,D(T(1,f))))))))"

  34. "D(D(D(D(D(D(D(D(D(D(D(D(T(12,f)))))))))))))"

    Returns: "D(T(1,D(D(D(D(D(D(D(D(D(D(D(f)))))))))))))"

  35. "D(T(2,f))"

    Returns: "T(1,D(f))"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: