PROBLEM STATEMENT
Checkers is a board game played with two players on an 8 by 8 board. Player 1
is represented by red game pieces and player 2 is represented by black game
pieces.
There are two types of moves for a game piece - a simple move and a jump. Both
moves are diagonal, and can be performed by pieces of both colors in all four
diagonal directions. *This is different from the real game of checkers, where
only 'king' pieces move in all four directions.*
A simple move involves moving a game piece diagonally 1 square. The diagram
below shows four ways to perform a simple move. 'B' denotes a black piece. '*'
denotes four possible endpoints of a simple move. The diagram shows only a
fragment of the board.
-------------
| * | | * |
----+---+----
| | B | |
----+---+----
| * | | * |
-------------
A jumping move involves moving diagonally over *one* of the opponents pieces,
and landing in an empty square immediately after that piece. See the following
diagram. 'R' denotes a red piece. 'B' denotes a black piece. '*' denotes four
possible endpoints of a jump. The diagram shows only a fragment of the board.
---------------------
| * | | | | * |
----+---+---+---+----
| | R | | R | |
----+---+---+---+----
| | | B | | |
----+---+---+---+----
| | R | | R | |
----+---+---+---+----
| * | | | | * |
---------------------
A piece over which you jumped is considered captured, and is removed from the
board.
Jumping moves take precedence over simple moves: if a side can make a jumping
move, all non-jumping moves become invalid.
Implement a class CheckersPos that contains a method moveCount. Given a
checkers position, moveCount would calculate the number of ways for red and
black sides to make a valid move.
DEFINITION
Class name: CheckersPos
Method name: moveCount
Parameters: int[], int[]
Return type: int[]
Method signature: int[] moveCount(int[] black, int[] red) (make sure your
method is public)
The 32 squares of the checkers board on which game pieces can be located are
numbered 1 through 32 (see the diagram below).
-------------------------
| |32| |31| |30| |29|
---+--+--+--+--+--+--+---
|28| |27| |26| |25| |
---+--+--+--+--+--+--+---
| |24| |23| |22| |21|
---+--+--+--+--+--+--+---
|20| |19| |18| |17| |
---+--+--+--+--+--+--+---
| |16| |15| |14| |13|
---+--+--+--+--+--+--+---
|12| |11| |10| | 9| |
---+--+--+--+--+--+--+---
| | 8| | 7| | 6| | 5|
---+--+--+--+--+--+--+---
| 4| | 3| | 2| | 1| |
-------------------------
black and red list square numbers occupied by pieces of the corresponding color.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- black will contain at most twelve values in the range from 1 to 32, inclusive.
- red will contain at most twelve values in the range from 1 to 32, inclusive.
- Neither black nor red will list the same value more than once.
- black will not list values used by red; red will not list values used by
black.
Your method should return a int[] of size 2. The first value should represent
the number of valid moves the black side can make; the second value should
represent the number of valid moves the red side can make.
NOTES
* Upon completion of a jumping move, if the piece that jumped can make another
jumping move, the piece must continue jumping until there are no more jumping
opportunities left *for that piece*. The entire chain of jumps is considered a
single move.
* When a side has an opportunity to jump, your method must return the number of
distinct jumping moves that the side can make.
* Sometimes different sequences of jumping moves lead to the same board
position. Your method should count such sequences only once (see examples 3 and
4).
EXAMPLES
1. black={18}, red={4, 8, 11}
For an illustration of the starting board position for example 1, see
http://www.topcoder.com/contest/CheckersPos01.html
Neither black nor red have jumping opportunities; therefore your method should
return {4,5}, because the black side can make four different moves (18-14,
18-15, 18-22, and 18-23), and red can make five different moves (8-3, 8-12,
11-7, 11-15, and 11-16).
2. black={15}, red={4, 8, 11}
For an illustration of the starting board position for example 2, see
http://www.topcoder.com/contest/CheckersPos02.html
The black side does not have jumping opportunities, but the red side can jump
11-18. Your method should return {3,1}.
3. black={14, 15, 22, 23}, red={10}
For an illustration of the starting board position for example 3, see
http://www.topcoder.com/contest/CheckersPos03.html
The black side has two jumping opportunities: 14-7 and 15-6. The red side can
jump clockwise - 10-19, 19-26, 26-17, and 17-10, or counterclockwise - 10-17,
17-26, 26-19, and 19-10. However, both jumping sequences for the reds are
identical, because the ending board position is the same: one red piece at
square 10. Therefore, your method should return {2,1}.
4. black={6, 7, 8, 14, 15, 16, 22, 23, 24}, red={4}
For an illustration of the starting board position for example 4, see
http://www.topcoder.com/contest/CheckersPos04.html
The black side has no jumping opportunities; 8 of the 9 black pieces have all
four simple moves open; one piece has three of the four simple moves open,
therefore the count of moves for the black side is 4*8+3=35.
The red side has numerous jumping opportunities with only four distinct
outcomes. Your method should return {35,4}.