Statistics

Problem Statement for "TheXGame"

Problem Statement

The X game is a two person game. The board is just a sequence of boxes, some of which are randomly marked with an X before the game begins. The two players alternate turns. On each turn the player whose turn it is marks 1 or more previously unmarked boxes. All her marks on the turn must be adjacent (with no wrap-around at the ends) to each other. The game continues until all the boxes are marked.

The number of points scored by a player on his turn is equal to the number of boxes he marked on that turn times a multiplier. The multiplier gets bigger and bigger as the game goes on:

  • first turn Player 1 multiplier=0
  • second turn Player 2 multiplier=1
  • third turn Player 1 multiplier=2
  • fourth turn Player 2 multiplier=4
  • fifth turn Player 1 multiplier=8
  • ... etc.
A players wins the game if the sum of the points scored on all her turns is strictly greater than her opponent's sum. Create a class TheXGame that contains a method firstMove that is given a String board indicating how many boxes there are, and which ones are marked with X before the game begins. The method returns the smallest number of Xs that the first player can mark on her first turn (somewhere on the board) that will allow her to win the game if she plays optimally thereafter. If no first move puts the first player into a winning position, the method returns -1.

Definition

Class:
TheXGame
Method:
firstMove
Parameters:
String
Returns:
int
Method signature:
int firstMove(String board)
(be sure your method is public)

Constraints

  • board will contain between 1 and 50 characters, inclusive.
  • Each character in board will be 'X' or '-'.
  • board will contain at least one '-'.

Examples

  1. "X---X-X-"

    Returns: 1

    There are 8 boxes, 3 of them marked with X before the game begins. The first player can win by marking the third box. After that each player will only be able to mark one box one each turn, and the scoring will be: P1: 0*1; P2: 1*1; P1: 2*1; P2: 4*1; P1: 8*1 and player 1 wins with a score of 10 versus player 2's score of 5.

  2. "----"

    Returns: 2

    The first player can win by marking the middle two spaces. After that, each player will mark one on each turn so player 1 wins by a score of 2 to 1. If the first player just marked one of the middle spaces, then the second player would mark 2 and the first player would mark 1 leaving the game tied (2 to 2).

  3. "--XXX"

    Returns: -1

    The first player cannot win by marking both of them, since her first turn multiplier is 0!

  4. "--------X-----X----X"

    Returns: 3

  5. "X-----X-------X---------X-----------"

    Returns: -1

  6. "--------------------------------------------------"

    Returns: 2

  7. "----X-----X----"

    Returns: 1

  8. "----XXX------XX--XXX"

    Returns: -1

  9. "-----XXX------XX--XXX"

    Returns: 1

  10. "---X----X-X-X-------X--------X"

    Returns: 2

  11. "-----X-X------------------------------X----------X"

    Returns: 14

  12. "-----X-X---------------------X----------X"

    Returns: 5

  13. "XXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXX-XXXXXXX"

    Returns: 2

  14. "--XXX--XX----X------------------------------"

    Returns: 4

  15. "--XXX--XX----X-----------------------------"

    Returns: 3

  16. "--XXX---XX----X------------------------------"

    Returns: 5

  17. "---------X--------X-----X-X-----------------------"

    Returns: 2

  18. "--XX---X---X----X------XX---X---X----X--"

    Returns: 2

  19. "--------X-X----------------X-X--X----X-----X-----"

    Returns: 2

  20. "--------------------------------------------------"

    Returns: 2

  21. "-----X---X----XXX---"

    Returns: 1

  22. "--------X-----X----X------------------------------"

    Returns: 9

  23. "-X--X----X-------"

    Returns: -1

  24. "--X----X---"

    Returns: 3

  25. "--XX---X---X----X------XX---X---X----X--"

    Returns: 2

  26. "--------X-X----------------X-X--X----X-----X-----"

    Returns: 2

  27. "--------------------------------------------------"

    Returns: 2

  28. "-----X---X----XXX---"

    Returns: 1

  29. "--------X-----X----X------------------------------"

    Returns: 9

  30. "-X--X----X-------"

    Returns: -1

  31. "--X----X---"

    Returns: 3

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: