The Problem is to find all the hidden words in a text file and to print the unmatched words in a single row.
The input lines are formed as X*Y grid. And the hidden words can be in any direction in the grid.
Possible word directions are shown in the following image.(just an example, don't search for meaningful words there :p )
Input to this program is a text file. File name should be given as a command line argument to the program. This text file contains two sections. first section contains the lines in which the words to be searched. second section contains the words to be found. These two sections are separated by a new line.
My algorithm to solve this problem is simple and see it below.
Souce Code : HuntWords.cpp
/**************************************************************************************************************/
/* */
/* Author : R. Satheesh Kumar */
/* Date : June 23rd 2011 */
/* */
/**************************************************************************************************************/
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include <pthread.h>
using namespace std;
typedef vector<vector<char> > My2DMatrix;
typedef vector<vector<int> > My2DMapMatrix;
typedef vector<string> WordsToFind;
My2DMatrix matrix;
My2DMapMatrix resultmap;
enum Directions{
LEFT,
RIGHT,
UP,
DOWN,
LEFTUP,
RIGHTUP,
LEFTDOWN,
RIGHTDOWN,
CENTRE
};
typedef vector<Directions> MyDirections;
void trim(string &str)
{
string whitespaces (" \t\f\v\n\r");
size_t found;
found=str.find_last_not_of(whitespaces);
if (found!=string::npos)
str.erase(found+1);
}
void createMatrix(string const &filename, My2DMatrix &matrix,My2DMapMatrix &resultmap, WordsToFind &words)
{
string line;
ifstream ifs(filename.c_str());
int flag=0; // 0=FILE, 1=WORD
int len=0;
int maxcol=0;
if(ifs.fail())
{
cout<<"Unable To Open File for Reading\n";
return;
}
while(!ifs.eof())
{
vector<char> tmp;
vector<int> rmap;
getline(ifs,line);
trim(line);
len = line.length();
if(maxcol<len)
maxcol=len;
if(len<=0)
{
flag=1;
continue;
}
if(flag==0)
{
tmp.clear();
tmp.insert(tmp.end(),line.begin(),line.end());
matrix.insert(matrix.end(),tmp);
rmap.clear();
rmap.assign(len,1);
resultmap.insert(resultmap.end(),rmap);
}
else if(flag==1)
{
words.insert(words.end(),line);
}
}
ifs.close();
for(int i=0;i<matrix.size();i++)
{
matrix[i].resize(maxcol,'\0');
resultmap[i].resize(maxcol,0);
}
}
MyDirections FindDirection(const My2DMatrix &matrix,const int &row, const int &col,const string &word)
{
MyDirections dir;
if(word.length()-1<=col && word[1]==matrix[row][col-1])
{
dir.insert(dir.end(),LEFT);
}
if(matrix[row].size()-col >= word.length() && word[1]==matrix[row][col+1])
{
dir.insert(dir.end(),RIGHT);
}
if(word.length()-1<=row && word[1]==matrix[row-1][col])
{
dir.insert(dir.end(),UP);
}
if(matrix.size()-row >= word.length() && word[1]==matrix[row+1][col])
{
dir.insert(dir.end(),DOWN);
}
if(word.length()-1<=row && word.length()-1<=col && word[1]==matrix[row-1][col-1])
{
dir.insert(dir.end(),LEFTUP);
}
if(word.length()-1<=row && matrix[row].size()-col>= word.length() && word[1]==matrix[row-1][col+1])
{
dir.insert(dir.end(),RIGHTUP);
}
if(matrix.size()-row>= word.length() && word.length()-1<=col && word[1]==matrix[row+1][col-1])
{
dir.insert(dir.end(),LEFTDOWN);
}
if(matrix.size()-row>= word.length() && matrix[row].size()-col>= word.length() && word[1]==matrix[row+1][col+1])
{
dir.insert(dir.end(),RIGHTDOWN);
}
return dir;
}
bool FindLeft(const My2DMatrix &matrix, const int &row, const int &col, const string &word)
{
bool flag=true;
for(int i=0;i<word.size();i++)
{
if(word[i]==matrix[row][col-i])
{
continue;
}
else
{
flag=false;
break;
}
}
return flag;
}
bool FindRight(const My2DMatrix &matrix, const int &row, const int &col, const string &word)
{
bool flag=true;
for(int i=0;i<word.size();i++)
{
if(word[i]==matrix[row][col+i])
{
continue;
}
else
{
flag=false;
break;
}
}
return flag;
}
bool FindUp(const My2DMatrix &matrix, const int &row, const int &col, const string &word)
{
bool flag=true;
for(int i=0;i<word.size();i++)
{
if(word[i]==matrix[row-i][col])
{
continue;
}
else
{
flag=false;
break;
}
}
return flag;
}
bool FindDown(const My2DMatrix &matrix, const int &row, const int &col, const string &word)
{
bool flag=true;
for(int i=0;i<word.size();i++)
{
if(word[i]==matrix[row+i][col])
{
continue;
}
else
{
flag=false;
break;
}
}
return flag;
}
bool FindLeftUp(const My2DMatrix &matrix, const int &row, const int &col, const string &word)
{
bool flag=true;
for(int i=0;i<word.size();i++)
{
if(word[i]==matrix[row-i][col-i])
{
continue;
}
else
{
flag=false;
break;
}
}
return flag;
}
bool FindRightUp(const My2DMatrix &matrix, const int &row, const int &col, const string &word)
{
bool flag=true;
for(int i=0;i<word.size();i++)
{
if(word[i]==matrix[row-i][col+i])
{
continue;
}
else
{
flag=false;
break;
}
}
return flag;
}
bool FindLeftDown(const My2DMatrix &matrix, const int &row, const int &col, const string &word)
{
bool flag=true;
for(int i=0;i<word.size();i++)
{
if(word[i]==matrix[row+i][col-i])
{
continue;
}
else
{
flag=false;
break;
}
}
return flag;
}
bool FindRightDown(const My2DMatrix &matrix, const int &row, const int &col, const string &word)
{
bool flag=true;
for(int i=0;i<word.size();i++)
{
if(word[i]==matrix[row+i][col+i])
{
continue;
}
else
{
flag=false;
break;
}
}
return flag;
}
void updateMapMatrix(My2DMapMatrix &resultmap, const int &row, const int &col, const int &len, const Directions &dir)
{
switch(dir)
{
case LEFT:
for(int i=0;i<len;i++)
{
resultmap[row][col-i]=0;
}
break;
case RIGHT:
for(int i=0;i<len;i++)
{
resultmap[row][col+i]=0;
}
break;
case UP:
for(int i=0;i<len;i++)
{
resultmap[row-i][col]=0;
}
break;
case DOWN:
for(int i=0;i<len;i++)
{
resultmap[row+i][col]=0;
}
break;
case LEFTUP:
for(int i=0;i<len;i++)
{
resultmap[row-i][col-i]=0;
}
break;
case RIGHTUP:
for(int i=0;i<len;i++)
{
resultmap[row-i][col+i]=0;
}
break;
case LEFTDOWN:
for(int i=0;i<len;i++)
{
resultmap[row+i][col-i]=0;
}
break;
case RIGHTDOWN:
for(int i=0;i<len;i++)
{
resultmap[row+i][col+i]=0;
}
break;
case CENTRE:
resultmap[row][col]=0;
break;
default:
break;
}
}
void FindWord(const My2DMatrix &matrix,My2DMapMatrix &resultmap,const string &word)
{
if(word.length()>1)
{
for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<matrix[i].size();j++)
{
if(word[0]==matrix[i][j])
{
MyDirections dir=FindDirection(matrix,i,j,word);
if(dir.size()<=0)
continue;
for(int k=0;k<dir.size();k++)
{
switch(dir[k])
{
case LEFT:
if(FindLeft(matrix,i,j,word))
{
updateMapMatrix(resultmap, i, j, word.length(),LEFT);
}
break;
case RIGHT:
if(FindRight(matrix,i,j,word))
{
updateMapMatrix(resultmap, i, j, word.length(),RIGHT);
}
break;
case UP:
if(FindUp(matrix,i,j,word))
{
updateMapMatrix(resultmap, i, j, word.length(),UP);
}
break;
case DOWN:
if(FindDown(matrix,i,j,word))
{
updateMapMatrix(resultmap, i, j, word.length(),DOWN);
}
break;
case LEFTUP:
if(FindLeftUp(matrix,i,j,word))
{
updateMapMatrix(resultmap, i, j, word.length(),LEFTUP);
}
break;
case RIGHTUP:
if(FindRightUp(matrix,i,j,word))
{
updateMapMatrix(resultmap, i, j, word.length(),RIGHTUP);
}
break;
case LEFTDOWN:
if(FindLeftDown(matrix,i,j,word))
{
updateMapMatrix(resultmap, i, j, word.length(),LEFTDOWN);
}
break;
case RIGHTDOWN:
if(FindRightDown(matrix,i,j,word))
{
updateMapMatrix(resultmap, i, j, word.length(),RIGHTDOWN);
}
break;
default:
break;
}
}
}
}
}
}
else if(word.length()==1)
{
for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<matrix[i].size();j++)
{
if(word[0]==matrix[i][j])
{
updateMapMatrix(resultmap, i, j, word.length(),CENTRE);
}
}
}
}
}
void printUnMatched(const My2DMatrix &matrix, const My2DMapMatrix &resultmap)
{
for(int i=0;i<resultmap.size();i++)
{
for(int j=0;j<resultmap[i].size();j++)
{
if(resultmap[i][j]==1 && matrix[i][j]!=' ')
{
cout<<matrix[i][j];
}
}
}
cout<<endl;
}
void *startThreaad(void *args)
{
const char* tmp = static_cast<char*>(args);
string word(tmp);
FindWord(matrix,resultmap,word);
pthread_exit(NULL);
}
int main(int argc, char* argv[])
{
if(argc < 2)
{
cout<<"Please provide the input file name in commandline.\n";
exit(1);
}
WordsToFind words;
string filename(argv[1]);
createMatrix(filename,matrix,resultmap,words);
pthread_t threads[words.size()];
pthread_attr_t attr;
pthread_attr_init(&attr);
for(int i=0;i<words.size();i++)
{
pthread_create(&threads[i], &attr, startThreaad, static_cast<void*>(const_cast<char*>(words[i].c_str())));
}
for (int i=0; i<words.size(); i++) {
pthread_join(threads[i], NULL);
}
printUnMatched(matrix,resultmap);
pthread_attr_destroy(&attr);
pthread_exit(NULL);
}
How To Compile:
This program is intended for Unix platform only. you should be having ptherad & GNU CC installed.
The following line will do the compilation job for you.
g++ HuntWords.cpp -lpthread -o HuntWords
To run the application just do ./HuntWords filename.txt from the compiled source directory.
Sample Input Output:
consider the following is the contents of input file filename.txt
ELGOOGWWW
TIRXMAHIR
BATMANZNC
CMRVLTOLD
WIN
TAR
BATMAN
CAR
WWW
TOLD
CD
The output will be : XMAHRZVL
Tested this code in GCC 3.4.4. With 20 input lines and 50 words to be found. the approximate completion time is 0.062 ms.
Thank you. That's all for now. If you any have better way of doing this. please let me and others know by posting your comments.
No comments:
Post a Comment