Coin flipping game: Optimization problem

Question

There is a rectangular grid of coins, with heads being represented by the value 1 and tails being represented by the value 0. You represent this using a 2D integer array table (between 1 to 10 rows/columns, inclusive).

In each move, you choose any single cell (R, C) in the grid (R-th row, C-th column) and flip the coins in all cells (r, c), where r is between 0 and R, inclusive, and c is between 0 and C, inclusive. Flipping a coin means inverting the value of a cell from zero to one or one to zero.

Return the minimum number of moves required to change all the cells in the grid to tails. This will always be possible.

Examples:

1111  
1111  
returns: 1  

01  
01  
returns: 2   

010101011010000101010101  
returns: 20  

000  
000  
001  
011  
returns: 6  

This is what i tried: Since the order of flipping doesn't matter, and making a move on a coin twice is like not making a move at all, we can just find all distinct combinations of flipping coins, and minimizing the size of good combinations(good meaning those that give all tails).

This can be done by making a set consisting of all coins, each represented by an index.(i.e. if there were 20 coins in all, this set would contain 20 elements, giving them an index 1 to 20). Then make all possible subsets and see which of them give the answer(i.e. if making a move on the coins in the subset gives us all tails). Finally, minimize size of the good combinations.

I don't know if I've been able to express myself too clearly... I'll post a code if you want. Anyway, this method is too time consuming and wasteful, and not possible for no.of coins>20(in my code). How to go about this?

Answer 1

I think a greedy algorithm suffices, with one step per coin.

Every move flips a rectangular subset of the board. Some coins are included in more subsets than others: the coin at (0,0) upper-left is in every subset, and the coin at lower-right is in only one subset, namely the one which includes every coin.

So, choosing the first move is obvious: flip every coin if the lower-right corner must be flipped. Eliminate that possible move.

Now, the lower-right coin's immediate neighbors, left and above, can only potentially be flipped by a single remaining move. So, if that move must be performed, do it. The order of evaluation of the neighbors doesn't matter, since they aren't really alternatives to each other. However, a raster pattern should suffice.

Repeat until finished.

Here is a C++ program:

#include <iostream>
#include <valarray>
#include <cstdlib>
#include <ctime>
using namespace std;

void print_board( valarray<bool> const &board, size_t cols ) {
    for ( size_t i = 0; i < board.size(); ++ i ) { 
        cout << board[i] << " "; 
        if ( i % cols == cols-1 ) cout << endl;
    }   
    cout << endl;
}

int main() {
    srand( time(NULL) );
    int const rows = 5, cols = 5;

    valarray<bool> board( false, rows * cols );
    for ( size_t i = 0; i < board.size(); ++ i ) board[i] = rand() % 2;
    print_board( board, cols );

    int taken_moves = 0;
    for ( size_t i = board.size(); i > 0; ) { 
        if ( ! board[ -- i ] ) continue;

        size_t sizes[] = { i%cols +1, i/cols +1 }, strides[] = { 1, cols };

        gslice cur_move( 0, valarray<size_t>( sizes, 2 ),
                            valarray<size_t>( strides, 2 ) );
        board[ cur_move ] ^= valarray<bool>( true, sizes[0] * sizes[1] ); 

        cout << sizes[1] << ", " << sizes[0] << endl;
        print_board( board, cols );

        ++ taken_moves;
    }   

    cout << taken_moves << endl;
}

Answer 2

Not c++. Agree with @Potatoswatter that the optimal solutition is greedy, but I wondered if a Linear Diophantine System also works. This Mathematica function does it:

f[ei_] := (
  xdim = Dimensions[ei][[1]];
  ydim = Dimensions[ei][[2]];

  (* Construct XOR matrixes. These are the base elements representing the
     possible moves *)

  For[i = 1, i < xdim + 1, i++,
   For[j = 1, j < ydim + 1, j++,
    b[i, j] =  Table[If[k <= i && l <= j, -1, 0], {k, 1, xdim}, {l, 1, ydim}]
   ]
  ];

  (*Construct Expected result matrix*)
  Table[rv[i, j] = -1, {i, 1, xdim}, {j, 1, ydim}];

  (*Construct Initial State matrix*)
  Table[eiv[i, j] = ei[[i, j]], {i, 1, xdim}, {j, 1, ydim}];

  (*Now Solve*)
  repl = FindInstance[
           Flatten[Table[(Sum[a[i, j] b[i, j], {i, 1, xdim}, {j, 1, ydim}][[i]][[j]])  
                   eiv[i, j] == rv[i, j], {i, 1, xdim}, {j, 1, ydim}]], 
           Flatten[Table[a[i, j], {i, 1, xdim}, {j, 1, ydim}]]][[1]];

  Table[c[i, j] = a[i, j] /. repl, {i, 1, xdim}, {j, 1, ydim}];

  Print["Result ",xdim ydim-Count[Table[c[i, j], {i, 1, xdim}, {j, 1,ydim}], 0, ydim xdim]];)

When called with your examples (-1 instead of 0)

ei = ({
   {1, 1, 1, 1},
   {1, 1, 1, 1}
   });
f[ei];

ei = ({
   {-1, 1},
   {-1, 1}
  });
f[ei];

ei = {{-1, 1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, -1, -1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1}};
f[ei];

ei = ({
    {-1, -1, -1},
    {-1, -1, -1},
    {-1, -1, 1},
    {-1, 1, 1}
   });
f[ei];

The result is

Result :1
Result :2
Result :20
Result :6

Or :)

Solves a 20x20 random problem in 90 seconds on my poor man's laptop.