Statistics

Problem Statement for "HardwareOptimize"

Problem Statement

When you are compiling code to a target architecture there are hardware specific optimizations that can be made. In this problem we will be taking a string of source text and compiling it to some variable architecture. The source text will be given as a String expression. expression should be a well-parenthesized mathematical formula that conforms to the following grammar: 
<EXPR> ::= '('<EXPR><OP><EXPR>')' | <INT>
<OP> ::= '+' | '-' | '/' | '*'
<INT> ::= a positive integer with no leading 0s between 1 and 100, inclusive
For example, 9, (1+(2+((3+2)-2))), and ((1*2)/2) conform to the grammar while (1+2+3), (0+2), and ((1+2)) do not.

If expression does not conform to the above grammar your method should return -2. If it does conform, you will then have to determine which instructions should be used to implement the expression. The machine capabilities will be given in a String[] instructions. Each element will conform to the following grammar:
<INST> ::= <COST>':'<VAREXPR>
<VAREXPR> ::= '('<VAREXPR><OP><VAREXPR>')' | 'X'
<OP> ::= '+' | '-' | '/' | '*'
<COST> ::= a positive integer with no leading 0s between 1 and 100, inclusive
An example element could be 10:(X+X) meaning that there is an instruction that will add 2 operands together at a cost of 10. Another example could be 12:(X*(X-X)) meaning that it will cost 12 to multiply 1 operand by the difference of two others. Each element of instruction will thus represent the possible operations the underlying hardware can perform along with their cost. Since instructions of the form "COST:X" are meaningless they will not be allowed as input. If the given expression cannot be computed on the given hardware your method should return -1. Otherwise it should return the minimum cost required to compute all of the operations in the expression. For example: 
expression = "((1+2)*(3+(4-2)))"
instructions = {"5:(X+X)",
                "5:(X-X)",
                "6:(X*X)",
                "7:((X+X)*X)"}
Using instruction 0 on the (1+2) portion of the expression and instruction 1 on the (4-2) portion of the expression will produce the intermediate expression (3*(3+2)). Then applying expression 0 to the (3+2) portion we get the intermediate expression (3*5). Finally applying instruction 2 we get an expression that no longer contains any operations and is thus complete. The total cost of this method is 5+5+5+6 = 21. Alternatively we could have used instruction 1, then 0, and finally 3 for a smaller cost of 17. Your method should thus return 17, the minimum possible cost. The cost of applying no operations is 0. For example:
expression = "84"
instructions = {"10:(X+X)"}
Since the expression only consists of a number, there are no operations to be processed, so the cost is simply 0.

Note that you are not allowed to apply any simplifications to the expression (i.e. no associativity, commutativity, distributivity, or identity laws). This means (3+(4*5)) cannot be processed by an instruction like 4:((X*X)+X).

Definition

Class:
HardwareOptimize
Method:
bestCost
Parameters:
String, String[]
Returns:
int
Method signature:
int bestCost(String expression, String[] instructions)
(be sure your method is public)

Constraints

  • expression will contain between 1 and 50 characters inclusive
  • expression will only contain characters from the string (quotes for clarity) "0123456789+*/-()"
  • instructions will contain between 0 and 50 elements inclusive
  • Each element of instructions will contain between 7 and 50 characters inclusive
  • Each element of instructions will only contain characters from the string (quotes for clarity) "0123456789:()X+*/-"
  • Each element of instructions will adhere to the format stated above
  • There will be no elements of instructions of the form "COST:X"

