fbpx

C++: Flipping Bits Game

Bjarne-stroustrup
 
The game

Given an N by N square array of zeroes or ones in an initial configuration, and a target configuration of zeroes and ones The task is to transform one to the other in as few moves as possible by inverting whole numbered rows or whole lettered columns at once, as one move.

In an inversion any 1 becomes 0, and any 0 becomes 1 for that whole row or column.

The Task

The task is to create a program to score for the Flipping bits game.

  1. The game should create an original random target configuration and a starting configuration.
  2. Ensure that the starting position is never the target position.
  3. The target position must be guaranteed as reachable from the starting position. (One possible way to do this is to generate the start position by legal flips from a random target position. The flips will always be reversible back to the target from the given start position).
  4. The number of moves taken so far should be shown.

Show an example of a short game here, on this page, for a 3 by 3 array of bits.

#include <time.h>
#include <iostream>
#include <string>

typedef unsigned char byte;
using namespace std;

class flip
{
public:
	flip() { field = 0; target = 0; }
	void play( int w, int h ) { wid = w; hei = h; createField(); gameLoop(); }

private:
	void gameLoop()
	{
		int moves = 0;
		while( !solved() )
		{
			display(); string r; cout << "Enter rows letters and/or column numbers: "; cin >> r;
			for( string::iterator i = r.begin(); i != r.end(); i++ )
			{
				byte ii = ( *i );
				if( ii - 1 >= '0' && ii - 1 <= '9' ) { flipCol( ii - '1' ); moves++; }
				else if( ii >= 'a' && ii <= 'z' ) { flipRow( ii - 'a' ); moves++; }
			}
		}
		cout << endl << endl << "** Well done! **" << endl << "Used " << moves << " moves." << endl << endl;
	}

	void display()
	{ system( "cls" ); output( "TARGET:", target ); output( "YOU:", field ); }

	void output( string t, byte* f )
	{
		cout << t << endl;
		cout << " "; for( int x = 0; x < wid; x++ ) cout << " " << static_cast<char>( x + '1' ); cout << endl;
		for( int y = 0; y < hei; y++ )
		{
			cout << static_cast<char>( y + 'a' ) << " ";
			for( int x = 0; x < wid; x++ )
			cout << static_cast<char>( f[x + y * wid] + 48 ) << " ";
			cout << endl;
		}
		cout << endl << endl;
	}

	bool solved()
	{
		for( int y = 0; y < hei; y++ )
		for( int x = 0; x < wid; x++ )
		if( target[x + y * wid] != field[x + y * wid] ) return false;
		return true;
	}

	void createTarget()
	{
		for( int y = 0; y < hei; y++ )
		for( int x = 0; x < wid; x++ )
		if( frnd() < .5f ) target[x + y * wid] = 1;
		else target[x + y * wid] = 0;
		memcpy( field, target, wid * hei );
	}

	void flipCol( int c )
	{ for( int x = 0; x < hei; x++ ) field[c + x * wid] = !field[c + x * wid]; }

	void flipRow( int r )
	{ for( int x = 0; x < wid; x++ ) field[x + r * wid] = !field[x + r * wid]; }

	void calcStartPos()
	{
		int flips = ( rand() % wid + wid + rand() % hei + hei ) >> 1;
		for( int x = 0; x < flips; x++ )
		{ if( frnd() < .5f ) flipCol( rand() % wid ); else flipRow( rand() % hei ); }
	}

	void createField()
	{
		if( field ){ delete [] field; delete [] target; }
		int t = wid * hei; field = new byte[t]; target = new byte[t];
		memset( field, 0, t ); memset( target, 0, t ); createTarget();
		while( true ) { calcStartPos(); if( !solved() ) break; }
	}

	float frnd() { return static_cast<float>( rand() ) / static_cast<float>( RAND_MAX ); }

	byte* field, *target; int wid, hei;
};

int main( int argc, char* argv[] )
{ srand( time( NULL ) ); flip g; g.play( 3, 3 ); return system( "pause" ); }
Output:
TARGET:
  1 2 3
a 0 1 0 
b 0 1 0 
c 0 1 0 

YOU:
  1 2 3
a 0 0 0 
b 0 0 0 
c 1 1 1 

Enter rows letters and/or column numbers: 2c

** Well done! **
Used 2 moves.

SOURCE

Content is available under GNU Free Documentation License 1.2.