TopCoder problem "RubeGoldberg" used in TCHS SRM 19 (Division I Level Three)



Problem Statement

    

Little Lucy's science project is really giving her a hard time. Her project requires that she build a Rube Goldberg device. A Rube Goldberg device is a device that performs a simple task in a convoluted way. In Lucy's case, she will be performing a series of energy transfers using a variety of parts. Each part will be formatted as "INPUT OUTPUT TIME", where INPUT is the type of energy required to start the part, OUTPUT is the type of energy released once the part has done its job, and TIME is the amount of time (in seconds) that the part takes to do its job. Lucy's parts have four different types of energy available: "CHEMICAL", "ELECTRIC", "MECHANICAL", and "THERMAL".

Lucy is going to put several of these devices in series to make a device that will run as close to target seconds as possible. The device will only work if the output from one part can be used as the input to the subsequent part. She can use any type of energy to start her machine, but she must use some part that releases last energy to complete the machine.

Given that Lucy has an infinite supply of each type of part, return the minimum absolute difference between the target time and the time that Lucy's machine operates.

 

Definition

    
Class:RubeGoldberg
Method:howClose
Parameters:String[], String, int
Returns:int
Method signature:int howClose(String[] parts, String last, int target)
(be sure your method is public)
    
 

Constraints

-parts will contain between 0 and 50 elements, inclusive.
-Each element of parts will be formatted as "INPUT OUTPUT TIME" (quotes for clarity only).
-In each element of parts, INPUT and OUTPUT will be one of "CHEMICAL", "ELECTRIC", "MECHANICAL", and "THERMAL" (all quotes for clarity only).
-In each element of parts, TIME will be an integer between 1 and 250000, inclusive, with no leading zeroes.
-last will be one of "CHEMICAL", "ELECTRIC", "MECHANICAL", and "THERMAL" (all quotes for clarity only).
-target will be between 0 and 250000, inclusive.
 

Examples

0)
    
{"CHEMICAL CHEMICAL 5"}
"CHEMICAL"
12
Returns: 2
You start the reaction with chemical energy. You can then put two copies of the part together, to get a total run time of 10.
1)
    
{"THERMAL THERMAL 5"}
"THERMAL"
13
Returns: 2
With the target being 13 instead, you should use 3 parts, overshooting by 2.
2)
    
{"CHEMICAL THERMAL 6",
"THERMAL CHEMICAL 3",
"THERMAL CHEMICAL 5"}
"THERMAL"
123
Returns: 0
3)
    
{"THERMAL CHEMICAL 4",
"CHEMICAL ELECTRIC 5",
"MECHANICAL THERMAL 8",
"ELECTRIC MECHANICAL 10"}
"MECHANICAL"
124
Returns: 1
4)
    
{"CHEMICAL MECHANICAL 12",
"MECHANICAL THERMAL 13",
"THERMAL CHEMICAL 14"}
"ELECTRIC"
123456
Returns: 123456
You have no "ELECTRIC" parts and so must start by using "ELECTRIC" energy, ending at time 0.
5)
    
{"MECHANICAL THERMAL 12","CHEMICAL ELECTRIC 228",
"CHEMICAL CHEMICAL 3361", "ELECTRIC ELECTRIC 4312",
"ELECTRIC CHEMICAL 1123", "THERMAL MECHANICAL 15000",
"MECHANICAL MECHANICAL 15000", "THERMAL THERMAL 20000"}
"THERMAL"
13579
Returns: 1433

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6809

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10071&pm=6809

Writer:

connect4

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming, Search