Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 295

# Searching duplicates in a 2d matrix

Hi everybody,

I asked a question like that sooner, but now I want to customize my function and add some functionalities. Let's say I have a 2d square matrix (x = y) containing some letters and I knows the coordinates of a letter in the grid. Ex. A letter 'C' is located at the point (0,3).  How could I check every direction to find a similar letter next to the starting one (including crossline) ?

I've search some info on google about games and searching function but couldn't find anything. If anyone could give me a hand, it would be greaty appreciate !

Thanks a lot !
0
The_Kingpin08
• 13
• 12
1 Solution

Commented:
You could use an algorithm like

#include <list>
using namespace std:

struct Coord {
int x;
int y;
};

// coordinates of all adjacent points relative to a "center"
Coord neigbours [] = { { -1, -1}, { -1, 0}, { -1, 1}, { 0, -1}, { 0, 1}, { 1, -1}, { 1, 0}, { 1, 1},  { 42, 42}};

// { 42, 42} serves as the "end marker"

void FindAdjacentIdentical ( const cha** pMatrix, const size_t szSquareSize,  const Coord c, list<Coord>& lstFound)
{

Coord* p = neigbours;

int x, y;

while ( p->x != 42) {

x = c.x + p->x;
y = c.y + p->y;

// go through the list of adjacent points to find a match
if (  x >= 0 && y >= 0 && x + c.x <= szSquareSize &&  y + c.y <= szSquareSize) {

// found one?
if ( pMatrix[x][y] == pMatrix[c.x][c.y])

Coord cFound;

cFound.x = x;
cFound.y = y;

lstFound.push_back( cFound);
}

++p; // move to next entry
}
}
0

Author Commented:
I understand most of your logic, but still; me <------- newb !

If I get it right, since you have the starting location, you make an array of direct neigbours instead of messing with the array ? Didn't though about that.
Not sure that I understand the push_back method.

Now since I already started a function that find the position in the grid of an item, could I call your function from there ?

Like this:

bool findWord(char *word, char **theGrid, int gridSize, int loc_x, int loc_y)
{
int len = strlen(word);

if(len>1)  // a word can't be 1 letter
for (int x=0; x < size - 1; x++) {

char* line = new char [strlen(array[x])];
line = array[x];          //get the current line of the grid

for (unsigned int y=0; y < strlen(array[x]); y++) {
if(line[y] == '\0') break;  //end of line

if (toupper(line[y])!=toupper(word[0])) continue;

// get the current coordinates
int cur_x = x;
int cur_y = y;

for (int l=0; l<len; l++)  {
if (toupper(line[y])!=toupper(word[l])) break;

// gets the coordinates of the first letter of the searched word
loc_x = x;
loc_y = y;

// **** Call your function to check the neigbours and return the direction if a matching letter was founf ****
return true;

if (cur_x<0 || cur_y<0 || cur_x>=size || cur_y>=size) break;
}
}
}
return false;
}

With a little modifications to your function, do you think this could be possible or it would be too much job ?

Thanks
0

Author Commented:
array should be theGrid in the previous post's function
0

Commented:
>>If I get it right, since you have the starting location, you make an array of direct neigbours instead of
>>messing with the array ? Didn't though about that.

Yes, that's the idea. As soon as you know the relative positions, only one loop is needed

>>Not sure that I understand the push_back method.

Well, I was assuming that there could be more than one adjacent equivalent character. thus I chose a list to store all that were found.

In your function, you could use that like

// gets the coordinates of the first letter of the searched word
list<Coord> lstFound
Coord toFind;
toFind.x = x;
toFind.y = y;

0

Commented:
Ooops, that should have been

FindAdjacentIdentical (theGrid, gridSize, 'C', toFind, lstFound);
0

Author Commented:
Hey thanks a lot for the precious help jkr !

Another thing I was wondering, how do I declare your function in my header file ? I just learned that and have no idea how to use user's type in the header and all my tries had no luck so far...

void FindAdjacentIdentical (const char**, const ,  const Coord, list<Coord>& lstFound);

?

Thanks a lot.
Frank
0

Commented:
>>Another thing I was wondering, how do I declare your function in my header file ?

You'll need all the necessary header files for that, and that should be

#include <list>
using namespace std:

// <other stuff>

void FindAdjacentIdentical ( const cha** pMatrix, const size_t szSquareSize,  const Coord c, list<Coord>& lstFound);
0

Commented:
*oops* - that should have been

#include <list>
using namespace std:

// <other stuff>

void FindAdjacentIdentical ( const char** pMatrix, const size_t szSquareSize,  const Coord c, list<Coord>& lstFound);
0

Author Commented:
Ok i tested for a while and change some things, but still have a problem (my fault because I didnt precised it when I ask my question).

Let's say I'm looking for a serie of letters in the grid (a word...), starting from the first letter, the word will always go in one direction and keep that direction. Well let's say the word is "Cumul", my function will find the first letter and returns its coordinates. Then, your function will check the neigbours and return correctly the 'u' since its the next letter we're looking for. Then the 'm'. Then... it gets messy. Since the test for the neigbours are always in the same order, the function will return the first 'u' (to the left of the 'm') and the word is crap...

Do you think there's a quick fix that could prevent that, or I have to make additional tests to find a way to "patch this" ?

Thanks a lot,

Frank
0

Author Commented:
The solution would be to "rememeber" the direction in which we went from starting letter, and continue that way. That would also avoid doing unecessary operations (like checking every neigbours even though we know the way to go...)

Easy to say, but doing it is another thing :S A little help would be really really appreciated !!!!!

0

Author Commented:
Anyone can take a quick look at my problem, it's pretty urgent =(

Thanks guys,

Frank
0

Author Commented:
bump
0

Commented:
Sorry, had to hit the sack :o)

The idea to prevent this from happening would be to 'erase' the entries once they have been found so they won't be found again, e.g.

void FindAdjacentIdentical ( const cha** pMatrix, const size_t szSquareSize,  const Coord c, list<Coord>& lstFound)
{

Coord* p = neigbours;

int x, y;

while ( p->x != 42) {

x = c.x + p->x;
y = c.y + p->y;

// go through the list of adjacent points to find a match
if (  x >= 0 && y >= 0 && x + c.x <= szSquareSize &&  y + c.y <= szSquareSize) {

// found one?
if ( pMatrix[x][y] == pMatrix[c.x][c.y])

Coord cFound;

cFound.x = x;
cFound.y = y;

lstFound.push_back( cFound);

pMatrix[x][y] = '_'; // set entry to an underscore, so it won't be founbd again
}

++p; // move to next entry
}
}
0

Author Commented:
Hi jkr,

your answer would be great if I had to go through the grid one time, but things always have to me more complicated and guess what, I have to fin a list of words in the grid. This way, I can't change the grid item to something else.

I think I have a way to solve the problem, but unfortunately I don't know how to modify the function to do this:

- Get the first letter of the word in the grid [ok]
- Find the second letter of the word in the grid (check the neigbours) [ok]
- Once the second letter of the word and the one from the grid matches, return the current direction (coord of letter2 - letter1) [to do]
- Redo the neigbours checkup with the known direction (this avoid 7 unnecessary tests since we already know the direction) [to do]
- Return true if the word is entirely found, else find another letter in the grid matching the word's first lettter [ok]

To do this, obviously we need to add a paramter to the function - the direction. From now on, I don't have a clue on how to handle the neigbours[]  and don't have much time left to test.

I appreciate so much the help you gave so far, thanks for spending this time helping me and for your patience.

Frank
0

Commented:
>>Redo the neigbours checkup with the known direction

Ahh, getting it - I thought the word could be continued in any direction. It wouldn't be to hard to add that feature, e.g. by tracking the last 'neighbouring' direction, e.g.

// return value is the index to the 'neighbour' where the match was found, that could be passed in again
int FindAdjacentIdentical ( const char** pMatrix, const size_t szSquareSize,  const Coord c, Coord& cFound, int nDirection = -1)
{
int  i = 0;
int nRetVal = -1;

Coord* p = neigbours;

int x, y;

if ( 0 > nDirection) {

x = c.x + neigbours[nDirection].x;
y = c.y + neigbours[nDirection].y;

// found one?
if ( pMatrix[x][y] == pMatrix[c.x][c.y])

cFound.x = x;
cFound.y = y;

}
}

while ( p->x != 42) {

x = c.x + p->x;
y = c.y + p->y;

// go through the list of adjacent points to find a match
if (  x >= 0 && y >= 0 && x + c.x <= szSquareSize &&  y + c.y <= szSquareSize) {

// found one?
if ( pMatrix[x][y] == pMatrix[c.x][c.y])

cFound.x = x;
cFound.y = y;

nRetVal = i;

return nRetVal;
}

++i;
}

++p; // move to next entry
}

return nRetVal;
}

0

Author Commented:
Just had an idea. If I make a copy of your function and call it "findDirection", it could check for neigbours and return the neigbour's coordinates - the searched letter's coordinates. With this, we could easily return the direction.

Then, call the original function with the direction instead of checking every neigbours. This way, for each first letter of a word, we would get the direction and check the direct neigbours of that direction ?

void findDirection(char** pMatrix, char letter, int size,  const Coord c, list<Coord>& lstFound)
{
Coord* p = neigbours;
Coord cFound;
Coord loc_dir;

int x = 0, y = 0;

// Search through the neigbours
while ( p->x != size) {

// A word can be horizontaly on the last line, that's why we test (not sure if this is correct)
// ex. a word can have his first letter on the (gridSize, gridSize) coord can continue to the left
if(x==size-1)
{x = c.x;}
else{x = c.x + p->x;}

// Same thing
if(y==size-1)
{y = c.y;}
else{y = c.y + p->y;}

// go through the list of adjacent points to find a match
if (  x >= 0 && y >= 0 && x <= size &&  y <= size) {

// found one?
if ( pMatrix[x][y] == letter)
{
cFound.x = x;
cFound.y = y;

// Difference between the current letter in the grid and the previous one to get the direction
loc_dir.x = x - c.x;
loc_dir.y = y - c.y;

lstFound.push_back(cFound);

FindAdjacentIdentical (pMatrix, letter, int size,  const Coord c, list<Coord>& lstFound, loc_dir)
return;
}
}

++p; // move to next entry
}
return;
}

bool FindAdjacentIdentical (char** pMatrix, char letter, int size,  const Coord c, list<Coord>& lstFound, const Coord loc_dir )
{
Coord* p = neigbours;
Coord cFound;

int x = 0, y = 0;

// A word can be horizontaly on the last line, that's why we test (not sure if this is correct)
// ex. a word can have his first letter on the (gridSize, gridSize) coord can continue to the left
if(x==size-1)
{x = c.x;}
else{x = c.x + loc_dir.x;}

// Same thing
if(y==size-1)
{y = c.y;}
else{y = c.y + loc_dir.y;}

// go through the list of adjacent points to find a match
if (  x >= 0 && y >= 0 && x <= size &&  y <= size) {

// found one?
if ( pMatrix[x][y] == letter)
{
cFound.x = x;
cFound.y = y;

lstFound.push_back(cFound);
return true;
}
}
return false;
}

Think this could work ?

Frank
0

Author Commented:
sry composed while you were posting
0

Commented:
Never mind :o)

You can do that with just the one function to have it return the 'neighbour index' where the character was found and re-supply it when calling it the next time. I also removed the list, since apparently you expect only one item to be found.
0

Author Commented:
You're right, your function is more efficient.

A couple things I need to understand in it because I don't want this thing to be only a pain, I want to learn from it =)

int nDirection = -1
[...]
if ( 0 > nDirection) {

x = c.x + neigbours[nDirection].x;
y = c.y + neigbours[nDirection].y;

// found one?
if ( pMatrix[x][y] == pMatrix[c.x][c.y])

cFound.x = x;
cFound.y = y;

}
}

- I guess this part is executed once we know the direction of the word in the grid ? But since nDirection is always initialized to -1, won't zero always be greater then nDirection ? (this leads to the calling of the function that I'm not sure to understand)

nRetVal = i;
return nRetVal;

- If we find a matching letter, this is how we return the found direction ? Now if this is it, shouldn't we make a recursive call of the function with the nRetVal as the direction ?

- I'm a little confused on how to call the function...
declaration:  int FindAdjacentIdentical ( const char** pMatrix, const size_t szSquareSize,  const Coord c, Coord& cFound, int nDirection = -1)
call:             FindAdjacentIdentical (array, size, toFind, ?, ?)

array: the grid
size: the size of the grid
toFind: the coord of the first letter of the searched word
?: Coord& cFound, When I'm calling this function for the first time, what is the sent value ?
?: nDirection, do I send something here (the nDirection is declared in the function's header...) ?

Thank you from tthe bottom of my hear, you truly are an expert !

Frank
0

Commented:
>>Iguess this part is executed once we know the direction of the word in the grid ? But since nDirection is always
>>initialized to -1

No, that's a default parameter value that only applies if you don't explicitly pass a direction, i.e. when searching for the 1st time, e.g.

Coord cStart = ...;
Coord cFound;
nDirectionFound = FindAdjacentIdentical (theGrid, gridSize, 'C', cStart, cFound); // here it will be -1

// ...

cStart = cFound;

FindAdjacentIdentical (theGrid, gridSize, 'C', cStart, cFound, nDirectionFound); // here it is set to the last direction found

>>If we find a matching letter, this is how we return the found direction ?

That was the plan :o)

>>Now if this is it, shouldn't we make a recursive call of the function with the nRetVal as the direction ?

That could be done also. Actually, that's not a bad idea, but I did not think of using it like that... I have been assuming that the calling function should have the control on about how to continue the search. IMHO recursions should be avoided, since an endless recursion causes endless trouble...

The 'how to call' thing I hope became clearer by the sample above.

0

Commented:
Oh, BTW, gonna be offline for a few hours, the "real life" is calling. Gonna be back, though :o)
0

Author Commented:
Ok just for a last checkup before I start to test, I'm gonna post the function I'm gonna use. I haven't test your function with the latest changes, so I don't know if my function calling yours handle it correctly, because the return value is an int. This being said, I don't know how to handle if every letters of the word were found... Anyway, here it is:

// The grid is already created. Now we create the words' list to find in the grid
void CreateWordList(char* fileWord)
{
int  size = 0;
// the make_size function returns the size of the array
make_size(fileWord, (unsigned &)size);

// the array that will contains all the words of the list
arrWords = new char* [size];

for (int i = 0; i < size; ++i) arrWords[i] = new char[1024];
// the load_data fills the array with the data from the file

int loc_x = 0, loc_y = 0;
// for each words in the list, we check if they are present in the grid
for (int l=0; l <= size; l++)
if(FindWord(arrWords[l], theGrid, sizeGrid, loc_x, loc_y))
{
cout << "The word if found!" << endl;
arrWords[l] = "" // delete the word from the list
}
}

bool FindWord(char *word, char **array, int size, int loc_x, int loc_y)
{
int len = strlen(word);

// The word can't be only 1 character
if(len>1)
for (int x=0; x < size; x++) {

// we get the current line from the grid
char* line = new char [strlen(array[x])];
line = array[x];

// for each lettter of the line...
for (unsigned int y=0; y <= strlen(array[x]); y++) {
if(line[y] == '\0') break;

// we compare the current word's letter with the grid letter
if (toupper(line[y])!=toupper(word[0])) continue;

// we create a new coordinates for the first letter of the word in the grid
Coord cStart;
Coord cFound;
int cur_x = x;
int cur_y = y;

// assigns the coordinates of the first letter
cStart.x = cur_x;
cStart.y = cur_y;

// get the direction of the word
int nDirectionFound = FindNextLetter(array, size, cStart, cFound);

// for each letter of the word, we try to find the next one
for (int l=1; l<len; l++)  {

list<Coord> lstFound;
Coord toFind;
toFind.x = cur_x;
toFind.y = cur_y;

// **** what's the coorect way to control the loop, since the return value is an int ?
if(FindNextLetter(array, size, toFind, cFound, nDirectionFound) == nDirectionFound)
cout << "the letter is in the same direction" << endl;

if (cur_x<0 || cur_y<0 || cur_x>=size || cur_y>=size) break;
}
}
}
return true;
}

int FindNextLetter( char** pMatrix, int size,  Coord c, Coord& cFound, int nDirection = -1)
{
int  i = 0;
int nRetVal = -1;

Coord* p = neigbours;

int x, y;

if ( 0 > nDirection) {

x = c.x + neigbours[nDirection].x;
y = c.y + neigbours[nDirection].y;

// found one?
if ( pMatrix[x][y] == pMatrix[c.x][c.y])
{
cFound.x = x;
cFound.y = y;
}
}

while ( p->x != 42) {

x = c.x + p->x;
y = c.y + p->y;

// go through the list of adjacent points to find a match
if (  x >= 0 && y >= 0 && x + c.x <= size &&  y + c.y <= size) {

// found one?
if ( pMatrix[x][y] == pMatrix[c.x][c.y])
{
cFound.x = x;
cFound.y = y;

nRetVal = i;
return nRetVal;
}
++i;
}
++p;
}
return nRetVal;
}

Thanks again,

Frank
0

Commented:
>>This being said, I don't know how to handle if every letters of the word were found...

Well, the idea would be to see if you're through with the input strinng. But, you're right, there needs to be a way to determine if anything was found at all, at least I had the idea (when still using the list) to check that for a list size != 0. But, this way, you could evaluate the return value, '-' will mean 'nothing found'.
0

Commented:
Thanx, but why in all the world a "C"? IMHO that's kinda inadequate... :-(
0

Commented:
Since I see you're back posting questions, would you mind answering mine here?
0

## Featured Post

• 13
• 12
Tackle projects and never again get stuck behind a technical roadblock.