LightbulbGame | Topcoder Archive

Problem Statement

Yvonne and Zed have a rectangular array of lightbulbs. Each lightbulb is either on or off. You are given the String[] board that describes their current states: '1' represents on, '0' off.

Yvonne and Zed use the array to play a game. They take alternating turns, Yvonne starts. In each turn the active player does the following:

The player must choose a lightbulb L that is currently on. If the player cannot do that, they lose the game.
The player must turn lightbulb L off.
The player then may choose another lightbulb L'. This lightbulb must be either somewhere to the right of L (in the same row) or somewhere downwards from L (in the same column).
If the player did choose L', they now must toggle it. (Turn it on if it was off, or vice versa.)

For the given board, count all winning moves for the player whose turn it is.

Definition

Class:: LightbulbGame
Method:: countWinningMoves
Parameters:: String[]
Returns:: int
Method signature:: int countWinningMoves(String[] board)
(be sure your method is public)

Constraints

board will contain between 1 and 50 elements, inclusive.
Each element of board will contain between 1 and 50 characters, inclusive.
All elements of board will have the same length.
Each character in board will be either '1' or '0'.

Examples

```
{"000",
 "000",
 "000"}
```
```
Returns: 0
```
All lightbulbs are off. The player immediately loses the game.
```
{"0000",
 "0100",
 "0000"}
```
```
Returns: 1
```
A single lightbulb is on. The only winning move is to turn it off and to refuse to toggle another lightbulb.
```
{"00000",
 "01001",
 "00000"}
```
```
Returns: 1
```
Two lightbulbs are on. As they are in the same row, the current player can win by choosing the lightbulb at row 1, column 1 (using 0-based indices) as L and then the other lightbulb as the L' to toggle. It can be shown that there are no other winning moves from this situation.
```
{"10",
 "01"}
```
```
Returns: 0
```
Two lightbulbs are currently on and two are off. We can work out all possible ways this game can play out to see that if the opponent plays optimally, the current player will lose regardless of the first move they make.
```
{"1111",
 "1110"}
```
```
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.