Statistics

Problem Statement for "GameOfTokens"

Problem Statement

Alice and Bob are playing a game called "Game of Tokens". The game is played on a 1 by n board. Each cell of the board can contain at most one token at any time. There are two types of tokens: 'A' tokens and 'B' tokens. A board state can therefore be described by a string of length n consisting of the characters 'A', 'B', and '.', with the period denoting an empty cell.

The rules of the game are as follows:
  • The players take alternating turns. Alice plays first.
  • When it is Alice's turn, she must choose one of the 'A' tokens and move it one cell to the left. Note that the destination cell must be empty.
  • When it is Bob's turn, he must choose one of the 'B' tokens and move it one cell to the left. Note that the destination cell must be empty.
  • The first player who is unable to make a valid move loses the game.
You are given a String pattern with n characters. Each character in pattern is one of 'A', 'B', '.', and '?', with the question mark denoting a wildcard. We say that a board matches the pattern given in pattern if it can be obtained from pattern by replacing each question mark by one of the other three characters. (Hence, if pattern contains k question marks, there are exactly 3^k boards that match the pattern.)

Among all boards that match pattern, let X be the number of boards for which Alice has a winning strategy. Compute and return the value X modulo (10^9 + 7).

Definition

Class:
GameOfTokens
Method:
count
Parameters:
String
Returns:
int
Method signature:
int count(String pattern)
(be sure your method is public)

Constraints

  • pattern will contain between 1 and 50 characters, inclusive.
  • Each character in pattern will be one of {'.', 'A', 'B', '?'}.

