i created word solver directions. finds words horizontally, vertically , reverse. however, having problems making go directions. take "hello" in:
h e l x l p q c l o m anyone can point me on how that? here algorithm searches words (in c++):
/* * loops search each row, each column in 8 possible directions. */ void scramble::solve() { cout << "output:" << endl; (int row = 0; row < getrows(); row++) { (int col = 0; col < getcols(); col++) (int rowdir = -1; rowdir <= 1; rowdir++) (int coldir = -1; coldir <=1; coldir++) if (rowdir != 0 || coldir != 0) findwords(row, col, rowdir, coldir); } } /* * finds matches in given direction. calls verifyword() verify * current sequence of letters possibly form 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]; (int = startingrow + rowdir, j = startingcol + coldir; >= 0 && j >= 0 && < getrows() && j < getcols(); = + 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 verifyword search method. * searches word make sure far, there possibly current sequence * of letter form word. avoid continuing search word * when first sequence of characters not construct valid word in dictionary. * * example, if have 'xzt', when search done prevents search * continue since no word in dictionary starts '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, solve() function looks word in straight line starting @ each point: intend? ask because 'hello' doesn't appear straight line in sample matrix:
h e l x l p q c l o m if want straight-line words only, fine (this how i've understood these puzzles work anyway), if in fact want find words in snake-wise fashion, recursive search zilchonum , blueraja suggesting bet. careful don't end looping on letters you've used.
2) in either case, verifyword() function has problems: @ least needs return value in case exit while (low < high) loop.
even so, still won't quite want to: example, dictionary contains {"ant", "bat" "hello", "yak", "zoo"}, , call verifyword() str="hel", you'd return value of 2, @ moment 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" set high = mid - 1 3 0 0 1 // set mid = (0+1)/2 = 0... words[0] == "ant" 4 1 0 1 // "hel" > "ant" set low = mid + 1 5 // (low<high) false, exit loop mid==0 rather comparing "hel" "hello", perhaps you'd better off truncating words in dictionary same length str: ie comparing str word[mid].substr(0,str.length())?
Comments
Post a Comment