PROBLEM STATEMENT
The game 'Stones' is played on a String of '.'s and 'X's, such as:
"..X......X..X"
Squares with a stone are represented by 'X', and empty squares are represented
by '.'.
There will be between 0 and 10 stones, inclusive.
Here are the rules to the game:
1. Play alternates between player 1 and player 2.
2. A player must move one stone on their turn.
3. If a player can't move, he/she loses.
4. A valid move consists of moving one stone 'X' one or two squares to the
left.
5. A player can't move a stone off the edge of the board.
6. A player can't move a stone past another stone.
7. A player can't move a stone on top of another stone.
It is player 1's turn. Given the current state of the board as a String, return
how many different winning moves player 1 has on that turn.
A winning move for player 1 is a move such that no matter how player 2 plays,
player 1 can insure (by playing perfectly) that player 2 will run out of moves
before player 1 will. (i.e. player 1 can insure that the last possible move of
the game will be on player 1's turn, winning by rule 3)
Example:
board = ".X.X"
player 1 has two possible (not necessarily winning) moves:
(a) to "X..X" (moving the left X one to the left)
(b) to ".XX." (moving the right X one to the left)
player 1 can't move either X two squares without violating rule 5 or 7.
if player 1 moves to (a), player 2 has two moves:
(a1) to "XX.." (moving the right X two to the left)
(a2) to "X.X." (moving the right X one to the left)
if player 2 plays to (a1), player 1 has no move and so loses. Because player 2
has a winning move, (a) isn't a winning move for player 1.
if player 1 moves to (b) instead, player 2 has only one move:
(b1) to "X.X." (moving the left X one to the left)
This leaves player 1 with only one move, to "XX.."
after the move to "XX..", player 2 has no move and loses, so (b) is a winning
move for player 1.
(a) is not a winning move, and (b) is a winning move, so player 1 has only one
winning move, and the method would return 1.
DEFINITION
Class: SlideGame
Method: waysToWin
Parameters: String
Returns: int
Method signature (be sure your method is public): int waysToWin(String board);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- board will be between 1 and 50 characters, inclusive.
- board will consist only of the characters 'X' and '.'.
- board will contain between 0 and 10 'X's, inclusive.
EXAMPLES
(1)
board: "...X.."
waysToWin would return: 0
(2)
board: "...X..X..X"
waysToWin would return: 3
(3)
board: "...X.X..X"
waysToWin would return: 3
(4)
board: ".X.X..X.X..XX.....X"
waysToWin would return: 3
(5)
board: "..X..X..X..X..X..X..X..X..X..X."
waysToWin would return: 10
(6)
board: "......"
waysToWin would return: 0
(7)
board: "X"
waysToWin would return: 0