GameOfTokens | Topcoder Archive

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

```
".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.
```
"???B"
```
```
Returns: 1
```
Among all 27 boards that match pattern, the only board that is a winning position for Alice is ".AAB".
```
"???????...BBB"
```
```
Returns: 0
```
```
"?.A?.B??.??B?"
```
```
Returns: 517
```

"????????????????????"

Returns: 612621096

Don't forget mod.

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.