PROBLEM STATEMENT
DandyLand is a board game for one to eight players. Players move around a
circular board collecting a point each time the intersection from the last
board position to the first board position is traversed in a forward direction.
A deck of cards determines movement. Each player in turn selects a card from
the deck and moves to a position on the board according to the movement rules
defined below. Create a method that given a number of players, a card deck, and
a board description, computes the number of points collected by each player.
The board is represented as a string. The first character in the string is the
first board position. The second character in the string is the second board
position, and so on. The character names the board position. The same name can
appear more than once on a board. The last character in the string is the last
board position. From the last position movement continues at the first board
position, thus making the board circular.
1 2 3 4 5 6
off-->-->a-->b-->c-->a-->b-->c-- board "abcabc"
^ |
| v
<-----(earn a point)<-----
For example, given the board definition "abcabc", the first board position is
the first character 'a', the last board position is the second character 'c'.
Forward movement goes from the first 'a' to the first 'b' to the first 'c' to
the second 'a' to the second 'b' to the second 'c' then back again to the first
'a' then to the first 'b' and so on. If a player's turn movement takes a player
from the last board position, the second 'c', to the first position, the first
'a', one point is earned. Once earned, a point cannot be lost. Players
initially begin off of the board and enter the board at the first board
position (the first 'a').
The card deck is represented as a string in which each character is a card.
Each player in turn selects a card and proceeds as follows.
If the card is a letter character (a through i), move forward around the board
until a board position with a matching character is reached. If the board does
not contain a position which matches the character on the card and the player
is currently on the board, the player moves backward one position instead. If
the player is on the first board position, moving backward one position places
the player on the last board position. If the player is currently off of the
board and there is no matching character on the board for the character on the
card, the player simply remains off of the board.
If the card is a digit (1 through 9), the player moves forward the number of
board positions equal to the numeric value of the digit on the card. If the
player begins off of the board, the player enters the board at the first
position which counts as moving one position and continues to move forward
around the board. (see Example E6)
If a player's ending board position after movement is already occupied by
another player, the player previously occupying the position is bumped off of
the board.
The game is over when the end of the card deck is reached, that is, all cards
have been used. The points for each player are returned as an int[], equal in
length to the number of players, with player one's points occupying int[]
position zero, player two's points occupying int[] position one, and so on.
DEFINITION
Class Name: DandyLand
Method Name: play
Parameters: int, String, String
Returns: int[]
Method signature (be sure your method is public): int[] play(int players,
String cards, String board);
TopCoder will ensure the following:
- players is from 1 to 8, inclusive
- cards consists only of the nine letter characters "abcdefghi" and the nine
digit characters "123456789" (double quotes are not included)
- board consists only of the nine letter characters "abcdefghi" (double quotes
are not included)
- cards will contain between 0 and 50 elements inclusive
- board will contain between 1 and 36 elements inclusive
NOTES:
N1: A player is either off of the board or occupies a specific position on the
board. When entering the board from off the board, the first board position
counts as a unit of movement. For example, using the board "abcabc" illustrated
above, a card of '2' places the player moving from off of the board onto 'b',
the second board position.
N2: Keep in mind that a point is earned by moving from the last board position
to the first board position. In particular, should a player move backward from
the first position to the last position, then move forward on a subsequent turn
to or beyond the first position, a point is earned. Should the player then move
backward again to the last square, then move forward on a subsequent turn to or
beyond the first position, another point is earned. See example E2 below.
EXAMPLES
play(2, "abab9abcaa", "abab") ==> [3,1]
There are two players initially off of the board. The board, "abab", has four
positions, two named 'a' and two named 'b'. The game proceeds as follows.
M1: Player one selects the first card, 'a', and moves to the first board
positon named 'a'.
M2: The second player selects card 'b' and moves to the second board position,
the first position named 'b'.
M3: Player one selects 'a' and moves to the second board position named 'a'.
M4: Player two selects 'b' and moves to the second position named 'b' which is
the last board position.
M5: Player one selects '9' and moves forward 9 positions earning two points for
passing from the last board position to the first board position twice and
ending on the last board position (the second 'b'). Since player two currently
occupies the last board position, player two is bumped off of the board.
M6: Player two selects the card 'a' and moves from off of the board to the
first board position named 'a'.
M7: Player one selects 'b' and moves from the last board position past the
first board position ending on the second board position (the first position
named 'b') earning another point.
M8: Player two selects 'c'. Since there is no board position named 'c', player
two moves backward one position. Since player two is currently at the first
board position, player two moves backwards to the last board position (the
second board position named 'b').
M9: Player one selects 'a' and moves to the second board position named 'a'.
M10: Player two selects 'a' and moves from the last board position to the first
board position collecting one point.
The card deck is exhausted and so the final result, three points for player
one, 1 point for player two, is returned.
More Examples
E1: play(1, "7aaa", "abcde") ==> [4]
E2: play(1, "af1f1fa", "abcde") ==> [3]
E3: play(2, "1181a221aeeb1", "abcd") ==> [4,1]
E4: play(4, "9b8b2a11", "ab") ==> [5,0,3,1]
E5: play(8, "d53ab9e7b5decaacd59aeeeb", "abcdabcdabcd") ==> [0,1,1,1,0,1,0,1]
E6: play(1, "4", "abcd") ==> [0]