Expert: vijayan - 4/5/2009

Question
recently i came across this question in our campus interview. which i dint clear. they dint gave the solution also for this one.
question :

input:
T X B X
X I S X
C D M D
S W Q E

search string : TIME

output : TIME (1,1,SE)
where 1,1 signify the 1st row and 1st column and SE represents the direction south east.

sir, can you help me out to clear this problem.

Answer
"Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy." - Rob Pike

"When in doubt, use brute force." - Ken Thompson

using brute force:

#include <algorithm>
#include <string>
#include <iostream>

enum { ROWS = 4, COLS = 4 } ;

enum direction { N, NE, E, SE, S, SW, W, NW } ;

const char* const direction_string[] =
               { "N", "NE", "E", "SE", "S", "SW", "W", "NW" } ;

const std::pair<int,int> increment[] =
{
   std::make_pair(0,-1), std::make_pair(+1,-1), std::make_pair(+1,0),
   std::make_pair(+1,+1), std::make_pair(-1,0), std::make_pair(-1,+1),
   std::make_pair(-1,0), std::make_pair(-1,-1)
};

inline bool apply_increment( int& a, int& b, const std::pair<int,int>& incr )
{
    a += incr.first ;
    b += incr.second ;
    return ( a >= 0 ) && ( a < ROWS ) && ( b >= 0 ) && ( b < COLS ) ;
}

void find_it( const char (&grid) [ROWS] [COLS], const std::string& word )
{
  for( int i = 0 ; i < ROWS ; ++i )
      for( int j = 0 ; j < COLS ; ++j )
      {
          for( direction dir = N ; dir <= NW ; dir = direction( dir+1 ) )
          {
               std::string str ;
               int x = i ;
               int y = j ;

               do str += grid[x][y] ;
               while( apply_increment( x, y, increment[dir] ) );

               if( str.find( word ) != std::string::npos )
               {
                   std::cout << word << '(' << i+1 << ',' << j+1 << ','
                             << direction_string[dir] << ")\n" ;
                   return ;
               }
          }
      }
}

int main()
{
   const char grid[ROWS][COLS] =
   {
       { 'T', 'X', 'B', 'X' },
       { 'X', 'I', 'S', 'X' },
       { 'C', 'D', 'M', 'D' },
       { 'S', 'W', 'Q', 'E' }
   } ;
   find_it( grid, "TIME" ) ;
}