Problem A
Pebble Solitaire
I bet you have seen a pebble solitaire game. You know the game where you are given a board with an arrangment of small cavities, initially all but one occupied by a pebble each. The aim of the game is to remove as many pebbles as possible from the board. Pebbles disappear from the board as a result of a move. A move is possible if there is a straight line of three adjacent cavities, let us call them $A$, $B$, and $C$, with $B$ in the middle, where $A$ is vacant, but $B$ and $C$ each contain a pebble. The move consists of moving the pebble from $C$ to $A$, and removing the pebble in $B$ from the board. You may continue to make moves until no more moves are possible.
In this problem, we look at a simple variant of this game, namely a board with twelve cavities located along a line. In the beginning of each game, some of the cavities are occupied by pebbles. Your mission is to find a sequence of moves such that as few pebbles as possible are left on the board.
Input
The input begins with a positive integer $n \le 10$ on a line of its own. Thereafter $n$ different games follow. Each game consists of one line of input with exactly twelve characters, describing the twelve cavities of the board in order. Each character is either ‘-’ or ‘o’. A ‘-’ character denotes an empty cavity, whereas an ‘o’ character denotes a cavity with a pebble in it. There is at least one pebble in all games.
Output
For each of the $n$ games in the input, output the minimum number of pebbles left on the board possible to obtain as a result of moves, on a line of its own.
Sample Input 1 | Sample Output 1 |
---|---|
5 ---oo------- -o--o-oo---- -o----ooo--- oooooooooooo oooooooooo-o |
1 2 3 12 1 |