The game of zeros and games (Google interview)

Question

I was asked this question some time ago in my Google interview, and so far I have not been able to find a good answer to it: This is a two-player game where you are given a string of zeros and ones. At each step, the player can select 1 (or the same number of 1 next to each other) and change his / them to 0 / 0s. A player who changes the last 1 (or group 1) to 0/0 is the winner of the game.

For example, starting from 0101110. The first player has 7 possible moves:

• 0 1 01110 → 0 0 01110 (The second player can win)
• 010 1 110 → 010 0 110 (The second player can win)
• 0101 1 10 → 0101 0 10 (The second player can win)
• 01011 1 0 → 01011 0 0 (The second player can win)
• 010 11 10 → 010 00 10 (The first player can win)
• 0101 11 0 → 0101 00 0 (The first player can win)
• 010 111 0 → 010 000 0 (The second player can win)

The goal is to find out if there is a winning strategy if you start over. We assume that both players are good players (this means that they are not mistaken!)

Update: This game is slightly different from Nim ( https://en.wikipedia.org/wiki/Nim ), for Nim the number of piles (or heaps) remains unchanged at every step, whereas here at every step you can change the number of piles. For example, if we do 0101 1 10 → 0101 0 10, initially we have two piles of size 1 and 3, but after moving we will have 3 piles of size 1.

Answer 1

Let nim[n] be the thread of a sequence of n units. Then we have the following recurrence relation:

nim[n] = mex{nim[i] xor nim[j]: i, j >= 0, i + j < n}

(see Sprague-Grundy theorem for a general theory.)

From this repetition relation, you can try to calculate the first few members of the nim sequence, and you will find that it looks like nim[n] = n .

Then the evidence can easily be deduced, which I will leave to you.

---

Thus, a sequence of n consecutive units is actually equivalent to a Nimes heap of size n . Now it’s easy to find the result of any game.

For example, if we have 0101110 , then it is equivalent to two Nim piles of size 1 and 3 respectively. Therefore, the total nimber is 1 xor 3 = 2 , which is nonzero, so the first player wins.

As another example, if we have 1110011111000111111 , then the full nimber is 3 xor 5 xor 6 = 0 , so the first player loses.

---

EDIT: Regarding your question about changing piles, here are some more explanations.

Although the number of piles will change, the key point is as follows:

• If the status is zero, any valid move should change it to a non-zero nimber status.
• If the status has a nonzero nimber, then there must be a valid move that changes it to a zero state.

Thus, for the winner, the strategy is to leave the opponent in a zero state.

Example: start with the sequence 1110011111000111111 , which I denote by 3, 5, 6 for brevity.

If the first player replaces 6 with the sums of 2 and 3 , then the second player will face the status 3, 5, 1, 4 , which has nimber 3 xor 5 xor 2 xor 3 = 7 . To keep the value zero, the second player will replace 5 with 2 , leaving the first player 3, 2, 2, 3 , who again has zero.

The procedure continues until there is a valid movement for the first player.

Answer 2

It can be solved using the graph view.

Vertices would be possible combinations of a given binary string / integer with a binary → decimal conversion.

Each vertex must have an edge associated with vertices whose values ​​can be obtained by transforming 1 → 0 in accordance with the rule of the game.

In this case, 7 bits => 2 ^ 7 = 128 combinations. However, we can filter out vertices that can never be reached from a given source combination.

For instance,

0101110 → 0 0 01110 → 0000000 (The second player wins)

0101110 → 010 0 110 → 0100 00 0 → 0000000 (The first player wins)

It happens like this. In each step, we can identify the next possible combination by obtaining adjacent vertices, and it leads us to the winning combination (0000000)