PROBLEM STATEMENT
In the classic science fiction movie Tron, humanoid computer programs competed
against each other by playing a racing game. Each competitor drives around in
a futuristic bike that erects a wall in its path. Drivers that crash lose the
game. Your program will simulate this game being played.
There will be 4 bikers competing on a X by Y grid where X is the width and Y is
the height. Each biker will start at the middle of their respective wall
heading toward the center of the grid (the grid dimensions are always odd).
Bikers zero, one, two, and three start against the top, right, bottom, and left
walls respectively. They are heading downward, leftward, upward, and rightward
respectively. Each biker can change direction numerous times as the game
progresses. If a biker collides with a boundary, another biker, or the wall
erected by another biker he loses, and all of the walls he built are removed
from the playing field.
XXXXXXXXXXXXXXX
X 0 X |
X X |
X X h
X X e
X3 1X i
X X g
X X h
X X t
X 2 X |
XXXXXXXXXXXXXXX
----width----
In the above picture the width and height are the dimensions of the playing
field, and there is a boundary just outside the playing field.
The movement works as follows. Each second the following events occur in
order:
1)Each biker can turn either left, or right with respect to their direction.
If no turn is made the biker's direction remains the same.
2)Each biker advances one space in the direction he is facing(after event 1 has
occured) and erects a wall in the space he used to reside in.
3)Each biker that shares coordinates with a wall, boundary, or another biker is
removed from the playing field.
4)All walls erected by bikers removed in step 3 are removed.
Multiple bikers crashing simultaneously are all removed. In addition, if a
player shares coordinates with a wall or boundary only the player is removed.
The boundary or wall still remains. Walls are only removed when the player who
created them loses and not when they are crashed into.
Seconds begin at 0 and increment until the game is over. The initial set of
events occur during second 0. Play ends when either 1 or 0 player(s) are left
on the grid at the end of a second(after the events of the second have occurred).
You will be given a list of moves for each player. They lists will be of the
format:
"<option><time>_<option><time>..." (brackets for clarity, '_' denoting one or
more spaces)
<option> can be 'L' or 'R' signifying a left or right turn respectively
<time> an integer between 0 and 1250 inclusive signifies the second during
which the turn occurred
"L12 L0 R19"
Means a left turn will occur at second 12, a left turn will occur at second 0,
and a right turn will occur at second 19.
Create a class TronRacing that contains the method whoWins, which takes an int
width, an int height, and a String[] players, and returns an int describing who
won. Return values of 0, 1, 2, and 3 indicate their respective player won. A
return value of -1 means there was no winner (remaining competitors crashed
simultaneously).
DEFINITION
Class: TronRacing
Method: whoWins
Parameters: int, int, String[]
Returns: int
Method signature (be sure your method is public): int whoWins(int width, int
height, String[] players);
NOTES
- The elements of players need not be sorted by time.
- The elements of players may contain values for options that occur after that
player dies.
- Entries in players only correspond to Left and Right turns. The choice to
not turn is the default.
- If a player collides with a wall the same second the wall is removed he loses
- A player does lose if he crashes into his own wall. At the end of that
second when walls are removed, his walls are then removed.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- The elements of the players will be of the form (brackets are for clarity):
<option><time>_<option><time>_<option><time> ... where '_' denotes one or more
spaces
- <option> is either L or R denoting left or right turn respectively
- <time> is an int between 0 and 1250 inclusive with no leading zeros denoting
the second during which the corresponding <option> occurs
- Each element of players will have no leading or trailing whitespace
- players will contain exactly 4 elements
- The elements of players will have length between 1 and 50 inclusive
- width is odd
- height is odd
- width is between 3 and 49 inclusive
- height is between 3 and 49 inclusive
- Each element of players will contain no repeated <time> values
EXAMPLES
'.' denotes empty space
A, B, C, D denote players 0, 1, 2, and 3 respectively
a, b, c, d (lowercase) denote the walls of players 0, 1, 2, and 3 respectively
Coordinates will be of the form <row,column> where row and column are 0-based
and start in the upper left hand corner. Row grows downward and column grows
to the right.
Pictures are an illustration of what the grid should look like
1) width = 9, height = 9, players = {"R100","R100","R100","R100"}
Before the race begins: After second 0:
....A.... ....a....
......... ....A....
......... .........
......... .........
D.......B dD.....Bb
......... .........
......... .........
......... ....C....
....C.... ....c....
After second 2: After second 3:
....a.... .........
....a.... .........
....a.... .........
....A.... .........
dddD.Bbbb .........
....C.... .........
....c.... .........
....c.... .........
....c.... .........
The bikers start at the middle of their respective walls. Player 0 is at <0,4>,
player 1 is at <4,8>, player 2 is at <8,4> and player 3 is at <4,0>. As can be
seen from the pictures the racers all head toward each other, crash, and lose
so the nobody wins. (Note that all of the bikers would turn right on second
100, but since they crash first, we don't have to worry about it).
Method returns -1.
2) width = 9, height = 3, players = {"L9 R7","R100","L94","R16"}
Before the race begins: After second 0:
....A.... .........
D.......B dD.....Bb
....C.... .........
After second 2: After second 3:
......... .........
dddD.Bbbb .........
......... .........
As can be seen from the pictures the racers all head toward each other.
Players 0 and 2 crash early on, whereas players 1 and 3 crash later. The value
in each element of players are all too high time-wise to affect play. Nobody
won the game.
Method returns -1.
3) width = 9, height = 3, players = {"R0","R100","R100","R0"}
Before the race begins: After second 0:
....A.... ...Aa....
D.......B d...C..Bb
....C.... D...c....
After second 1: After second 3:
..Aaa.... Aaaaa....
......Bbb ....Bbbbb
......... .........
As can be seen from the pictures racers 0 and 3 changed directions early.
Player 3 ended up running into the boundary whereas player 2 ran into player
0's wall. After second 4, player 0 will have run into the boundary thus giving
player 1 the win.
Method returns 1.
4) width = 11, height = 7, players = {"R2 L1 R0","R3 R4","L2 L4","R1000"}
Method returns 1.
5) width = 49, height = 49, players = {"R0 R1 R2","R0 R1 R2","R0 R1
R2","R1000"}
Method returns 3.
6) width = 3, height = 3, players = {"R0","L0","R1000","L0"}
Method returns 2.