PROBLEM STATEMENT
Mankala is an old African game with many variations. In this particular
variation there are twelve "play pits", and two "home pits". The game is
started by placing an equal number of pieces in each of the play pits. The
object of the game is to get as many pieces as you can into your home pit.
Consider the diagram below:
****************************************************
* ** ** ** ** ** ** *
* *** *11* *10* * 9* * 8* * 7* * 6* *** *
* *hom* ** ** ** ** ** ** *hom* *
* *pit* *pit* *
* * 2 * ** ** ** ** ** ** * 1 * *
* *** * 0* * 1* * 2* * 3* * 4* * 5* *** *
* ** ** ** ** ** ** *
****************************************************
You are player 1, the rules are as follows:
(a) Your play pits are those labeled 0, 1, 2, 3, 4, and 5.
(b) You start your turn by selecting one of your non-empty play pits, (one
which has at least one piece).
(c) If all your play pits are empty, you cannot go, so it's your opponents turn.
(d) Once you select a play pit, you pick up all pieces from that pit and do as
follows:
(i) In a counter-clockwise direction, place one piece in every pit you
pass, including your home pit (home pit 1), and excluding your opponents home
pit (home pit 2). Note, you start at the first pit after the one you selected.
Do this until you run out of pieces. For example, if there were 15 pieces in
pit #1 then you would play the 15 pieces in this order: 2 -> 3 -> 4 -> 5 ->
home pit 1 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 0 -> 1 -> 2 (where the pits as
numbered as in the above diagram).
(ii) If the last piece you placed was placed in a non-empty play pit
(even if this pit is on your opponents side), pick up the pieces in that play
pit and continue the turn as before.
(iii) If the last piece you placed was placed in your home pit (home pit
1), you get to go again. You must select a non-empty play pit on your side.
If all your play pits are empty, your turn is over, and your opponent goes.
(iv) If the last piece you placed was placed in an empty pit, your turn
is over, and your opponent goes.
(e) The game ends when all the pieces are in home pits - i.e. all of both
players' play pits are empty.
Given a representation of the current state of the board, you are to write a
method, greedyMove, which returns the maximum number of pieces you can place in
your home pit before your turn is over. Note that this is not necessarily your
best move (for example it may be to your advantage to put less pieces in your
home pit, if it will help you later on).
DEFINITION
Class: Mankala
Method name: greedyMove
Parameters: int[], int[]
Return type: int
Method signature (be sure your method is public): int greedyMove (int[]
player1, int[] player2);
NOTES
- player1 represents the number of pieces in each of your pits (0 through 5).
player2 represents the number of pieces in each of your opponents pits (6
through 11). For player1, index 0 represents play pit 0, index 1 represents
play pit 1, etc. For player2, index 0 represents play pit 6, index 1
represents play pit 7, etc.
TopCoder will ensure that:
- There are no more than 30 total pieces on the board.
- Each element of player1 and player2 will be between 0 and 30 (inclusive).
- player1 and player2 each have 6 elements.
- Each element of player1 and player2 is non-negative.
EXAMPLES
1. If player1 = {0,0,0,0,0,1} and player2 = {2,3,4,5,6,7},
You only have one non-empty play pit on your side. You play it, and it lands
in your home pit. However now all your play pits are empty so your turn is
over. Return 1.
2. If player1 = {1,0,1,0,2,1} and player2 = {0,5,5,5,5,5},
If you play pit 0 or pit 2 you get nowhere.
(a) Your best strategy is to play pit 5, getting one piece in your home pit
and allowing you to go again. You now have 1 piece in your home pit and player1
= {1,0,1,0,2,0} and player2 = {0,5,5,5,5,5}.
(b) Next you play pit 4, placing one piece in pit 5 and one in your home pit.
You now have 2 pieces in your home pit and player1 = {1,0,1,0,0,1} and player2
= {0,5,5,5,5,5}.
(c) Now you play pit 5 again, placing one piece into your home pit. You now
have 3 pieces in your home pit and player1 = {1,0,1,0,0,0} and player2 =
{0,5,5,5,5,5}.
(d) Finally, you may choose either pit 2 or pit 4, but neither gets another
piece into your home pit. Return 3.
3. If player1 = {0,2,0,0,1,6} and player2 = {0,0,0,0,5,0},
(a) Clearly, your best move is to move pit 5 because its the only one where
you'd get more than one piece into your home pit. After moving it, you get one
piece into your home pit, and your last piece lands in pit 10, which is
non-empty, so you continue. Now you have 1 point and player1 = {0,2,0,0,1,0}
and player2 = {1,1,1,1,6,0} and you have to play the pieces in pit 10.
(b) After playing the pieces in pit 10 (skipping over his home pit), you land
in pit 4. You still have one point, and player1 = {1,3,1,1,2,0} and player2 =
{1,1,1,1,0,1} and you have to play the pieces in pit 4.
(c) After playing this pit, you place one piece in pit 5 and one in your home
pit. You now have 2 points and player1 = {1,3,1,1,0,1} and player2 =
{1,1,1,1,0,1}.
(d) Now choosing either pit 0, pit 2, or pit 5 will result in one more point
for you. You can't do better than that. For example, if you play pit 2, the
resulting board will be player1 = {1,3,0,0,1,0} and player2 = {0,2,0,2,1,1},
with 3 pieces in your home pit. Return 3.
4. If player1 = {0,0,0,0,0,0} and player2 = {0,0,0,0,5,0},
You have no legal moves (all your pits are empty), so you do not get to go.
Return 0.