TopCoder problem "RobotRace" used in SRM 263 (Division I Level Three)



Problem Statement

    

RobotRace is the name of a popular game played by one or more engineers for fabulous cash prizes. Before the game begins, each engineer is shown a map of the rectangular game board. Each cell on the board is either empty, an obstacle, the starting position for a robot, or the location of a token. Each engineer must program his robot to navigate the game board and collect one of the tokens, which are then redeemable for cash prizes. The game is challenging because tokens may hold different values for different robots, and some might hold no value for one or more robots. Each token can only be collected by a single robot (and each robot can only collect a single token), so each engineer must program his robot carefully to ensure that he takes home as much money as possible.

The official rules for the game of RobotRace are as follows:

  1. Before the game begins, each engineer will be provided with a complete map of the game board, and will be told the redemption value of each token for himself and for all other engineers.
  2. The engineers are given one robot each, identified by a unique lowercase letter. Each engineer then programs a series of commands into his robot, where each command is either "move_forward", "turn_clockwise", "turn_counterclockwise", or "surrender". (The two "turn" commands rotate the robot in place 90 degrees.)
  3. The command "surrender" is considered a complete program; if used, it must be the first and only command in a robot's memory, and the engineer is rewarded with a constant $20 consolation prize.
  4. Once the robots have all been programmed, the game begins. At time t=0, all engineers simultaneously place their robots on their starting positions on the board, oriented in a direction of their choosing (either north, south, east, or west).
  5. The robots all begin their programs simultaneously, taking one second to execute each command in their memory. Robots are disqualified if they walk off the edge of the game board or into a cell that contains an obstacle.
  6. If a robot navigates to a cell with a token (represented by an uppercase letter), the robot must collect that token. That robot can make no further moves, and that token cannot be taken by any other robot. If any robot attempts to enter a cell with a token that has already been obtained, it becomes disqualified.
  7. Each cell of the board is big enough to allow any number of robots to occupy it at the same time. However, any cells with a token can only be occupied by one robot. If a token has already been taken by a robot, no other robot can occupy or walk through its cell. If two robots attempt to enter the same token cell during the same turn, the robot whose identifying letter is earlier in the alphabet obtains the token, while the other robot becomes disqualified.
  8. The game ends after all robots finish executing their preprogrammed commands. (Robots have a finite amount of memory, and it is impossible to program a loop, so every robot's program is guaranteed to eventually terminate.)

Since they only have one chance to program their robots, all engineers play the game perfectly to maximize their personal winnings. They all know how much each token is worth to themselves and to everyone else, and they know that every engineer has programmed his robot optimally to either surrender or to obtain the best possible prize for himself. As a result, each engineer is able to deduce how much money everyone will win, before the game even begins.

You will be given a String[] board. Each character in board will represent a single cell on the game board. A space (' ') represents an empty cell, an asterisk ('*') represents an obstacle, a lowercase letter represents the starting position of the robot identified by that letter, and an uppercase letter represents the location of a token. You will also be given a String[] tokenValues. Each element of tokenValues corresponds to the token redemption values for one robot, and is formatted as "<robot>:<tokens>", where <robot> is a lowercase letter, and <tokens> consists of one or more unique uppercase letters. The first token in a robot's list can be redeemed for $100 if obtained by that robot. Each successive token in the list can be redeemed for $1 less than the previous token. If a token does not appear in a robot's list, that token cannot be redeemed for a cash prize by that robot's engineer.

Your program should return a String[] that contains the cash prize that each engineer will be awarded after one game of RobotRace. Each element should be formatted as "<robot> <prize>", where <robot> is a lowercase letter and <prize> is an integer with no leading zeroes. The output should be sorted in alphabetical order by robot.

 

Definition

    
Class:RobotRace
Method:getPrizes
Parameters:String[], String[]
Returns:String[]
Method signature:String[] getPrizes(String[] board, String[] tokenValues)
(be sure your method is public)
    
 

Notes

-The results of a game of RobotRace will never be surprising to the engineers. No robot will ever be disqualified during a game, and every engineer will always take home at least $20.
 

Constraints

-board will contain between 1 and 50 elements, inclusive.
-Each element of board will contain between 1 and 50 characters, inclusive.
-Each element of board will contain the same amount of characters.
-Each character in board will be either an uppercase letter ('A' - 'Z'), lowercase letter ('a' - 'z'), asterisk ('*'), or space (' ').
-board will contain at least one uppercase and one lowercase letter.
-No uppercase or lowercase letter will appear more than once in board.
-tokenValues will contain between 1 and 26 elements, inclusive.
-tokenValues will contain exactly one element for each lowercase letter in board.
-Each element of tokenValues will contain between 3 and 28 characters, inclusive.
-Each element of tokenValues will be formatted as "<robot>:<tokens>", where <robot> is a lowercase letter and <tokens> is a nonempty string consisting of unique uppercase letters.
-Each uppercase and lowercase letter in tokenValues will also appear in board.
 

Examples

0)
    
{"b C"
,"a D"}
{"a:CD", "b:DC"}
Returns: {"a 100", "b 100" }
Each robot is programmed to move forward, turn to face east, and move forward two more times. Robot "a" is placed on the board facing north, and robot "b" is placed facing south. They both collect the highest-valued token on their list after four seconds.
1)
    
{"b Cx"
,"a D "}
{"a:CD", "b:DC", "x:C"}
Returns: {"a 99", "b 20", "x 100" }
Robot "x" starts right next to token "C" facing west, and moves forward for one second before collecting it for $100. Robot "a" starts the game facing east, and moves forward twice to obtain token "D" for $99, since he would have been disqualified if he had tried to pick up token "C". The engineer who programmed robot "b" knew that he wouldn't be able to reach either token in time, and instead programmed the robot to surrender.
2)
    
{"b C x"
,"a D  "}
{"a:CD", "b:DC", "x:C"}
Returns: {"a 99", "b 99", "x 20" }
Now robot "x" is two seconds away from token "C", the only token that holds value to him. Because of this, robot "a" is programmed to collect his $99 token, token "D", after two seconds. Likewise, robot "b" is programmed to collect token "C" for $99 after two seconds. If robot "x" were to attempt to collect token "C", he would be disqualified because robot "b"'s identifying letter appears earlier in the alphabet than "x". Therefore, robot "x" is programmed to surrender.
3)
    
{"w     x"
,"  A*B  "
," H   C "
," * Q * "
," G   D "
,"  F*E  "
,"y     z"}
{"z:Q", "y:Q", "x:Q", "w:Q"}
Returns: {"w 20", "x 20", "y 20", "z 20" }
The only token of value is token "Q", but it is impossible for any robot to obtain it without being disqualified.
4)
    
{"a*  "
," X b"}
{"a:X","b:X"}
Returns: {"a 20", "b 100" }
5)
    
{"  bY a"
,"X c  Z"}
{"a:XYZ"
,"b:XYZ"
,"c:YXZ"}
Returns: {"a 98", "b 99", "c 99" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7997&pm=4778

Writer:

LunaticFringe

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Greedy, Search, Simulation