|
Various code samples for various reasons.
linefinder.cc
/*
this is an answer to an interview question.
Copyright (c) 2009, Peter Varga pvarga@pvrg.net
All rights reserved.
Redistribution and use in source and binary forms, with or
without modification, are permitted provided that the following
conditions are met:
o Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
o Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
o Neither the name of pvrg.net nor the names of its contributors may be used
to endorse or promote products derived from this software without specific
prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
THE POSSIBILITY OF SUCH DAMAGE.
*/
#include <iostream>
#include <istream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector< vector<int> > vector2d;
typedef vector<int> vector1d;
/** finds a line in a matrix provided by client code.
line can be linear or diagonal and have the same values.
*/
class LineFinder {
protected:
/**
finds a line of 0's in a row or column of a matrix
end return true, otherwise false.
<param>int ** matrix</param> pointer to the integer array specified by
x and y vertices.
<param>bool</param> indicating vertical or horizontal search.
*/
const bool checkEdgeLine( const vector2d & matrix, bool vert = true ) const {
size_t idx = 0;
size_t idy = 0;
size_t *pida = &idy;
size_t *pidb = &idx;
size_t maxrunner = matrix[0].size();
size_t maxtang = matrix.size();
size_t ** runner = &pidb;
size_t ** tang = &pida;
bool good = true;
if( ! vert ) {
pida = &idx;
pidb = &idy;
maxrunner = matrix.size();
maxtang = matrix[0].size();
runner = & pida;
tang = &pidb;
}
for( (**runner) = 0; (**runner) < maxrunner; (**runner)++ ) {
if( matrix[*pida][*pidb] == 0 ) {
good = true;
// if( checkLine(matrix, *pida, vert) ) return true;
for( (**tang) = 0; (**tang) < maxtang; (**tang)++ ) {
cout << " eval " << matrix[*pida][*pidb] ;
if( matrix[*pida][*pidb] != cond ) {
good = false;
break;
}
}
if( good ) return true;
}
}
return false;
}
/**
finds a line of cond in a matrix diagonally.
<param>vector2d</param> matrix.
*/
const bool checkDiagonal( const vector2d & matrix ) const {
// run through the longer side, when found a 0, run diagonals
ssize_t x = 0;
ssize_t y = 0;
ssize_t longer = matrix[0].size();
ssize_t shorter = matrix.size();
ssize_t * pida = &x;
ssize_t * pidb = &y;
ssize_t **runner = &pida;
ssize_t **orto = &pidb;
if( longer < shorter ) {
swap(longer, shorter);
swap(pida, pidb);
swap(runner, orto);
}
for( (**runner) = 0; (**runner) < longer; (**runner)++ ) {
if( matrix[*pida][*pidb] == 0 ) {
// run diagonals pos
ssize_t saverunner = (**runner);
ssize_t saveorto = (**orto);
bool good = true;
ssize_t limit = max(longer - (**runner), shorter );
for( ; (**orto) < limit; (**orto)++, (**runner)++ ) {
if( matrix[*pida][*pidb] != cond ) {
good = false;
break;
}
}
(**runner) = saverunner;
(**orto) = saveorto;
if( good ) return true;
// run diagonals neg
good = true;
for( ; (**runner) >= 0 && (**orto) < shorter;
(**orto)++, (**runner)-- )
{
if( matrix[*pida][*pidb] != 0 ) {
good = false;
break;
}
}
if( good ) return true;
(**runner) = saverunner;
(**orto) = saveorto;
}
}
return false;
}
/**
find first cond on the edge of the matrix's 2 sides, and follow to find all
0's ine series. Start with longer vertex first.
*/
protected:
const int cond;
public:
/** LineFinder constructor.
<param>int</param> condition to find in the matrix.
*/
LineFinder( int x = 0 ) : cond(x) { }
/**
find a line in a matrix. it calls protected members, checkEdgeLine and checkDiagonal.
<param>vector2d</param> a matrix
*/
const bool findLine( const vector2d & matrix ) {
const bool vertical = true;
const bool horizontal = false;
if( checkDiagonal( matrix ) ) return true;
if( matrix[0].size() == matrix.size() ) return false;
if( checkEdgeLine( matrix, vertical ) ) return true;
if( checkEdgeLine( matrix, horizontal ) ) return true;
return false;
}
/** just a debug to see what's in the matrix
*/
const bool printmatrix( const vector2d & matrix ) const {
const size_t xsize = matrix[0].size();
const size_t ysize = matrix.size();
size_t idx;
size_t idy;
for( idy = 0; idy != ysize; idy++ ) {
for( idx = 0; idx != xsize; idx++ ) {
cout << matrix[idy][idx] << " ";
}
cout << endl;
}
cout << "x size " << matrix.size() << endl;
cout << "y size " << matrix[0].size() << endl;
return false;
}
};
//
// simplistic testing code below:
// remove as needed
class Randomizer {
public:
Randomizer(int x = 123) {
srand( x ); // use the same seed to have the same order
}
size_t operator() (size_t s ) {
return( rand() % s );
}
};
int main(int argc, char ** argv ) {
if( argc < 3 ) {
cout << " this is part of testing LineFinder. needs a seed integer" << endl;
}
int x = atoi(argv[1]);
Randomizer randomizer(x);
vector2d v2d(5, vector<int>(4,-1) );
vector1d v1d(4);
v1d[0] = 1;
v1d[1] = 0;
v1d[2] = 0;
v1d[3] = 1;
cout << " v2d[0] " << v2d[0].size() << " v2d " << v2d.size() << endl;
for( size_t idx = 0; idx < v2d.size(); idx++ ) {
random_shuffle( v1d.begin(), v1d.end(), randomizer );
v2d[idx] = v1d;
}
LineFinder lf;
lf.printmatrix( v2d );
bool r = lf.findLine( v2d );
cout << endl << "result is " << r << endl;
return 0;
}
|