search word in n x n puzzle

[jerryseinfeld]

Hi I am a new c+ student. I can make only simple calculator or find some average number programmes.... But now I have though one for me :( I need a program to find word in nxm puzzle and print its location... words may have been located directions.. I mean (i)left to right E(east) (ii)right to left W(west) (iii) up to bottom S(south) (iv) bottom to up N(north)

I think I am gonna use

char* puzzle[6]={ 
                          "ebzrys",
                          "rsygaf",
                          "caakce",
                          "avcmre",
                          "nolnoc",
                          "droguz"}; 
char* words[5]={"ercan", "olcay", "conlon", "oguz", "cprog"};

output should be like that.....
word ercan at 1, 1 direction S
word olcay at 6, 3 direction N
word conlon at 5, 6 direction W
word ogus 6, 3 direction E
word cprog cant found

I think this is not hard for you but I cant do it :( please help me :(

You need to think about the index positions in your 2d array. How you keep your search function within bounds and how you check for a complete match.

[jerryseinfeld]

Array[rol+1][col]>=Array[rol][col]
Array[rol][col+1]>=Array[rol][col]

is it work for that???

[Infarction]

How would you do it by hand? There's a variety of methods, but here's one you could try to implement:
- search each row for the first letter of the word.
- if the word fits horizontally, see if there's a match (both directions)
- if the word fits vertically, see if there's a match (both directions)

and like iamthwee said, you'll be treating the grid like a two-dimentional array. Try it and see how you do ;)

Erm no. Do you know how to initialise a 2d array?

[jerryseinfeld]

I really dont know :( I am stack in here :(

[jerryseinfeld]

Tnks a lot you really helped me to think way but in code language I stack. for example ıt looks easy if it fits horizantally but how can I find if its vertically???

Oh, do you know what a nested for loop is? You'll definitely need that at some point.

[jerryseinfeld]

Oh, do you know what a nested for loop is? You'll definitely need that at some point.

ok this is 2d array Array[rol][col]

:)but ı am not sure what its that >=

|0|1|2|3|4|5|6|7|8|9| 
  +-+-+-+-+-+-+-+-+-+-+
 0|j|k|a|d
  +-+-+-+-+-+-+-+-+-+-+
 1|
  +-+-+-+-+-+-+-+-+-+-+
 2|
  +-+-+-+-+-+-+-+-+-+-+ 
 3|
  +-+-+-+-+-+-+-+-+-+-+ 
 4|
  +-+-+-+-+-+-+-+-+-+-+
 5|        f
  +-+-+-+-+-+-+-+-+-+-+ 
 6|
  +-+-+-+-+-+-+-+-+-+-+
 7|
  +-+-+-+-+-+-+-+-+-+-+
 8|
  +-+-+-+-+-+-+-+-+-+-+
 9|                z
  +-+-+-+-+-+-+-+-+-+-+

Just treat it as a 2d array, for example 'z' is on row 9 column 8

[Infarction]

Here's how the 2-d indexing works: you've got Array[row][col]. col is the horizontal index, row is the vertical one. So if you want to check for a horizontal match you check from your starting point and add or subtract to col depending on the direction. For a vertical match, it's the same but changing row. Pretty straightforward.

A nested loop is simply a loop inside of another, like this:

for (int i = 0; i < n; i++)
{
  for(int j = 0; j < m; j++)
  {
     // do something in here
  }
}

When you search for 'z' say you do:-

for (int row = 0 ; row <10; row++ )
{
  for (int col =0; col <10; col++)
  {
   if array[row][col] == 'z')
  {
    cout<<"z found";
   }
  }
}

edit* like what infarction said above.

[jerryseinfeld]

you are the best my friends thnx a lot I think I can handle from this thanks lot . hurrayyy :) Now I need to work on it thank you again and again and again :) byes :)

[jerryseinfeld]

