Statistics

Problem Statement for "TheStringGame"

Problem Statement

John and Brus are playing a game where they alternate moves and John goes first. Initially, there is a string that contains only uppercase letters 'X', 'O' and 'L'. A move consists of replacing a single occurrence of 'X' with either 'O' or 'L'. After a player moves, if "LOL" (quotes for clarity) appears as a substring, that player immediately wins and the game ends. Otherwise, the game continues until there are no more 'X's left.

Both players use an optimal game strategy. If a player can win, he will follow the strategy that minimizes the number of moves in the game. Otherwise, if a player can make the game end without a winner, he will follow the strategy that does so (note that in this case the total number of moves in the game does not depend on the chosen strategy). Otherwise, if a player cannot win and cannot end the game in a draw, he will follow the strategy that maximizes the number of moves in the game.

You are given a String s containing the initial state of the game. If the game will end without a winner, return "Draw". If John will win the game, return "John x", and if Brus will win the game, return "Brus x", where x is the number of moves in the game, with no leading zeroes (all quotes for clarity).

Definition

Class:
TheStringGame
Method:
winner
Parameters:
String
Returns:
String
Method signature:
String winner(String s)
(be sure your method is public)

Constraints

  • s will contain between 1 and 16 characters, inclusive.
  • Each character of s will be 'X', 'O' or 'L'.
  • s will not contain "LOL" as a substring.

Examples

  1. "XXOXXXLXLX"

    Returns: "John 1"

    John can win by changing the 'X' between the two 'L's into a 'O'.

  2. "LXXLXXL"

    Returns: "Brus 2"

    Brus can win this game after John's first move, regardless of what John does.

  3. "LLOOLLOOLLOOLLOO"

    Returns: "Draw"

    No moves available.

  4. "XXXXXXXXXXXXXXXX"

    Returns: "Brus 16"

  5. "L"

    Returns: "Draw"

  6. "O"

    Returns: "Draw"

  7. "XX"

    Returns: "Draw"

  8. "XXX"

    Returns: "Draw"

  9. "XXXX"

    Returns: "Draw"

  10. "XXXXX"

    Returns: "Draw"

  11. "XXXXXX"

    Returns: "Draw"

  12. "XXXXXXX"

    Returns: "John 7"

  13. "XXXXXXXX"

    Returns: "Draw"

  14. "XXXXXXXXX"

    Returns: "John 9"

  15. "XXXXXXXXXX"

    Returns: "Draw"

  16. "XXXXXXXXXXX"

    Returns: "John 11"

  17. "XXXXXXXXXXXX"

    Returns: "Draw"

  18. "XXXXXXXXXXXXX"

    Returns: "John 13"

  19. "XXXXXXXXXXXXXX"

    Returns: "Draw"

  20. "XXXXXXXXXXXXXXX"

    Returns: "John 15"

  21. "X"

    Returns: "Draw"

  22. "LXXXXXXXXXOX"

    Returns: "Draw"

  23. "OXXXXXXXXXLXX"

    Returns: "John 11"

  24. "LXLXLXLXLXLXLXL"

    Returns: "John 1"

  25. "OOOOOOOOOOOOOOOO"

    Returns: "Draw"

  26. "XXOX"

    Returns: "Draw"

  27. "LXXLXXLXXLXXLXXL"

    Returns: "Brus 2"

  28. "LXXXXXL"

    Returns: "John 3"

  29. "OXOXOXXXXXOO"

    Returns: "Draw"

  30. "OOXOOXOOXXOXO"

    Returns: "Draw"

  31. "OXXXOXXO"

    Returns: "Draw"

  32. "OXXOXXOXXOXXOXXO"

    Returns: "Draw"

  33. "LXXXXXXXXXXXXXXL"

    Returns: "Brus 14"

  34. "LXXXOXOXXXL"

    Returns: "John 7"

  35. "LXLXLXXXXXLLLLLX"

    Returns: "John 1"

  36. "LXLLXXLXLX"

    Returns: "John 1"

  37. "XXXLXXLLLLXXLL"

    Returns: "John 3"

  38. "XLXLXXXXLXX"

    Returns: "John 1"

  39. "LXXXXXXXXXLXXLXX"

    Returns: "John 11"

  40. "XXXXXXLXXXXXXXX"

    Returns: "Brus 14"

  41. "XXLLLXXXXLXLXLX"

    Returns: "John 1"

  42. "XXXXXXXXXXXXXXLL"

    Returns: "Brus 14"

  43. "XXXXXLXXLXXLLXX"

    Returns: "John 7"

  44. "XXXXXXXOOXXXXXXX"

    Returns: "Brus 14"

  45. "LXXXXXXXXXXXXXXX"

    Returns: "John 13"

  46. "XXLXXXXXXXXXXXXX"

    Returns: "John 15"

  47. "XXXXXXXXLXXXXXXX"

    Returns: "John 13"

  48. "LXXXXXXXOXXXXXXL"

    Returns: "John 11"

  49. "XXXXXXXXLXXXXXX"

    Returns: "Brus 14"

  50. "XXXXXXXXXXXXXXXL"

    Returns: "John 13"

  51. "XXXXXXXXXXXXXXXO"

    Returns: "John 15"

  52. "XXOXXXXLXXXLXXXX"

    Returns: "John 11"

  53. "XXXXXXXLXXXXXXXX"

    Returns: "John 13"

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: