Identifing an isolated character in a matrix

  • (2 Pages)
  • +
  • 1
  • 2

17 Replies - 1749 Views - Last Post: 18 December 2012 - 07:03 AM Rate Topic: -----

#1 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Identifing an isolated character in a matrix

Posted 12 December 2012 - 10:20 AM

Hi guys,
I've been thinking how to solve this problem the whole day.

Problem description
Let's suppose you have a matrix composed of 1's and 0's.(*)
Write a function that recognises if there is at least a 1 that is not adjacent to another 1.

I don't want you to solve the problem, i'd like if you could show me the direction though.

Thought of everithing in my head but it all seems too messy and this is an exercise about C++ Fundamentals, so it shouldn't be so complicated...

Any hint?

(*) ( Is it right to abbreviate ones and zeros like that in your language? ).

Is This A Good Question/Topic? 0
  • +

Replies To: Identifing an isolated character in a matrix

#2 AKMafia001  Icon User is offline

  • </code.in.dream>

Reputation: 187
  • View blog
  • Posts: 624
  • Joined: 11-June 11

Re: Identifing an isolated character in a matrix

Posted 12 December 2012 - 10:51 AM

You are trying to violate Rule#1 of this forum...

Please show some code what you have done so far, at least try to create a matrix bool matrix[rows][cols];...
Was This Post Helpful? 1
  • +
  • -

#3 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Identifing an isolated character in a matrix

Posted 12 December 2012 - 11:08 AM

View PostAKMafia001, on 12 December 2012 - 10:51 AM, said:

You are trying to violate Rule#1 of this forum...

Please show some code what you have done so far, at least try to create a matrix bool matrix[rows][cols];...


Usually, I don't write a single line of code until I've identified at least how to solve the problem ( via flow chart or pseudo-code )
To be honest, in this cade I've not written anything, just because as I said, I can't think of a single clean solution.
Anyway, I'll try...

1 Control of there is a single one present

May be decomposed into

1 If there is an isolated 1 on a row

sorry, i've not finished the post yet...
Was This Post Helpful? 0
  • +
  • -

#4 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Identifing an isolated character in a matrix

Posted 12 December 2012 - 11:41 AM

View PostAKMafia001, on 12 December 2012 - 10:51 AM, said:

You are trying to violate Rule#1 of this forum...

Please show some code what you have done so far, at least try to create a matrix bool matrix[rows][cols];...


Usually, I don't write a single line of code until I've identified at least how to solve the problem ( via flow chart or pseudo-code )
To be honest, in this cade I've not written anything, just because as I said, I can't think of a single clean solution.
Anyway, I'll try...
1 Control of there is a single one present


May be decomposed into
0 Initialize counter
1 If there is an isolated 1 on a row
2   If there isn't a 1 around it
3     Increment counter
4 Else, go to the subsequent row.


Expanding line 1...
1 // It doesn't work if the line starts with a 1, and it doesn't recognize if the last character is a 1!
2 While the current value of the current row is 0
3   Go to the next cell
4   If the current value is 1
5     Go to the next cell
6       If the current value is 0
7         Increment i
8   Go to the next cell



It doesn't work if the line starts with a 1, and it doesn't recognize if the last character is a 1!

Anyway, am i pointing in the right direction?
Is the first top-down refinement the one you'd have taken?

Sorry for the double numbers at the beginning of every line.
Didn't know how the [co.de] tags work...

Umh.. I could add
If the current value is a 1
  Go to the next line
    If the current value is a 0
      Increment counter


at the top of the first line to let it recognize the first isolated 1...
Was This Post Helpful? 0
  • +
  • -

#5 AKMafia001  Icon User is offline

  • </code.in.dream>

Reputation: 187
  • View blog
  • Posts: 624
  • Joined: 11-June 11

Re: Identifing an isolated character in a matrix

Posted 12 December 2012 - 12:25 PM

Well! Start with something, at least some wrong code, it doesn't matter. All that you have in mind, code them and then we will see if it works and how to make it better...

A pseudo:
bool matrix[2][2] = {{0, 1}, {1, 0}};

//Or simply declare the matrix and assign values to it using nested for loop
bool matrix[2][2];

for i = 1 to 2
    for j = 1 to 2
        matrix[i][j] = some_value
    next j
next i



Once you have the matrix, you can check for consecutive 1s...
if(matrix[i][j] == 1)
    if(matrix[i][j] == matrix[i][j+1])    // or simply, if(matrix[i][j+1] == 1)



