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

You could use recursive trials.

You would need at least the move count and to pass a copy of the vector. You'd also want to set a maximum move cutoff to set a limit to the breadth of branches coming out of at each node of the search tree. Note this is a "brute force" approach."

Your general algorithm structure would be:

const int MAX_FLIPS=10;
const unsigned int TREE_BREADTH=10;

int run_recursion(std::vector<std::vector<bool>> my_grid, int current flips)
{
   bool found = true;
   int temp_val = -1;
   int result = -1;
   //Search for solution with for loops; if true is found in grid, found=false;
   ...
   if  ( ! found && flips < MAX_FLIPS )
   {
       //flip coin.
      for ( unsigned int more_flips=0; more_flips < TREE_BREADTH; more_flips++ )
      {
         //flip one coin
         ...
         //run recursion
         temp_val=run_recursion(my_grid,flips+1)
         if ( (result == -1 && temp_val != -1) || 
              (temp_val != -1 && temp_val < result) )
            result = temp_val;
      }
   }

   return result;
}

...sorry in advance for any typos/minor syntax errors. Wanted to prototype a fast solution for you, not write the full code...

Or easier still, you could just use a brute force of linear trials. Use an outer for loop would be number of trials, inner for loop would be flips in trial. On each loop you'd flip and check if you'd succeeded, recycling your success and flip code from above. Success would short circuit the inner loop. At the end of the inner loop, store the result in the array. If failure after max_moves, store -1. Search for the max value.

A more elegant solution would be to use a multithreading library to start a bunch of threads flipping, and have one thread signal to others when it finds a match, and if the match is lower than the # of steps run thus far in another thread, that thread exits with failure.

I suggest MPI, but CUDA might win you brownie points as it's hot right now.

Hope that helps, good luck!

Answer 2

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 3

Basically, you're taking the N+M-1 coins in the right and bottom borders and solving them, then just calling the algorithm recursively on everything else. This is basically what Potatoswatter is saying to do. Below is a very simple recursive algorithm for it.

Solver(Grid[N][M])
    if Grid[N-1][M-1] == Heads
        Flip(Grid,N-1,M-1)

    for each element i from N-2 to 0 inclusive //This is empty if N is 1
        If Grid[i][M-1] == Heads
            Flip(Grid,i,M-1)

    for each element i from M-2 to 0 inclusive //This is empty if M is 1
        If Grid[N-1][i] == Heads
            Flip(Grid,N-1,i)

    if N>1 and M > 1:
        Solver(Grid.ShallowCopy(N-1, M-1))

    return;     

Note: It probably makes sense to implement Grid.ShallowCopy by just having Solver have arguments for the width and the height of the Grid. I only called it Grid.ShallowCopy to indicate that you should not be passing in a copy of the grid, though C++ won't do that with arrays by default anyhow.

Answer 4

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.

Answer 5

An easy criterion for rectangle(x,y) to be flipped seems to be: exactly when the number of ones in the 2x2 square with top-left square (x,y) is odd.

(code in Python)

def flipgame(grid):
  w, h = len(grid[0]), len(grid)
  sol = [[0]*w for y in range(h)]
  for y in range(h-1):
    for x in range(w-1):
      sol[y][x] = grid[y][x] ^ grid[y][x+1] ^ grid[y+1][x] ^ grid[y+1][x+1]
  for y in range(h-1):
    sol[y][w-1] = grid[y][w-1] ^ grid[y+1][w-1]
  for x in range(w-1):
    sol[h-1][x] = grid[h-1][x] ^ grid[h-1][x+1]
  sol[h-1][w-1] = grid[h-1][w-1]
  return sol

The 2D array returned has a 1 in position (x,y) if rectangle(x,y) should be flipped, so the number of ones in it is the answer to your original question.

EDIT: To see why it works: If we do moves (x,y), (x,y-1), (x-1,y), (x-1,y-1), only square (x,y) is inverted. This leads to the code above. The solution must be optimal, as there are 2^(h*w) possible configurations of the board and 2^(h*w) possible ways to transform the board (assuming every move can be done 0 or 1 times). In other words, there is only one solution, hence the above produces the optimal one.