search word puzzle.....please help

[kkjoker]

I am writing a c++ word puzzle. I want to cin the size of 2d array and content array. Then, I want to cin a word to search in four directions as from (i) left to right (E), (ii) right to left (W), (iii) up to bottom (S), or (iv) bottom to up (N). The program will print the starting place and the direction of each word. If no word found, cout<<not found
eg.
//input
6 6
ebzrys
rsygaf
caakce
avcmre
nolnoc
droguz
olcay
//output
olcay at 6, 3, N



I only have a few idea of this program. Can anyone help me to finish the whole program?


void patternSearch(char grid[R][C], string word)
{
// Consider every point as starting point and search
// given word
for (int row = 0; row < R; row++)
for (int col = 0; col < C; col++)
if (search2D(grid, row, col, word))
cout << "pattern found at " << row << ", "
<< col << endl;
}

// Driver program
int main()
{
int i, j, R, C;
char grid[R][C] ;
cin>>R>>C;
for(i=0; i<r;i++)
for(j=0;j<c;j++)
cin>>grid[R][C];


char str[20];
cin>>str;

patternSearch(grid, str);
cout << endl;

}

[D80DSL3A]

The array grid[][] is not declared legally. No dynamic array size declarations. Dimensions must be fixed at compile time.
Once you get that squared away, try the following approach:
For each word to find: eg word = olcay
Go through grid looking for a 1st letter match grid[r][c] == word[0]
Search each direction for the rest of the word, eg for search up:

int k=1;// # of steps taken away from r,c

//    still in grid and another letter matched
while( (r-k >= 0) && grid[r-k][c] == word[k]  )++k;// take another step

// did we find the whole word?
if( word[k] == '\0' )// we found it!! (at r,c in up direction) 

Interesting problem btw. My solution is working for the standard 8 direction search (not the easy 4 direction search you got :), so I know that approach works. It's wasteful, but coding it isn't too hard.

edit: be nice!

[kkjoker]

Here is part of my code to check the direction of word search.
However, not all the case are correct and I can't figure where has problem.
I want to ask anything wrong in this part of code?

    for(int i=row-1;i>=0;i--)
    {
        for(int j=column-1;j>=0;j--)
        {
            for(int k=0;word[k] !='\0' ; k++)
            {
                
                if (length<=column-j && table[i][j+k]==word[k])
                {
                    Same=true;
                    direction = 'E';
                }
                
                else if (length<=row-i && table[i+k][j]==word[k] )
                {
                    Same=true;
                    direction = 'S';
                }
                
                
                else if (length<=j+1 && table[i][j-k]==word[k])
                {
                    Same=true;
                    direction = 'W';
                }
                
                else if (length<=i+1 && table[i-k][j]==word[k] )
                {
                    Same=true;
                    direction = 'N';
                }
                

                else
                {
                    Same=false;
                    break;
                }

[D80DSL3A]

That is algorithmic ally inside out. You're attempting to search in all directions at once.
Search each direction until run off the grid (you're not checking for this) or encounter a match failure.
Then search the next direction, etc..

interesting..
No checking for running off grid, but
You do watch for word[k] !='\0', which isn't necessary because
table[i][j] == word[k] will fail once word[k] = '\0' as there are no '\0' in the grid.

[kkjoker]

I am not sure how to check for running off grid. Can you explain it more? Thanks!

[D80DSL3A]

I must pay closer attention when I post. I see you are checking for running off grid
if (length<=column-j && table[i][j+k]==word[k]) where length = length of search word, right?
I was mainly looking at the checking of all 4 ways at once.
Search each direction all the way, then search the next:

Something more like this?

for(int i=0;i<row;i++)
    {
        for(int j=0;j<column;j++)
        {
            if( table[i][j] == word[0] )// 1st letter match
           {
                   direction = 'E';
                   int k=1;
                   for(k=1;j-k>=0 & table[i][j-k] == word[k] ! ; k++);// just iterate!
                   if( word[k] != '\0' )// didn't find it. Check next direction
                  {
                     direction = 'W';
                      k=1;
                      for(k=1;j+k<columns && table[i][j+k] == word[k] ! ; k++);// just iterate!
                      if( word[k] != '\0' )// still not found
                      // try 'S' and 'N' directions
                  }
                  // check if found                  
                   if( word[k] == '\0' )// found it!
                  {
                     cout << word << " found at " << i << ',' << j << " in direction " << direction;
                     return;// done here
                  }
            }
        }
    }

[JLBorges]

Brute force version, using std::string:

#include <iostream>
#include <string>
#include <vector>
#include <iomanip>

// make all rows of the same width
std::vector<std::string> normalise( std::vector<std::string> table, std::size_t width )
{
    for( std::string& row : table ) row.resize( width, ' ' ) ;
    return table ;
}

// invariant: all rows in the table have the same width
std::string get_col( const std::vector<std::string>& table, std::size_t col_num )
{
    std::string col_str ;
    if( !table.empty() && col_num < table.front().size() )
        for( const auto& row : table ) col_str += row[col_num] ;
    return col_str ;
}

std::size_t find_reverse( const std::string& str, const std::string& substr )
{
    auto pos = std::string( str.rbegin(), str.rend() ).find(substr) ;
    if( pos != std::string::npos ) pos = str.size() - pos - 1 ;
    return pos ;
}

// print with row, column numbers starting at one
void print( const std::string& word, std::size_t row_num, std::size_t col_num, char dir )
{
    std::cout << "word " << std::quoted(word) << " found at " << row_num+1 << ", "
              << col_num+1 << " (" << dir << ")\n" ;
}

// invariant: all rows in the table have the same width
void pattern_search( const std::vector<std::string>& table, const std::string& word )
{
    for( std::size_t row_num = 0 ; row_num < table.size() ; ++row_num ) // check rows
    {
        const std::string& row = table[row_num] ;

        const auto found_lr = row.find(word) ;
        if( found_lr != std::string::npos ) print( word, row_num, found_lr, 'E' ) ;

        const auto found_rl = find_reverse( row, word ) ;
        if( found_rl != std::string::npos ) print( word, row_num, found_rl, 'W' ) ;
    }

    for( std::size_t col_num = 0 ; col_num < table.front().size() ; ++col_num ) // check cols
    {
        const std::string col = get_col( table, col_num ) ;

        const auto found_tb = col.find(word) ;
        if( found_tb != std::string::npos ) print( word, found_tb, col_num, 'S' ) ;

        const auto found_bt = find_reverse( col, word ) ;
        if( found_bt != std::string::npos ) print( word, found_bt, col_num, 'N' ) ;
    }
}

int main()
{
    std::vector<std::string> table = { "ebzrys", "rsygaf", "caakce", "avcmre", "nolnoc", "droguz" } ;
    table = normalise( std::move(table), 6 ) ;
    for( const std::string& row : table ) std::cout << row << '\n' ;
    std::cout << '\n' ;

    for( const std::string word : { "olcay", "aakc", "yrzb", "ercan", "zceef" } ) pattern_search( table, word ) ;
}

http://coliru.stacked-crooked.com/a/a3164f62f556e0ae

[D80DSL3A]

Quite nice. I see it works for the 4 direction search in the given problem, but an 8 way search is just a get_diag() definition away.
Here's my brute force version. I believe yours is more efficient JLBorges, the string::find() won't search short segments for a word that wouldn't fit there, whereas my method does. I iterate off in all 8 directions blindly without checking if there's enough space for the word that way or not.
disclaimer: Other efficiency differences not apparent to me at this time may also be present.

#include <iostream>
#include <string>
#include <vector>
using std::vector;
using std::string;

bool inPuzzle(int x, int xMax, int y, int yMax )
{
    if( x < 0 || x >= xMax ) return false;
    if( y < 0 || y >= yMax ) return false;
    return true;
}

void pattern_search( const vector<string>& puzzle, const string& word )
{
    const int dr[] = { 0, 0,  1, -1, -1, -1, 1,  1 };// 8 search
    const int dc[] = { 1, -1, 0,  0,  1, -1, 1, -1 };// directions
    const vector<string> dir = { "E", "W", "S", "N", "NE", "NW", "SE", "SW" };
    int W = puzzle[0].size(), H = puzzle.size();// puzzle width, height

    for(int r=0; r<H; ++r)// at each space in puzzle
        for(int c=0; c<W; ++c)
            if( puzzle[r][c] == word[0] )// 1st letter match
                for(int n=0; n<8; ++n)// for each direction
                {
                    int k=1;// displacement from r,c
                    while( inPuzzle( c+k*dc[n],W, r+k*dr[n],H) && (puzzle[r+k*dr[n]][c+k*dc[n]] == word[k]) )++k;
                    if( word[k] == '\0' )// found it!
                    {
                        std::cout << word << " found at r = " << r << ", c = " << c << " dir = " << dir[n] << '\n';
                        return;// next i please
                    }
                }// end for each direction

    std::cout << "Couldn\'t find " << word << '\n';
}

int main()
{
    vector<string> puzzle = { "ebzrys", "rsygaf", "caakce", "avcmre", "nolnoc", "droguz" };
    vector<string> word = { "olcay", "aakc", "yrzb", "ercan", "zceef", "mase", "fcml" };// + 2 on diags

    for(size_t i=0; i<word.size(); ++i)// for each clue
        pattern_search( puzzle, word[i] );

    return 0;
}

edit: code to new function pattern_search

Checking for enough space for word in a search direction wasn't hard.
To replace lines 26 - 32 above:

                    const int len = word.size() - 1;
                    if( inPuzzle( c+dc[n]*len,W, r+dr[n]*len,H ) )// room for word this direction
                    {
                        int k=1;// displacement from r,c
                        while( word[k] && (puzzle[r+k*dr[n]][c+k*dc[n]] == word[k]) )++k;// must check word[k] as may go outside puzzle to find '\0'
                        if( word[k] == '\0' )// found it!
                        {
                            std::cout << word << " found at r = " << r << ", c = " << c << " dir = " << dir[n] << '\n';
                            return true;
                        }
                    }

edit: My larger test case:

    vector<string> puzzle =   { "TPIRCSAVAJLEXIPIGE", "LIAMEMORYMMOUSENIL", "CRABKSATXINUYHSTFG", "DNDIRECTORYETAOEOO",
                                "POWERSUPPLYNIRFRLO", "UCOASAEVASSCRETNDG", "KIROPKTYPSHRUWWEEL", "CDDECPREEAHYCAATRM",
                                "ANRIMALLTDRPERREAT", "BOLENMEIEKETSEEPHH", "RCKIPRAFCVRIIRSULM", "EEBEIARRIABOOTMBOR",
                                "NSTWRAPRGRTNWBINGO", "NOOSGNDLOODINTIOIS", "ANGMAKAULARAOTEANR", "CAEASPTLTAIPONRNDU",
                                "SNFIREWALLWREIKOOC", "TFDPRDHTOOTEULBYTE" };// 18x18

    vector<string> word = { "APPLICATION", "BACKUP", "BINARY", "BLUETOOTH", "BOOT", "BYTE", "CHAT", "CLICK", "COOKIE", "CURSOR",
       "DATA", "DEFRAGMENT", "DIRECTORY", "DISKDRIVE", "DOS", "DRAG", "EMAIL", "ENCRYPTION", "FILE", "FIREWALL",
    "FOLDER", "GIF", "GOOGLE", "HTML", "ICON", "INTERNET", "JAVASCRIPT", "KERNAL", "LCD", "LOGIN",
    "MEMORY", "MONITOR", "MOUSE", "NANOSECOND", "NETWORK", "PARTITION", "PASTE", "PDF", "PIXEL", "PROGRAMMER",
    "ROUTER", "SAVEAS", "SCANNER", "SECURITY", "SHAREWARE", "SOFTWARE", "SPAM", "TASKBAR", "THUMBNAIL", "UNIX",
    "WALLPAPER", "WIRELESS", "POWERSUPPLY" };// 53 words 

[JLBorges]

> I believe yours is more efficient JLBorges

No. Both get_col() and find_reverse() create temporary strings.

Though it is probably more programmer-efficient.

Excessive straight-line function length and excessive block nesting depth (e.g., if, for, while, and try blocks) are twin culprits that make functions more difficult to understand and maintain, and often needlessly so.

Each level of nesting adds intellectual overhead when reading code because you need to maintain a mental stack (e.g., enter conditional, enter loop, enter try, enter conditional, ...). Have you ever found a closing brace in someone's code and wondered which of the many fors, whiles, or ifs it matched? Prefer better functional decomposition to help avoid forcing readers to keep as much context in mind at a time.

- Alexandrescu and Sutter in 'C++ Coding Standards: 101 Rules, Guidelines, and Best Practices'