Algorithm for checking a special matrix template
I am struggling for this problem.
The algorithm checks a special matrix template if it matches or does not match the specified values. The maximum dimension is 20x20.
Special pattern: some term must be the sum or product of adjacent cells. Amounts and cells of products follow each other using one free cell. For odd-numbered rows, the sequence starts at free cells, and for even-numbered rows, starts at Sum or Product.
Empty representation of a 3x4 matrix (+ symbol indicates that this is the sum of neighbors, symbol x indicates that this is the product of neighbors):
[][+][]
[+][][x]
[][x][]
[x][][+]
Valid 3x4 matrix:
[1][6][2]
[9][3][8]
[3][54][3]
[5][2][6]
+3
source to share
2 answers
#include <stdio.h>
#include <memory.h>
#define MAX_DIMENSION 20
int dump_matrix( int m[MAX_DIMENSION][MAX_DIMENSION], int dx, int dy )
{
int i, j;
printf( " " );
for( i = 0; i < dx; ++i )
printf( "%4d ", i );
printf( "\n " );
for( i = 0; i < dx; ++i )
printf( "-----" );
printf( "\n" );
for( j = 0; j < dy; ++j )
{
printf( "%2d| ", j );
for( i = 0; i < dx; ++i )
{
printf( "%4d ", m[i][j] );
}
printf( "\n" );
}
printf( "\n" );
}
int dump_matrix_check( char c[MAX_DIMENSION][MAX_DIMENSION], int dx, int dy )
{
int i, j;
printf( " " );
for( i = 0; i < dx; ++i )
printf( "%2d ", i );
printf( "\n " );
for( i = 0; i < dx; ++i )
printf( "---" );
printf( "\n" );
for( j = 0; j < dy; ++j )
{
printf( "%2d| ", j );
for( i = 0; i < dx; ++i )
{
printf( "%c ", c[i][j] );
}
printf( "\n" );
}
printf( "\n" );
}
int test_matrix( int m[MAX_DIMENSION][MAX_DIMENSION], char c[MAX_DIMENSION][MAX_DIMENSION], int dx, int dy )
{
/* Test matrix. */
int is_special = 1; /* Assume special unless we find a fail case. */
int i, j;
dump_matrix( m, dx, dy );
for( i = 0; i < dx; ++i )
{
for( j = 0; j < dy; ++j )
{
int sum = ( i ? m[i - 1][j] : 0 ) + ( j ? m[i][j - 1] : 0 ) + ( ( i < dx - 1) ? m[i + 1][j] : 0 ) + ( ( j < dy - 1 ) ? m[i][j + 1] : 0 );
int product = ( i ? m[i - 1][j] : 1 ) * ( j ? m[i][j - 1] : 1 ) * ( ( i < dx - 1) ? m[i + 1][j] : 1 ) * ( ( j < dy - 1 ) ? m[i][j + 1] : 1 );
c[i][j] = ( sum == m[i][j] ) ? '+' : ( ( product == m[i][j] ) ? '*' : ' ' );
if( ( ( ( m[i][j] == sum ) || ( m[i][j] == product ) ) ? 1 : 0 ) != ( i + j ) % 2 )
{
/* Optionally, you can return 0 if you do not want to check the rest of the matrix */
is_special = 0;
}
/* If you prefer the more readable long view:
if( i + j % 2 )
{
// Check to make sure it is a free cell
if( ( m[i][j] == sum ) || ( m[i][j] == product ) )
is_special = 0;
}
else
{
// Check to make sure it is a sum or product cell
if( ( m[i][j] != sum ) && ( m[i][j] != product ) )
is_special = 0;
}
*/
}
}
dump_matrix_check( c, dx, dy );
return is_special;
}
int main( int argc, char ** argv )
{
int i, j;
int dx, dy;
char c[MAX_DIMENSION][MAX_DIMENSION];
int m[MAX_DIMENSION][MAX_DIMENSION];
/* Read in the values of the matrix */
memset( &c, sizeof( char ) * MAX_DIMENSION * MAX_DIMENSION, 0 );
memset( &m, sizeof( int ) * MAX_DIMENSION * MAX_DIMENSION, 0 );
dx = 3, dy = 4;
m[0][0] = 1; m[1][0] = 6; m[2][0] = 2;
m[0][1] = 9; m[1][1] = 3; m[2][1] = 8;
m[0][2] = 3; m[1][2] = 54; m[2][2] = 3;
m[0][3] = 5; m[1][3] = 2; m[2][3] = 6;
/* Test matrix. */
int is_special;
is_special = test_matrix( m, c, dx, dy );
printf( "Matrix is %sspecial\n\n\n", ( is_special ? "" : "not " ) );
m[0][0] = 1; m[1][0] = -6; m[2][0] = 2;
m[0][1] = 9; m[1][1] = 3; m[2][1] = 8;
m[0][2] = 3; m[1][2] = 54; m[2][2] = 3;
m[0][3] = 5; m[1][3] = 2; m[2][3] = 6;
is_special = test_matrix( m, c, dx, dy );
printf( "Matrix is %sspecial\n\n\n", ( is_special ? "" : "not " ) );
return 0;
}
Outputs:
0 1 2
---------------
0| 1 6 2
1| 9 3 8
2| 3 54 3
3| 5 2 6
0 1 2
---------
0| +
1| * +
2| *
3| + *
Matrix is special
0 1 2
---------------
0| 1 -6 2
1| 9 3 8
2| 3 54 3
3| 5 2 6
0 1 2
---------
0| +
1| * +
2| *
3| + *
Matrix is not special
+2
source to share
I may be wrong, but something like this should work: (pseudocode)
for each row
if row is odd
for all even col
check if m[row][col] sum or product of (m[row-1][col], m[row+1][col], m[row][col-1], m[row][col+1])
if row is even
for all odd col
check if m[row][col] sum or product of (m[row-1][col], m[row+1][col], m[row][col-1], m[row][col+1])
If any check fails, you stop and return false.
Just add some logic to check the line / col +/- 1 to avoid segfault and that should be OK
+1
source to share