Word Solver - All Directions

Question

I created a word solver for all directions. It finds words horizontally, vertically and reverse. However, I am having problems making it go all directions. So to take "hello" in:

H  E  i  l
x  L  p  q
c  L  O  m

Anyone can point me on how to do that? Here is my algorithm to that searches for the words (in C++):

/*
 * For loops that search each row, each column in all 8 possible directions.
 */
void Scramble::solve() {

cout << "Output:" << endl;

for (int row = 0; row < getRows(); row++) {
    for (int col = 0; col < getCols(); col++)
        for (int rowDir = -1; rowDir <= 1; rowDir++)
            for (int colDir = -1; colDir <=1; colDir++)
                if (rowDir != 0 || colDir != 0)
                    findWords(row, col, rowDir, colDir);
}
}

/*
 * Finds the matches in a given direction. Also calls verifyWord() to verify that the
 * current sequence of letters could possibly form a word. If not, search stops.
 */
void Scramble::findWords(int startingRow, int startingCol, int rowDir, int colDir) {

int searchResult;
string sequence = "";
sequence = sequence + wordsArr[startingRow][startingCol];

for (int i = startingRow + rowDir, j = startingCol + colDir; i >= 0 && j >= 0
&& i < getRows() && j < getCols(); i = i + rowDir, j = j + colDir) {

    sequence = sequence + wordsArr[i][j];

    if (sequence.length() >= 3) {

        searchResult = verifyWord(words, sequence);

        if ((unsigned int)searchResult == words.size())
            break;

        if (words[searchResult].rfind(sequence) > words[searchResult].length())
            break;

        if (words[searchResult] == (sequence))
            cout << sequence << endl;
    }
}
}

/*
 * Performs the verifyWord search method.
 * Searches the word to make sure that so far, there is possibly that the current sequence
 * of letter could form a word. That is to avoid continuing to search for a word
 * when the first sequence of characters do not construct a valid word in the dictionary.
 *
 * For example, if we have 'xzt', when this search is done it prevents the search
 * to continue since no word in the dictionary starts with 'xzt'
 */
int Scramble::verifyWord(vector<string> words, string str) {

int low = 0;
int mid = 0;
int high = words.size();

while (low < high) {

    mid = (low + high) / 2;

    if (str > words[mid]) {
        low = mid + 1;
    }

    else if (str < words[mid]) {
        high = mid - 1;
    }

    else
        return mid;
}
}

Answer 1

1) Currently, your solve() function looks for a word in a straight line starting at each point: is this what you intend? I only ask because 'hello' doesn't appear as a straight line in your sample matrix:

H  E  i  l
x  L  p  q
c  L  O  m

If you do want straight-line words only, then fine (this is how I've always understood these puzzles to work anyway), but if in fact you want to find words in a snake-wise fashion, then a recursive search like Zilchonum and BlueRaja are suggesting would be a good bet. Just be careful you don't end up looping back on letters you've already used.

2) In either case, your verifyWord() function also has some problems: at the very least it needs to return some value in the case where you exit the while (low < high) loop.

Even so, it still won't quite do what you want it to: for example, say your dictionary contains {"ant", "bat" "hello", "yak", "zoo"}, and you call verifyWord() with str="hel", you'd like to return a value of 2, but at the moment it does this:

step  low   mid  high
 0     0     0     5   // initialise
 1     0     2     5   // set mid = (0+5)/2 = 2... words[2] == "hello" 
 2     0     2     1   // "hel" < "hello" so set high = mid - 1
 3     0     0     1   // set mid = (0+1)/2 = 0... words[0] == "ant"
 4     1     0     1   // "hel" > "ant" so set low = mid + 1     
 5  // now (low<high) is false, so we exit the loop with mid==0

Rather than comparing "hel" with "hello", perhaps you'd be better off truncating the words in the dictionary to the same length as str: ie comparing str to word[mid].substr(0,str.length())?

Answer 2

Here's an interesting way to think about it: finding the word is akin to solving a maze. The 'start' and 'end' correspond to the beginning and end of the word you're looking for, a 'dead end' corresponds to a mismatch between the path and your word, and 'success' is when the string along your path is a match.

The good news here is that there are lots of resources on maze-solving algorithms. One particular algorithm that I'm familiar with, and isn't too difficult to implement, is recursion with backtracking.

Obviously some changes will have to be made in order for this to work for your problem. You don't know where the start is, for example, but luckily it doesn't matter. You can check every possible starting position, and many of them will be discarded on the first step anyway due to a mismatch.

Answer 3

Just treat it like a graph where each letter is connected to all adjacent letters, and do a depth/breadth-first search starting from each letter, only accepting those nodes whose letter is equal to the next letter you're looking for.

Answer 4

This is a simple word sleuth program that i wrote --->

#include<iostream>

using namespace std;

int main()
{
    int a, b, i, j, l, t, n, f, g, k;
    cout<<"Enter the number of rows and columns: "<<endl;               
    cin>>a>>b;                                                              //Inputs the number of rows and columns
    char mat[100][100], s[100];
    cout<<"Enter the matrix: "<<endl;
    for (i = 0; i < a; i++) for (j = 0; j < b; j++) cin>>mat[i][j];         //Inputs the matrix
    cout<<"Enter the number of words: "<<endl;
    cin>>t;                                                                 //Inputs the number of words to be found
    while (t--)
    {
        cout<<"Enter the length of the word: "<<endl;
        cin>>n;                                                             //Inputs the length of the word
        cout<<"Enter the word: "<<endl;
        for (i = 0; i < n; i++) cin>>s[i];                                  //Inputs the word to be found
        for (i = 0; i < a; i++)                                         //Loop to transverse along i'th row
        {
            for (j = 0; j < b; j++)                                     //Loop to transverse along j'th column
            {
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, g++);          //Loop to find the word if it is horizontally right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" right"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, g--);      //Loop to find the word if it is horizontally left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++);      //Loop to find the word if it is vertically down
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--);      //Loop to find the word if it is vertically up
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++, g++); //Loop to find the word if it is down right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down right"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--, g--); //Loop to find the word if it is up left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++, g--); //Loop to find the word if it is down left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--, g++); //Loop to find the word if it is up right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up right"<<endl;
                    goto A;
                }
            }
        }
        A:;                                                             //If the word has been found the program should reach this point to start the search for the next word
    }
    return 0;
}

In my program, it first checks for the first letter of the word, and then the subsequent letters. If the word is found, then it prints the the starting coordinates of the word and the direction in which the word is found.