Well! That's more than enough! Before asking any further, you have to show some code of yours...
Was This Post Helpful? 0
  • +
  • -

#6 Adak  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 331
  • View blog
  • Posts: 1,168
  • Joined: 01-April 11

Re: Identifing an isolated character in a matrix

Posted 12 December 2012 - 05:37 PM

You've been thinking about the 1's, and logically so - but turn that around and focus on the 0's, instead.

Now the algorithm comes to the fore.

Scan through the array, looking for a zero. When you find it, you will check ahead (use another variable for this check), for two digits. If the first digit is a one as you scan ahead, and the second digit is a space, then you have found an isolated one.

else, continue scanning. (yes, you will be scanning over some digits twice [once in the look ahead, and once in the non look ahead scan], but you will be able to optimize that problem away.)
Was This Post Helpful? 0
  • +
  • -

#7 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Identifing an isolated character in a matrix

Posted 17 December 2012 - 08:12 AM

Hi, I think i've got it!
Anyway, the compiler gives me an error, because i declare the function

bool checkIsolatedPoints( const int bitmap[][ kCols ], const int kRows, const int kCols );

before the main and i've not ye the dimensions of the matrix.
The request is to let the user choose them, so i pass them in the main after i've called a function name set_matrix_dimensions(...), but the compiler doesn't like it!

Excluding the passage via pointers, is there another way to calm the compiler?
Was This Post Helpful? 0
  • +
  • -

#8 jimblumberg  Icon User is offline

  • member icon


Reputation: 4131
  • View blog
  • Posts: 12,844
  • Joined: 25-December 09

Re: Identifing an isolated character in a matrix

Posted 17 December 2012 - 08:47 AM

Post your current code.


Jim
Was This Post Helpful? 0
  • +
  • -

#9 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Identifing an isolated character in a matrix

Posted 17 December 2012 - 12:20 PM

Sure!

/* All comments have been deleted cause they were not in your language! */

#include <iostream>
using std::cout;
using std::cin;
using std::cerr;
using std::endl;

// PROTOTYPES
void set_matrix_sizes( int &rows, int &columns );
int inputBitmap( int * const kFirstElement_ptr, const int kRows, const int kCols );
void printBitmap( int * const kFirstElement_ptr, const int kRows, const int kCols );
bool checkIsolatedPoints( const int bitmap[][ kCols ], const int kRows, const int kCols );

// MAIN
int main( )
{
	int rows;
	int columns;

	set_matrix_sizes( rows, columns );

	int bitmap[ rows ][ columns ];

	inputBitmap( &bitmap[ 0 ][ 0 ], rows, columns );
	printBitmap( &bitmap[ 0 ][ 0 ], rows, columns );

	if ( checkIsolatedPoints( bitmap, rows, columns ) )
		cout << "La matrice contiene punti isolati.\n";
	else
		cout << "La matrice non contiene punti isolati.\n";


	return 0;
}

int inputBitmap( int * const kFirst_ptr, const int kRows, const int kCols )
{
	for ( int * current_ptr = kFirst_ptr; current_ptr <  ( kFirst_ptr + ( kRows * kCols ) ); current_ptr++ )
	{
		cout << "Inserisci l'elemento [" <<  ( current_ptr - kFirst_ptr ) / kCols
			 << "][" << ( current_ptr - kFirst_ptr ) % kCols << "]: ";
		cin >> *current_ptr;

		if ( ( *current_ptr != 0 ) and ( *current_ptr != 1 ) )
			return -1;

	}

	return 0;
}

void printBitmap( const int * const kFirst_ptr, const int kRows, const int kCols )
{
	cout << endl;

	for ( const int * current_ptr = kFirst_ptr; current_ptr < ( kFirst_ptr + ( kRows * kCols ) ); current_ptr++ )
	{
		cout << *current_ptr << ( ( ( current_ptr - kFirst_ptr ) + 1 ) % kCols == 0 ? '\n' : ' ' );
	}

	cout << endl;
}

