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;
}
}
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())?