Examples

  1. "((1+2)*(3+(4-2)))"

    {"5:(X+X)", "5:(X-X)", "6:(X*X)", "7:((X+X)*X)"}

    Returns: 17

  2. "(1000+1)"

    {"5:(X+X)", "5:(X-X)", "6:(X*X)", "7:((X+X)*X)"}

    Returns: -2

  3. "(10/10)"

    {"5:(X+X)", "5:(X-X)", "6:(X*X)", "7:((X+X)*X)"}

    Returns: -1

  4. "1/0"

    {"1:(X/X)"}

    Returns: -2

  5. "((1+1)*(2+2)"

    {"1:(X+X)"}

    Returns: -2

  6. "(1+2+3)"

    {}

    Returns: -2

  7. "(((1+2)+(3+4))*(((1+2)+3)+4))"

    {"100:(((X+X)+(X+X))*(((X+X)+X)+X))"}

    Returns: 100

  8. "(((1+2)+(3+4))*(((1+2)+3)+4))"

    {"100:((X+X)*(((X+X)+X)+X))"}

    Returns: -1

  9. "(((1+2)+(3+4))*(((1+2)+3)+4))"

    {"100:((X+X)*(((X+X)+X)+X))","10:(X+X)"}

    Returns: 120

  10. "(1+2)+(3+4)"

    {}

    Returns: -2

  11. "((1+2)+3)"

    {"1:(X+X)","1:((X+X)+X)"}

    Returns: 1

  12. ")12("

    {}

    Returns: -2

  13. "9999999999999999999999999999999999999999999"

    {}

    Returns: -2

  14. "))))))((((((("

    {}

    Returns: -2

  15. "((1+2)*(3-4))"

    {"1:((X-X)*(X+X))","10:(X+X)","20:(X*X)","10:(X-X)"}

    Returns: 40

  16. "((((1+1)+(1+1))+((1+1)+(1+1)))+(((1+1)+1)+(1+1)))"

    {"50:(X+X)", "49:(X+X)", "48:(X+X)", "47:(X+X)", "46:(X+X)", "45:(X+X)", "44:(X+X)", "43:(X+X)", "42:(X+X)", "41:(X+X)", "40:(X+X)", "39:(X+X)", "38:(X+X)", "37:(X+X)", "36:(X+X)", "35:(X+X)", "34:(X+X)", "33:(X+X)", "32:(X+X)", "31:(X+X)", "30:(X+X)", "29:(X+X)", "28:(X+X)", "27:(X+X)", "26:(X+X)", "25:(X+X)", "24:(X+X)", "23:(X+X)", "22:(X+X)", "21:(X+X)", "20:(X+X)", "19:(X+X)", "18:(X+X)", "17:(X+X)", "16:(X+X)", "15:(X+X)", "14:(X+X)", "13:(X+X)", "12:(X+X)", "11:(X+X)", "10:(X+X)", "9:(X+X)", "8:(X+X)", "7:(X+X)", "6:(X+X)", "5:(X+X)", "4:(X+X)", "3:(X+X)", "1:((X+X)+X)", "1:(X+X)"}

    Returns: 8

  17. "((((1+1)+(1+1))+((1+1)+(1+1)))+(((1+1)+1)+(1+1)))"

    {"50:(X+X)", "49:(X+X)", "48:(X+X)", "47:(X+X)", "46:(X+X)", "45:(X+X)", "44:(X+X)", "43:(X+X)", "42:(X+X)", "41:(X+X)", "40:(X+X)", "39:(X+X)", "38:(X+X)", "37:(X+X)", "36:(X+X)", "35:(X+X)", "34:(X+X)", "33:(X+X)", "32:(X+X)", "31:(X+X)", "30:(X+X)", "29:(X+X)", "28:(X+X)", "27:(X+X)", "26:(X+X)", "25:(X+X)", "24:(X+X)", "23:(X+X)", "22:(X+X)", "21:(X+X)", "20:(X+X)", "19:(X+X)", "18:(X+X)", "17:(X+X)", "16:(X+X)", "15:(X+X)", "14:(X+X)", "13:(X+X)", "12:(X+X)", "11:(X+X)", "10:(X+X)", "9:(X+X)", "8:(X+X)", "7:(X+X)", "6:(X+X)", "5:(X+X)", "4:(X+X)", "3:(X+X)", "2:(X+X)", "1:(X+X)"}

    Returns: 12

  18. "((((((((((1+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)"

    {"50:(X+X)", "49:(X+X)", "48:(X+X)", "47:(X+X)", "46:(X+X)", "45:(X+X)", "44:(X+X)", "43:(X+X)", "42:(X+X)", "41:(X+X)", "40:(X+X)", "39:(X+X)", "38:(X+X)", "37:(X+X)", "36:(X+X)", "35:(X+X)", "34:(X+X)", "33:(X+X)", "32:(X+X)", "31:(X+X)", "30:(X+X)", "29:(X+X)", "28:(X+X)", "27:(X+X)", "26:(X+X)", "25:(X+X)", "24:(X+X)", "23:(X+X)", "22:(X+X)", "21:(X+X)", "20:(X+X)", "19:(X+X)", "18:(X+X)", "17:(X+X)", "16:(X+X)", "15:(X+X)", "14:(X+X)", "13:(X+X)", "12:(X+X)", "11:(X+X)", "10:(X+X)", "9:(X+X)", "8:(X+X)", "7:(X+X)", "6:(X+X)", "5:(X+X)", "4:(X+X)", "3:(X+X)", "2:(X+X)", "1:(X+X)"}

    Returns: 10

  19. "(((1+1)+((1+1)+(1+1)))+(((1+1)+(1+1))+((1+1)+1)))"

    {"50:(X+X)", "49:(X+X)", "48:(X+X)", "47:(X+X)", "46:(X+X)", "45:(X+X)", "44:(X+X)", "43:(X+X)", "42:(X+X)", "41:(X+X)", "40:(X+X)", "39:(X+X)", "38:(X+X)", "37:(X+X)", "36:(X+X)", "35:(X+X)", "34:(X+X)", "33:(X+X)", "32:(X+X)", "31:(X+X)", "30:(X+X)", "29:(X+X)", "28:(X+X)", "27:(X+X)", "26:(X+X)", "25:(X+X)", "24:(X+X)", "23:(X+X)", "22:(X+X)", "21:(X+X)", "20:(X+X)", "19:(X+X)", "18:(X+X)", "17:(X+X)", "16:(X+X)", "15:(X+X)", "14:(X+X)", "13:(X+X)", "12:(X+X)", "11:(X+X)", "10:(X+X)", "9:(X+X)", "8:(X+X)", "7:(X+X)", "6:(X+X)", "5:(X+X)", "4:(X+X)", "3:(X+X)", "2:(X+X)", "1:(X+X)"}

    Returns: 12

  20. "((((1+1)/(1*(1+1)))-(1+1))/((((1+1)*1)*1)/(1+1)))"

    {"10:(X+X)", "100:(X/X)", "5:(X-X)", "9:(((X+X)/(X*(X+X)))-(X+X))", "12:((((X+X)*X)*X)/(X+X))" }

    Returns: 121

  21. "((1/(1*1))-(1/(1*1)))+((1/(1*1))-(1/(1*1)))"

    {"10:(X/(X*X))", "1:(X*X)", "1:(X-X)"}

    Returns: -2

  22. "(((1/(1*1))-(1/(1*1)))+((1/(1*1))-(1/(1*1))))"

    {"10:(X/(X*X))", "1:(X*X)", "1:(X-X)", "15:(X+X)", "19:(X+(X-X))"}

    Returns: 57

  23. "(((1+1)+((1+1)+(1+1)))+(((1+1)+(1+1))+(1+1)))"

    { "1:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "2:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "3:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "4:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "5:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "6:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "7:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "8:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "9:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "10:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "11:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "12:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "13:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "14:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "15:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "16:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "17:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "18:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "19:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "20:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "21:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "22:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "23:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "24:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "25:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "26:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "27:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "28:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "29:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "30:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "31:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "32:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "33:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "34:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "35:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "36:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "37:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "38:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "39:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "40:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "41:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "42:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "43:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "44:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "45:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "46:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "47:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "48:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "49:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))", "50:(((X+X)+((X+X)+(X+X)))+(((X+X)+(X+X))+(X+X)))"}

    Returns: 1

  24. "((((((((((1+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)"

    {"1:(X+X)", "1:(X+(X+(X+X)))", "1:((X+X)+X)", "2:(((X+X)+X)+X)", "3:((((X+X)+X)+X)+X)", "4:(((((X+X)+X)+X)+X)+X)", "5:((((((X+X)+X)+X)+X)+X)+X)" }

    Returns: 5

  25. "((0+0)*(0+0))"

    {"10:(X+X)"}

    Returns: -2

  26. "(((1+1)+((1+1)+(1+1)))+(((1+1)+(1+1))+((1+1)+1)))"

    {"10:(X+X)","19:(X+(X+X))"}

    Returns: 117

  27. "23"

    {}

    Returns: 0

  28. "(1+2)"

    {}

    Returns: -1

  29. "(1/(1-1))"

    {"1:(X-X)","1:(X/X)"}

    Returns: 2

  30. "((1*1)+1)"

    {"10:(X*X)", "10:(X+X)", "5:(X+(X*X))"}

    Returns: 20

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: