?
Solved

Searching duplicates in a 2d matrix

Posted on 2005-02-24
27
Medium Priority
?
286 Views
Last Modified: 2010-04-01
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
Comment
Question by:The_Kingpin08
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 13
  • 12
27 Comments
 
LVL 86

Expert Comment

by:jkr
ID: 13399388
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 Comment

by:The_Kingpin08
ID: 13399606
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 Comment

by:The_Kingpin08
ID: 13399614
array should be theGrid in the previous post's function
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 86

Expert Comment

by:jkr
ID: 13399729
>>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;

FindAdjacentIdentical (theGrid, gridSize, 'C', lstFound);
0
 
LVL 86

Expert Comment

by:jkr
ID: 13399735
Ooops, that should have been

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

Author Comment

by:The_Kingpin08
ID: 13399822
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
 
LVL 86

Expert Comment

by:jkr
ID: 13399852
>>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
 
LVL 86

Expert Comment

by:jkr
ID: 13399889
*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 Comment

by:The_Kingpin08
ID: 13400521
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 Comment

by:The_Kingpin08
ID: 13400576
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 !!!!!

Thanks for your precious time.
0
 

Author Comment

by:The_Kingpin08
ID: 13400680
Anyone can take a quick look at my problem, it's pretty urgent =(

Thanks guys,

Frank
0
 

Author Comment

by:The_Kingpin08
ID: 13402569
bump
0
 
LVL 86

Expert Comment

by:jkr
ID: 13403406
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 Comment

by:The_Kingpin08
ID: 13407181
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
 
LVL 86

Expert Comment

by:jkr
ID: 13407506
>>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 Comment

by:The_Kingpin08
ID: 13407525
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 Comment

by:The_Kingpin08
ID: 13407533
sry composed while you were posting
0
 
LVL 86

Expert Comment

by:jkr
ID: 13407551
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 Comment

by:The_Kingpin08
ID: 13407705
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
 
LVL 86

Expert Comment

by:jkr
ID: 13407793
>>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
 
LVL 86

Expert Comment

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

Author Comment

by:The_Kingpin08
ID: 13408407
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
      load_data(arrWords, size, fileWord);
            
      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
 
LVL 86

Accepted Solution

by:
jkr earned 1500 total points
ID: 13408733
>>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
 
LVL 86

Expert Comment

by:jkr
ID: 13531549
Thanx, but why in all the world a "C"? IMHO that's kinda inadequate... :-(
0
 
LVL 86

Expert Comment

by:jkr
ID: 13548595
Since I see you're back posting questions, would you mind answering mine here?
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

764 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question