Hi I am a new c+ student. I can make only simple calculator or find some average number programmes.... But now I have though one for me :( I need a program to find word in nxm puzzle and print its location... words may have been located directions.. I mean (i)left to right E(east) (ii)right to left W(west) (iii) up to bottom S(south) (iv) bottom to up N(north)

I think I am gonna use

char* puzzle[6]={ 
                          "ebzrys",
                          "rsygaf",
                          "caakce",
                          "avcmre",
                          "nolnoc",
                          "droguz"}; 
char* words[5]={"ercan", "olcay", "conlon", "oguz", "cprog"};

output should be like that.....
word ercan at 1, 1 direction S
word olcay at 6, 3 direction N
word conlon at 5, 6 direction W
word ogus 6, 3 direction E
word cprog cant found

I think this is not hard for you but I cant do it :( please help me :(

sorry guys I stuck again... may be we think wrong.. is that neccesary to think 2d array because we have puzzle[] and word[] we dont have puzzle [] [] ....
and another point is ok we can find z .I mean just one letter... but how we can extract for example "ercan" second letter (r) or we say we find it then third one? how we can say in code in 'words' array's first element 4. letter???
or am I completly wrong way :( :(

>is that neccesary to think 2d array because we have puzzle[]

Hi, if you don't initialise it as a 2d array, you certainly need to treat it like a 2d array - that much is certain.

>and another point is ok we can find z .I mean just one letter... but how we can extract for example "ercan"

Again, think about this as index postions.
You know 'e' was found at 1,1.

'r' was found at 2,1

'c' was found at 3,1

'a' was found at 4,1

'n' was found at 5,1

Can you see a pattern emerging. In programming it's all about patterns. Computer are good at doing repetive things where patterns can be applied.

[jerryseinfeld]

thnx again I need to study on it thanx for helping ......

Hi, I understand how you might assume the below isn't really a 2d array.

char* puzzle[6]={ 
                          "ebzrys",
                          "rsygaf",
                          "caakce",
                          "avcmre",
                          "nolnoc",
                          "droguz"};

After all where is the puzzle[][] bit? But it is.

If you do:-

cout << puzzle[0][0]  you should get 'e'
 cout << puzzle[5][5] you should get 'z'.

Try it and see.

(note: arrays start at [0][0])

So really it is a 2d array.

Another thing is you will eventually realise that you have to make sure your search, i.e north south east west do not go beyond the confines of your arrray. Anyway, I'll let you try what you have so far.

Good luck.

[Infarction]

sorry guys I stuck again... may be we think wrong.. is that neccesary to think 2d array because we have puzzle[] and word[] we dont have puzzle [] [] ....
and another point is ok we can find z .I mean just one letter... but how we can extract for example "ercan" second letter (r) or we say we find it then third one? how we can say in code in 'words' array's first element 4. letter???
or am I completly wrong way :( :(

We have char* puzzle[]. Think about how pointers and arrays are related (hint: you can index a pointer like you can an array). So we can treat puzzle as though it were char puzzle[][].

For finding a word match, you'll have to do similarly. The list of words is char* words[] but you can think of it as char words[wordIndex][letterIndex], if that helps. So the 'r' in ercan would be words[0][1], and the 'z' in oguz would be words[3][3].

[jerryseinfeld]

yes finally I understand that.... now I will make loops to check puzzle[][] and words[][] are same?. if these are same I will find a match... after the loops can I use

if( puzzle[x][y] == words[i][j]){
count................

is that correct? can I use 2d array in """if""" to get same letter?

my other question is puzzle is a 6x6 array
but is the words array 4x5? if it is, when the loop is counting [4][5] what its gonna read? I mean [4] is "cprog" line and it dosent have [5] ???

[jerryseinfeld]

I realy thankfull to you it is until 6 april so until that day any answer anytime wil be helpfull thanks lot :)

[Infarction]

What you have to do is for each item in words, you need to see if the pattern can be found in puzzle. It's not just a matter of checking if words and puzzle are equal. You need to see if the characters in a given word occur in horizontal or vertical order in puzzle. This is going to use nested loops. Here's a general idea of one way to do it for finding one word in a grid (very general pseudo-code):

for each letter in the grid (this would probably be a nested loop)
{
  if it's the beginning of the word
  {
    see if it matches horizontally left or right (this'll need a loop)
      if it matches, return the results
    if not, try to match vertically up or down (this'll need a loop)
      if it matches, return the results
  }
}
if it wasn't found, then the word was not in the grid

Then you could do this for each word.

[WaltP]

You know, I just went through this entire thread and saw absolutely no code by Jerry. How can we help if you won't even try anything suggested, and/or won't post what you've tried?

[jerryseinfeld]

oh, sorry guys I am newcomer here and I really dont know the process... My work is here... I coldnt write because I am little bit shame maybe I think stupid but anyway here is my work.....

#include<stdio.h>
int i,j,x,y;
int main(){
char* puzzle[6]={       
   "ebzrys",
   "rsygaf",
   "caakce",
   "avcmre",
   "nolnoc",
   "droguz"            };
char* words[5]={  
   "ercan",
   "olcay",
   "conlon",
   "oguzr",
   "cprog"            };
for(i=0;i<=5;i++);  {
 for(j=0;j<=5;j++);  {
  for(x=0;x<=4;x++); {
   for(y=0;y<=5;y++);{
if( puzzle[x][y] == words[i][j]){
    printf(" %c is in %d %d \n",words[x-1][y-1],i,j);
     } }}}}
return 0;
}

now here I tried to count puzzle[j] and words[x][y] to match letters.. BUt I coludnt of course. Because I thoght comletly wrong then I saw this morning "Infractin" s work here then I will change it... then I am gonna write here again....

[jerryseinfeld]

you saw my codes now its coming my stupid questions :)
is that wrong to count 4 integers to check puzzle[][] words[][] are there any matches? because with if( puzzle[x][y] == words[i][j]) I only get adresses not same letters.
if I am gonna use if (array[row][col] == 'z') for every letter it would be too long.. How can I extrtact and put into if these letter are there any suggestion loops?

[jerryseinfeld]

my last work but in that point I coludnt any solution and I am completly stack please help :(

#include<stdio.h>
int i,j;
int main(){
char* puzzle[6]={ 
"ebzrys",
"rsygaf",
"caakce",
"avcmre",
"nolnoc",
"droguz" };
char* words[5]={ 
"ercan",
"olcay",
"conlon",
"oguzr",
"cprog" };
for(i=0;i<=5;i++);{
for(j=0;j<=5;j++);{
if(puzzle[i-1][j-1] == 'e'&& puzzle[i][j-1]=='r'){ /* up to down*/
printf("it is %d line up to down\n",i);
return 0;}
else
if(puzzle[i-1][j-1] == 'e'&& puzzle[i-1][j]=='r'){ /* left to right*/
printf("it is %d line left to right\n",i-1);
return 0;}
}}
printf("it wasnt found\n");
return 0;
}

[vijayan121]

one way to do this is
a. pad the matrix with null chars on all four sides.
b. search for the word in each row using strstr.(EAST)
c. rotate the matrix by 90 degrees and repeat (NORTH)
d. rotate the matrix by 90 degrees and repeat (WEST)
e. rotate the matrix by 90 degrees and repeat (SOUTH)

here is the code. in this example, the co-ordinares printed
are in the rotated matrix, (number of rotations are given in
paranthesis).
your task: translate these to the original (unrotated) co-ordinares.

#include <iostream>
#include <cstring>
using namespace std;

enum { WIDTH = 8 };
void rotate( char (&array)[WIDTH][WIDTH] ) // rotate array by 90 degrees anti-clockwise
{
  for ( int i=0, mi=WIDTH ; i < mi-- ; ++i )
    for ( int j=0, mj=WIDTH ; j < mj--; ++j )
    {
      char tmp = array[i][j];
      array[i][j] = array[mj][i];
      array[mj][i] = array[mi][mj];
      array[mi][mj] = array[j][mi];
      array[j][mi] = tmp;
    }
}

int main(int argc, char *argv[])
{
  const char* const puzzle[] =
  {   "ebzrys",
      "rsygaf",
      "caakce",
      "avcmre",
      "nolnoc",
      "droguz"
  };
  const char* const words[]={"ercan", "olcay", "conlon", "oguz", "cprog"};
  const int NWORDS = sizeof(words) / sizeof(*words) ;
  char grid[WIDTH][WIDTH] = { {0} };
  for( int i=0 ; i<WIDTH-2 ; ++i ) strcpy( grid[i+1]+1, puzzle[i] ) ;  
  
  for( int n=0 ; n<5 ; ++n )
  {
    cout << words[n] ;
    char* found = 0 ;
    for( int i=1 ; i<WIDTH-1 ; ++i )
    {
      for( int nrot=0 ; nrot<4 ; ++nrot )
      {
        if( !found && ( found = strstr(grid[i]+1,words[n]) ) )
            // TODO: translate these to the original (unrotated) co-ordinares
            cout << " [" << i << ", " << found-grid[i] << "] 
                                  (" << nrot << " rotations) "  ;
        rotate(grid) ;
      }
    }
    cout << (found ? "" : " not found" ) << '\n' ;
  }
  
  return 0;
}

[jerryseinfeld]

thank you so much I am working on it I am very thankfull but God :) this includes so many unknown code for me :) is it should be that hard??? .... Anyway I will still try thanks...

In short, ignore the previous post, it'll prolly only confuse you. Carry on with how you think you might do it. It looks like you're getting there slowly.

Now what part do you need to do next.

[jerryseinfeld]

sorry I am late but I can say I shouldnt take just one bye one letter from words array... like 'e'.. I think I have to write in a nested loop just you said before... But I can not do that... The last codes were awesome :) I dont know most of them...

[Lerner]

In the OPs recent posts he consistently does this:

for(i=0;i<=5;i++);{
for(j=0;j<=5;j++);{

Unfortunately the semicolon stops the loop before the opening braces become evaluated so they are worthless. If you want to do something in the body of the loop don't have semicolon right after the control statement.

It would also probably be better to leave it as:
char * puzzle[] = { ".....
rather than
char * puzzle[6] = {".....

As indicated in previous posts, the traditional way for the beginning programer to solve this type of problem is to view the puzzle not as an array of strings, but as columns and rows of type char. In OPs post #23 they come reasonably close to doing that by setting up the traditional nested for loops to do this with:

for(i=0;i<=5;i++)  
 for(j=0;j<=5;j++)  
  for(x=0;x<=4;x++) 
   for(y=0;y<=5;y++)

If that were changed to:

for(i = 0; i <= 5; i++) //controls current word from words 
  for(x = 0; x < 6; x++) //controls row of current char from puzzle
    for(y = 0; y <= 6; y++) //controls column of current char from puzzle.

Then implementation could proceed something like this:

for(i = 0; i <= 5; i++) 
  determine length of curent word
  for(x = 0; x < 6; x++) 
    for(y = 0; y <= 6; y++)
      if look left or 
      look right or 
      look up or 
      lood down 
        found equal true
   
    if found
     out put word and x and y.

where the 4 look right/left/up/down lines are functions that return boolean results called within the if conditional. Each function would check to see if current word could fit going the given direction based on size of word and current row or column position. If it doesn't fit return false. If it does fit check first letter of word versus current letter of puzzle. If it's the same check second letter versus next letter in puzzle going whichever direction the function is named, etc. If all letters in current word match puzzle going current direction return true. At first mismatch going in any direction the function can return false.