TopCoder problem "Resort" used in TCI '02 Round 3 (Division I Level Two)

Problem Statement

At most ski resorts, the runs (a run is defined as an inclined course on which one can ski downhill) are rated by their difficulty. The three classifications commonly used are Green Circle for easy, Blue Square for medium, and Black Diamond for hard. However, there can be a situation where a run is rated easy, but only feeds into hard runs (meaning that all paths from the easy run to the bottom pass through hard runs). Thus, even though the run itself is easy, it should be classified as Black Diamond, since the easiest path to the base of the mountain involves a hard run. Note that one run may feed into many other runs, and that since you are skiing downhill, once you feed into another run, there will be no way to return to any previously skied run (in other words the transitive closure of feeds is acyclic).

For the purposes of this problem, the terms "easy", "medium", and "hard" shall refer to the actual difficulty of the given run, and "Green Circle", "Blue Square", and "Black Diamond" shall refer to the compound difficulty of the easiest path to the base of the mountain from that run (called the "classification").

Given the run configuration for a ski resort, return the classification of the requested run.

The run configuration will be in the form of a String[], with each element formatted as (quotes added for clarity):

"<name>:<difficulty>,<feed1>,<feed2>,<feed3>,..."

Where <name> is the run's unique name, <difficulty> is a single character representing the difficulty ('E'asy, 'M'edium, or 'H'ard). The <feedX> arguments are all of the runs that <name> feeds into. There can be between 0 and 5 feeds, inclusive. So for example:

"BLACK STALLION:M,BLUE MOUNTAIN,FLYING TOPCODER,DOKS RUN"

is a medium run named BLACK STALLION, which feeds into BLUE MOUNTAIN, FLYING TOPCODER, and DOKS RUN. If all 3 of these were hard, then BLACK STALLION would have to be classified "BLACK DIAMOND", even though it by itself would have been a "BLUE SQUARE".

For the requested run, return either "BLACK DIAMOND" if the easiest path to the base of the mountain must include a hard run, "BLUE SQUARE" if the easiest path to the base of the mountain must include a medium run, but no hard run, and "GREEN CIRCLE" if the easiest path to the base of the mountain is all easy runs.

If, and only if, a run feeds into no other runs, it ends at the base of the mountain and should be treated as the easiest route from itself to the base. Thus if it is rated 'M', it is classified "BLUE SQUARE".

Definition

Class:	Resort
Method:	classify
Parameters:	String[], String
Returns:	String
Method signature:	String classify(String[] runs, String classify)
(be sure your method is public)

Notes

The classification of a run is not affected by the difficulty of any runs which feed into it.

Constraints

runs will contain between 1 and 50 elements, inclusive

each element of runs will consist of only capital letters ('A'-'Z'), spaces, commas (','), and a colon (':').

each element of runs will contain between 3 and 50 characters, inclusive, and will be formatted as (quotes added for clarity): "<name>:<difficulty>,<feed1>,<feed2>,<feed3>..."

there may be between 0 and 5 feeds, inclusive, for each run.

there will be no commas except for a single comma between feeds and between the difficulty and the first feed (if there is a first feed).

<difficulty> will be a single character capital letter, either 'E', 'M', or 'H'.

<name> will be between 1 and 48 characters in length, inclusive.

<name> will be unique and consist of only capital letters ('A'-'Z') and spaces, but will not begin or end with a space.

each feed will reference a run that appears as <name> in some element of runs (this is necessary to determine its difficulty).

within each element of runs, the feeds will be unique.

runs will contain no loops, i.e. runs will contain no circular or self references.

classify will be between 1 and 48 characters in length, inclusive, and will reference a run that appears as <name> in some element of runs.

Examples

{"BLACK STALLION:M,BLUE MOUNTAIN,TOPCODER,DOKS RUN"
,"BLUE MOUNTAIN:H"
,"TOPCODER:H"
,"DOKS RUN:H,CHOGYS RUN"
,"CHOGYS RUN:M,EASY RUN,MEDIUM RUN,HARD RUN"
,"EASY RUN:E"
,"MEDIUM RUN:M"
,"HARD RUN:H"}

"BLACK STALLION"

Returns: "BLACK DIAMOND"

The path to the base must go through either BLUE MOUNTAIN, TOPCODER, or DOKS RUN, all of which are hards.

{"BLACK STALLION:M,BLUE MOUNTAIN,TOPCODER,DOKS RUN"
,"BLUE MOUNTAIN:H"
,"TOPCODER:H"
,"DOKS RUN:H,CHOGYS RUN"
,"CHOGYS RUN:M,EASY RUN,MEDIUM RUN,HARD RUN"
,"EASY RUN:E"
,"MEDIUM RUN:M"
,"HARD RUN:H"}

"DOKS RUN"

Returns: "BLACK DIAMOND"

Since DOKS RUN itself is hard, it doesn't matter how hard the runs below it are.

{"BLACK STALLION:M,BLUE MOUNTAIN,TOPCODER,DOKS RUN"
,"BLUE MOUNTAIN:H"
,"TOPCODER:H"
,"DOKS RUN:H,CHOGYS RUN"
,"CHOGYS RUN:M,EASY RUN,MEDIUM RUN,HARD RUN"
,"EASY RUN:E"
,"MEDIUM RUN:M"
,"HARD RUN:H"}

"CHOGYS RUN"

Returns: "BLUE SQUARE"

CHOGYS RUN is a medium difficulty. Since the easiest path from CHOGYS RUN to the base of the mountain is CHOGYS RUN->EASY RUN, and a medium difficulty is the hardest run in the path, CHOGYS RUN is classified as "BLUE SQUARE".

{"NOOB CITY:E,GREEN BARON,RISKY RUN,LEAP OF FAITH"
,"GREEN BARON:E"
,"RISKY RUN:M"
,"LEAP OF FAITH:H"}

"NOOB CITY"

Returns: "GREEN CIRCLE"

The easiest path is NOOB CITY->GREEN BARON, both of which are easy.

{"NOOB CITY:E,RISKY RUN,LEAP OF FAITH"
,"RISKY RUN:M"
,"LEAP OF FAITH:H"}

"NOOB CITY"

Returns: "BLUE SQUARE"

The easiest path is NOOB CITY->RISKY RUN, and RISKY RUN is a medium difficulty.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4345&pm=590

Writer:

chogyonim

Testers:

alexcchan , lbackstrom

Problem categories:

Graph Theory, String Manipulation