bool checkCandidates( const int bitmap[][ kCols ], const int kRows, const int kCols, const int i, const int j )
{
	if ( i >= 1 )
	{
		int k = i - 1;

		if ( j >= 1 )
			if ( bitmap[ k ][ j - 1 ] != 0 )
				return false;

		if ( bitmap[ k ][ j ] != 0 )
		        return false;

		if ( j < kCols - 1 )
			if ( bitmap[ k ][ j + 1 ] != 0 )
				return false;
	}

	if ( i < kRows - 1 )
	{
		k = i + 1;

		if ( j >= 1 )
			if ( bitmap[ k ][ j - 1 ] != 0 )
				return false;

		if ( bitmap[ k ][ j ] != 0 )
			return false;

		if ( j < kCols - 1 )
			if ( bitmap[ k ][ j + 1 ] != 0 )
				return false;

	if ( j >= 1 )
		if ( bitmap[ i ][ j - 1 ] != 0 )
			return false;

	if ( j < kCols - 1 )
		if ( bitmap[ i ][ j + 1 ] != 0 )
			return false;

	return true;
}

bool checkIsolatedPoints( const int bitmap[][ kCols ], const int kRows, const int kCols );
{
	for ( int row = 0; row < kRows; row++ )
		for ( int col = 0; col < kCols; col++ )
			if ( bitmap[ i ][ j ] == 1 )
				if ( checkCandidates( bitmap, kRows, kCols, i, j ) )
					return true;

	return false;
}



Was This Post Helpful? 0
  • +
  • -

#10 jimblumberg  Icon User is offline

  • member icon


Reputation: 4131
  • View blog
  • Posts: 12,844
  • Joined: 25-December 09

Re: Identifing an isolated character in a matrix

Posted 17 December 2012 - 12:29 PM

Array indexes in C++ must be compile time constants. So the following is not allowed:
	int rows;
	int columns;

	set_matrix_sizes( rows, columns );

	int bitmap[ rows ][ columns ];


Also in your function prototypes the following will produce an error:
bool checkIsolatedPoints( const int bitmap[][ kCols ], const int kRows, const int kCols );


The variable kCols must be defined before you try to use it in this prototype, and it must be a compile time constant.


Also in the future please post the complete error messages, exactly as they appear in your development environment.

Jim
Was This Post Helpful? 0
  • +
  • -

#11 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Identifing an isolated character in a matrix

Posted 17 December 2012 - 01:24 PM

bitmap.cpp:11: error: 'kCols' was not declared in this scope
bitmap.cpp:11: error: expected ')' before ',' token
bitmap.cpp:11: error: expected unqualified-id before 'const'
bitmap.cpp:71: error: 'kCols' was not declared in this scope
bitmap.cpp:71: error: expected ')' before ',' token
bitmap.cpp:71: error: expected unqualified-id before 'const'


Sorry, this are the error messages i got from my IDE. ( when will i be able to edit my previous posts? )

However, let's get back to the last problem. As i said, I should let the user decide the dimensions of the matrix, and i don't wanna use pointers ( because all the code i've written is based on an index-oriented logic ). I guess i could even use pointers and convert them to indexes in the code.
Do anyone know a cleaner solution?
Was This Post Helpful? 0
  • +
  • -

#12 jimblumberg  Icon User is offline

  • member icon


Reputation: 4131
  • View blog
  • Posts: 12,844
  • Joined: 25-December 09

Re: Identifing an isolated character in a matrix

Posted 17 December 2012 - 01:27 PM

Quote

Do anyone know a cleaner solution?

Yes, use vectors instead of the arrays.

Jim
Was This Post Helpful? 0
  • +
  • -

#13 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Identifing an isolated character in a matrix

Posted 17 December 2012 - 01:30 PM

I tryed this way but it doesn't seem to work. If I understand correctly is because when the compiler reads something like
bitmap[ 2 ][ 4 ]
it jumps
( ( 2 * 100 ) + 4 ) - 1
memory location after the first element, right?

/* Comments were deleted because they were not written in your language! */

#include <iostream>
using std::cout;
using std::cin;
using std::cerr;
using std::endl;

// Costanti globali
const int kMaxRows = 100;
const int kMaxCols = 100;


// PROTOTIPI
void set_matrix_sizes( int &rows, int &columns );
int inputBitmap( int * const kFirstElement_ptr, const int kRows, const int kCols );
void printBitmap( const int * const kFirstElement_ptr, const int kRows, const int kCols );
bool checkIsolatedPoints( const int bitmap[][ kMaxCols ], const int kRows, const int kCols );

// MAIN
int main( )
{
	int rows;
	int columns;

	set_matrix_sizes( rows, columns );

	int bitmap[ kMaxRows ][ kMaxCols ]; // inizializza la matrice bitmap

	inputBitmap( &bitmap[ 0 ][ 0 ], rows, columns );
	printBitmap( &bitmap[ 0 ][ 0 ], rows, columns );

	if ( checkIsolatedPoints( bitmap, rows, columns ) )
		cout << "La matrice contiene punti isolati.\n";
	else
		cout << "La matrice non contiene punti isolati.\n";


	return 0; 
}

void set_matrix_sizes( int &rows, int &columns )
{
	do
	{
		cout << "Inserisci il numero di righe della matrice associata alla bitmap: ";
		cin >> rows;
		
		if ( ( rows < 2 ) or ( rows > 100 ) )
			cout << "Errore! Prova ad inserire un valore compreso tra 2 e 100." << endl;
	} while ( ( rows < 2 ) or ( rows > 100 ) );
	
	do
	{
		cout << "Inserisci il numero di colonne della matrice associata alla bitmap: ";
		cin >> columns;
		
		if ( ( columns < 2 ) or ( columns > 100 ) )
			cout << "Errore! Prova ad inserire un valore compreso tra 2 e 100." << endl;
	} while ( ( columns < 2 ) or ( columns > 100 ) );
}

int inputBitmap( int * const kFirst_ptr, const int kRows, const int kCols )
{
	for ( int * current_ptr = kFirst_ptr; current_ptr <  ( kFirst_ptr + ( kRows * kCols ) ); current_ptr++ )
	{
		cout << "Inserisci l'elemento [" <<  ( current_ptr - kFirst_ptr ) / kCols
			 << "][" << ( current_ptr - kFirst_ptr ) % kCols << "]: ";
		cin >> *current_ptr;

		if ( ( *current_ptr != 0 ) and ( *current_ptr != 1 ) )
			return -1;

	}

	return 0;
}

void printBitmap( const int * const kFirst_ptr, const int kRows, const int kCols )
{
	cout << endl;

	for ( const int * current_ptr = kFirst_ptr; current_ptr < ( kFirst_ptr + ( kRows * kCols ) ); current_ptr++ )
	{
		cout << *current_ptr << ( ( ( current_ptr - kFirst_ptr ) + 1 ) % kCols == 0 ? '\n' : ' ' );
	}

	cout << endl;
}

bool checkCandidates( const int bitmap[][ kMaxCols ], const int kRows, const int kCols, const int i, const int j )
{
	if ( i >= 1 )
	{
		int k = i - 1;

		if ( j >= 1 )
			if ( bitmap[ k ][ j - 1 ] != 0 )
				return false;

		if ( bitmap[ k ][ j ] != 0 )
			return false;

		if ( j < kCols - 1 )
			if ( bitmap[ k ][ j + 1 ] != 0 )
				return false;
	}

	if ( i < kRows - 1 )
	{
		int k = i + 1;

		if ( j >= 1 )
			if ( bitmap[ k ][ j - 1 ] != 0 )
				return false;

		if ( bitmap[ k ][ j ] != 0 )
			return false;

		if ( j < kCols - 1 )
			if ( bitmap[ k ][ j + 1 ] != 0 )
				return false;
	}

	if ( j >= 1 )
		if ( bitmap[ i ][ j - 1 ] != 0 )
			return false;

	if ( j < kCols - 1 )
		if ( bitmap[ i ][ j + 1 ] != 0 )
			return false;

	return true;
}

bool checkIsolatedPoints( const int bitmap[][ kMaxCols ], const int kRows, const int kCols )
{
	for ( int row = 0; row < kRows; row++ )
		for ( int col = 0; col < kCols; col++ )
			if ( bitmap[ row ][ col ] == 1 )
				if ( checkCandidates( bitmap, kRows, kCols, row, col ) )
					return true;

	return false;
}


Was This Post Helpful? 0
  • +
  • -

#14 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Identifing an isolated character in a matrix

Posted 17 December 2012 - 02:56 PM

reading the code from my smartphone now...
I think the mistake I made is in the inputBitmap function (and even in printBitmap(...) so) and it's related to the pointers
Will update the code asap!
Was This Post Helpful? 0
  • +
  • -

#15 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Identifing an isolated character in a matrix

Posted 18 December 2012 - 06:12 AM

Here we go!

#include <iostream>
using std::cout;
using std::cin;
using std::cerr;
using std::endl;

// Global Constants
const int kMaxRows = 100;
const int kMaxCols = 100;


// PROTOTYPES
void set_matrix_sizes( int &rows, int &columns );
int inputBitmap( bool bitmap[][ kMaxCols ], const int kRows, const int kCols );
void printBitmap( const bool bitmap[][ kMaxCols ], const int kRows, const int kCols );
bool checkIsolatedPoints( const bool bitmap[][ kMaxCols ], const int kRows, const int kCols );

// MAIN
int main( )
{
	int rows;
	int columns;

	// let the user choose bitmap's dimensions
	set_matrix_sizes( rows, columns );

	bool bitmap[ kMaxRows ][ kMaxCols ]; // initialize the bitmap matrix

	// let the user fill the bitmap
	inputBitmap( bitmap, rows, columns );
	// show the bitmap
	printBitmap( bitmap, rows, columns );

	// show the proper output
	if ( checkIsolatedPoints( bitmap, rows, columns ) )
		cout << "The bitmap contains isolated point(s).\n";
	else
		cout << "The bitmap does not contain an isolated point.\n";


	return 0; // denotes a correct termination
}

// function that lets the user choise the matrix's dimensions
void set_matrix_sizes( int &rows, int &columns )
{
	do
	{
		cout << "Enter the number of rows of the matrix associated to the bitmap: ";
		cin >> rows;
		
		if ( ( rows < 2 ) or ( rows > 100 ) )
			cout << "Error! Try to insert a value in the 2-100 range." << endl;
	} while ( ( rows < 2 ) or ( rows > 100 ) );
	
	do
	{
		cout << "Enter the number of columns of the matrix associated to the bitmap:  ";
		cin >> columns;
		
		if ( ( columns < 2 ) or ( columns > 100 ) )
			cout << "Error! Try to insert a value in the 2-100 range." << endl;
	} while ( ( columns < 2 ) or ( columns > 100 ) );
}

// function that lets the user fill the content of the matrix
int inputBitmap( bool bitmap[][ kMaxCols ], const int kRows, const int kCols )
{
	for ( int row = 0; row < kRows; row++ )
	{
		for ( int col = 0; col < kCols; col++ )
		{
			cout << "Enter the element [" << row << "][" << col << "]: ";
			cin >> bitmap[ row ][ col ];

			if ( ( bitmap[ row ][ col ] != 0 ) and ( bitmap[ row ][ col ] != 1 ) )
				// if user insert a non-acceptable value,
				// return an error flag to the main that terminate the execution
				return -1;
		}

	}

	return 0; // denots a correct termination
}

// function that prints out the bitmap
void printBitmap( const bool bitmap[][ kMaxCols ], const int kRows, const int kCols )
{
	cout << endl;

	for ( int row = 0; row < kRows; row++ )
		for ( int col = 0; col < kCols; col++ )
			cout << bitmap[ row ][ col ] << ( col % kCols == kCols - 1 ? '\n' : ' ' );
			
	cout << endl;
}

// function that checks if checkIsolatedPoints( ... )'s candidates are isolated pointss
bool checkCandidates( const bool bitmap[][ kMaxCols ], const int kRows, const int kCols, const int i, const int j )
{
	if ( i >= 1 )
	{
		// is at least at the second line
		int k = i - 1;
		// ** read "k = nord" **

		if ( j >= 1 )
			if ( bitmap[ k ][ j - 1 ] != 0 )
				return false;

		if ( bitmap[ k ][ j ] != 0 )
			return false;

		if ( j < kCols - 1 )
			if ( bitmap[ k ][ j + 1 ] != 0 )
				return false;
	}

	if ( i < kRows - 1 )
	{
		// is at most at the second last row
		int k = i + 1;
		// ** read "k = nord" **

		if ( j >= 1 )
			if ( bitmap[ k ][ j - 1 ] != 0 )
				return false;

		if ( bitmap[ k ][ j ] != 0 )
			return false;

		if ( j < kCols - 1 )
			if ( bitmap[ k ][ j + 1 ] != 0 )
				return false;
	}

	if ( j >= 1 )
		if ( bitmap[ i ][ j - 1 ] != 0 )
			return false;

	if ( j < kCols - 1 )
		if ( bitmap[ i ][ j + 1 ] != 0 )
			return false;

	// candidate is promoted to isolated point!
	return true;
}

// functions that checks if there are isolated point
bool checkIsolatedPoints( const bool bitmap[][ kMaxCols ], const int kRows, const int kCols )
{
	for ( int row = 0; row < kRows; row++ )
		for ( int col = 0; col < kCols; col++ )
			if ( bitmap[ row ][ col ] == 1 )
				// a candidate to isolated point exist
				if ( checkCandidates( bitmap, kRows, kCols, row, col ) )
					// candidate is in fact an isolate point!
					return true;

	// there are not candidates!
	return false;
}



Now i'd like to make it better.
Let's focus on the algorithm to find isolated points.
Any suggestion?
Even if you don't post code, advice are greatly appreciated!
Thanks.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2