Examples

  1. ".AB"

    Returns: 0

    Obviously, the only board that matches the given pattern is ".AB" itself. For this board there is only one way for the game to play out: Alice must move the only A token to the left. The board becomes "A.B". Bob must move the only B token to the left. The board becomes "AB.". Alice cannot make a valid move, so she loses the game. Thus, the board ".AB" is a losing position for Alice.

  2. "???B"

    Returns: 1

    Among all 27 boards that match pattern, the only board that is a winning position for Alice is ".AAB".

  3. "???????...BBB"

    Returns: 0

  4. "?.A?.B??.??B?"

    Returns: 517

  5. "????????????????????"

    Returns: 612621096

    Don't forget mod.

  6. "..A..A..AAAAA.AAA?.A...A.AAAAA.?BA.A.AAAA.A"

    Returns: 9

  7. "?BBB"

    Returns: 0

  8. "??AAAA??AA?AAAAA?"

    Returns: 579

  9. "BBBBB.BBBBBB"

    Returns: 0

  10. "?A??AABAAA"

    Returns: 16

  11. "BAA.AABBABAABBABABABBAAA.ABBBBABBBBA"

    Returns: 1

  12. ".A............A.AAAA?B?...."

    Returns: 9

  13. "..............B.................AB......."

    Returns: 0

  14. "AAA?AA??A?AAAA"

    Returns: 61

  15. "BB.BBB.BBB.BB..BBBBBB.BB.BBBB."

    Returns: 0

  16. "AAA...AAAAAAAAA.AAAA..A.AAAA.AAA.A.AAA"

    Returns: 1

  17. "..."

    Returns: 0

  18. "AAAAAABAABAAAAA.AA.AAAAABAABAAAABBAAAAAAAAA"

    Returns: 1

  19. ".BB?.BB.BB.?.BBBBBBB.BBB"

    Returns: 0

  20. ".......?...?B?....."

    Returns: 6

  21. "AAB?A?A.BBAAA.AAAAA?.AA.AAAA..AAAA.AAAA.ABAA"

    Returns: 27

  22. "???????B???????B??.?????????????"

    Returns: 894098465

  23. "?????????"

    Returns: 7798

  24. "......"

    Returns: 0

  25. "???A??????AB????????????A"

    Returns: 94404183

  26. "..B.BB?B??.?BB.?BBB..BB.B?B??.???B??BB?..BB?B.."

    Returns: 0

  27. "....."

    Returns: 0

  28. ".AAAAAAAAAABA.A?AA?AAAA.AAAAAAAA?AA.A?AAA"

    Returns: 81

  29. "B..BB.B..BA"

    Returns: 0

  30. ".BBBBBBBBA...BBBBBBBB.B.B"

    Returns: 0

  31. ".B?BBBB.BBBBBBBBBBBBBB.BBBBBBBBAB"

    Returns: 0

  32. "....B.....BB.?"

    Returns: 0

  33. "..A...A.............?..?........B.A.."

    Returns: 6

  34. "??AA?A?BBA?AA?AA.??.?A???A?A??.??A.AB.?.??.??A??B"

    Returns: 913279485

  35. "?.???.?????"

    Returns: 8967

  36. "?BBB??BBB?.?BABAB......BB??.A.?BB??BBB?....?..B."

    Returns: 0

  37. "BBBBBBBB"

    Returns: 0

  38. "AA.....A..AAAAAAA......"

    Returns: 1

  39. "?"

    Returns: 0

  40. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 0

  41. ".B??..???.B...."

    Returns: 32

  42. ".B..B.BBBBA.B.A.BB."

    Returns: 0

  43. "?..?.??B??..BB..?B.B?B???.???..?"

    Returns: 379717

  44. "AAAAAAAAA"

    Returns: 0

  45. "......................?.A?......AA...?...."

    Returns: 27

  46. "................................."

    Returns: 0

  47. "..AAB...B.BA.ABBABAAAA..AA...BA.BB.A."

    Returns: 0

  48. ".........?"

    Returns: 1

  49. "?AAAAAA?AA?AA?A"

    Returns: 65

  50. "...?...B."

    Returns: 0

  51. "B...BB.BABABAA.BAB..BBB..AB"

    Returns: 0

  52. "?????????????????????????????????A.??"

    Returns: 29270351

  53. ".BBAB..BB.B.BBB.B.BB.BA.BBBB....B.....BB.BB.B"

    Returns: 0

  54. ".AAAA?AAAA.AAAAAAAAA.A?.AAAAAABAAA.AAABAABAAAAAA"

    Returns: 9

  55. "..................B......"

    Returns: 0

  56. "BBBBBBBBBBBBBBBBBABBBBBBBBABBBABABBBBBBBB"

    Returns: 0

  57. "BB?BBBBBBBB?BBBBBBB?BBBBBBB?BB?BBBB?BB"

    Returns: 0

  58. "AAA....AA..AA.ABAA.A.A.AA..?A..AA"

    Returns: 3

  59. "B??????????A?????????????????"

    Returns: 621755428

  60. "BABBABBABBBBBBBBBBBBBBBBBBBBBABBABBBBBBBBBBBB"

    Returns: 0

  61. "AAAAAAAAAAABAABAAAAAAABA.AAAAAABAAABAAAAA.A"

    Returns: 1

  62. "AAAAAAAAAAAAAAA?A?AAAAAAAAAAAAAA?AAAAAA?AAAAA"

    Returns: 65

  63. "BAAAA"

    Returns: 0

  64. "BBBBBB"

    Returns: 0

  65. "A.A.AA"

    Returns: 1

  66. ".?A"

    Returns: 2

  67. "..A"

    Returns: 1

  68. "?B?BBBBBBBBBBBBBBBBBBBBBBBB?BBBBBBBBB"

    Returns: 0

  69. ".B.B.A.B.B.B..BB.BBA....B...BB..B.A.BB.."

    Returns: 0

  70. "..........................................."

    Returns: 0

  71. "?B???????.???B?.?????????"

    Returns: 757039369

  72. "AAAAAAAA"

    Returns: 0

  73. "BBAABBB?AABAAAABABB?AAAB.BBB"

    Returns: 1

  74. "??????A??.A?"

    Returns: 15364

  75. "?AB?BB?AAAABAB???B?A?AAAAA.ABAA"

    Returns: 5364

  76. ".BBBBA.BBBBABBBB?BB.BBBBBBBBBBB?BBBB?B"

    Returns: 0

  77. "..??...?AAB??A..??.?A?A.?????"

    Returns: 4254175

  78. "???.?A"

    Returns: 59

  79. "???A???.???.?????"

    Returns: 2499903

  80. ".AAA..A.A....AA.AA....A..........A......"

    Returns: 1

  81. "?AAAA??AAA??B??AA????AAAA?AAAAA??A?AAA?A????"

    Returns: 379493907

  82. "..A.?.B..BB..??B?..?.?...?B...B?B.?..BBBB"

    Returns: 0

  83. "?..??????A??.??A.???A????AA.??.??????A."

    Returns: 961008300

  84. "AABB?AAB??AAA.BAABBAA?.?BAABA"

    Returns: 172

  85. "BBBB.BB?BB.BBBBBBBBBA????B?B.?BBB?BBBBB"

    Returns: 0

  86. "???.???????????????????????????"

    Returns: 454215925

  87. "A.B.?..B..?...A...A...B.A.....?A...A"

    Returns: 27

  88. "."

    Returns: 0

  89. "AAABA?AABAAAAAAAAAAAAAAABAAAAAABBAAAAAA"

    Returns: 1

  90. "B....A"

    Returns: 1

  91. "..B."

    Returns: 0

  92. "...??.......B..B?.......?..?...."

    Returns: 31

  93. "BBBBBBBBBBBBBB"

    Returns: 0

  94. "..?.A........A.A..A"

    Returns: 3

  95. "B?????BB?.B????????????B?B???B.??B?B?????B.?"

    Returns: 183867584

  96. "?.....B.?.....B....B.B...B....B..."

    Returns: 0

  97. "???BBBBB.BBB"

    Returns: 0

  98. "BAAA.AABBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: 1

  99. "AB...A......B.BB.B.B.A.B..BA.A"

    Returns: 0

  100. "?B?ABAA..BAAAAAAAA?AAB?A"

    Returns: 54

  101. "ABBAABAAABBBAABAAB.AABB.BBABBBBAABBBAAABAA.B"

    Returns: 0

  102. ".????.?BB??.??"

    Returns: 3914

  103. "AB???A???????B?A?BBB?A?AAA?????AAA?????ABA?AA?A?"

    Returns: 405567502

  104. "BBBBBAAABAABABA.ABAAAAA.AAABA"

    Returns: 1

  105. "...B?.B.AB..A"

    Returns: 1

  106. "??????????????????????????????????????????????????"

    Returns: 933631340

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: