A common game in newspapers is a word search. You are given a grid of letters an

Question

A common game in newspapers is a word search. You are given a grid of letters and must find
words that appear in the grid. If you can choose the starting letter of the word within the grid,
and then go in one of the 8 possible directions (up, diagonal up and right, right, diagonal down
and right, down, diagonal down and left, left, diagonal up and left) and spell out the word exactly
as you go by each letter, then the word is in the grid. Here is an example of a partially solved
word search:
In a typical word search, you are given a list of words, each of which can be found in the grid. In
this example, we can see that the word "TWIZZLERS" appears starting in the last row and first
column, going along the up and left diagonal. We can find "PAYDAY" starting on the 5th row
and 6th column, going left.
Obviously, solving a word search is very time consuming. You've decided to use your
programming skills to very quickly solve word searches so that you can impress your friends
with your "vision"!
Programming Tip: DX and DY arrays
In many programming applications, one must start in some location on a two dimensional grid
and then they must move in one of several directions. In terms of coding, it would be nice if one
could simply "loop" through each of the possible directions in a seamless manner. The best way
to do this is to define constants that store each of the possible directions of movement. For this
program, these constants look like the following:
const int DX_SIZE = 8;
const int DX[] = {-1,-1,-1,0,0,1,1,1};
const int DY[] = {-1,0,1,-1,1,-1,0,1};
These should be defined before main, where constants are typically defined.
Now, if we are currently at a spot (x,y), we can move to each of the adjacent locations as
follows:
for (i=0; i<DX_SIZE; i++) {
int nextX = x + DX[i];
int nextY = y + DY[i];
// (nextx, nexty) represents the adjacent location in
// direction i.
}
For this assignment adjustments will have to be made to this framework, but the overarching idea
is very, very useful as it avoids an if statement with 8 branches which is very, very error prone.
In this framework, the logic has to be written once and the DX and DY arrays have to be double
checked, that's it!
Dictionary Information and Binary Search
Before the program processes any word search grids, your program should load in the dictionary
from the file, dictionary.txt. The first line of this file will have a single positive integer, n,
representing the number of words in the dictionary. The words follow on the next n lines, one
word per line. Each word will only contain lowercase letters and be in between 4 and 19 letters
long, inclusive.
It is recommended that you use a binary search to see if a particular string is in the dictionary. If
you use a linear search, your program will not earn full credit.
The Problem
Given an input dictionary read in from a file to use for all test cases, and several word search
grids, identify all words from the dictionary that appear in each word search grid.
The Input (of word search grids, to be read in from standard input)
The first line of the input file will contain a single positive integer, c (c 100), representing the
number of input cases. The input cases follow, one per line. The first line of each input case will
contain two positive integers, r (4 r 300), and c (4 c 300), representing the number of
rows and columns, respectively, in the word search grid. The following r lines will contain
strings of exactly c characters, all of which will be lowercase letters for each row of the word
search grid for that input case.
The Output
For each case, output a header with the following format:
Words Found Grid #k:
where k is the grid number starting with 1. (Please pay attention to the capitalization above,
the pound sign and the colon. You will lose a small amount of credit if you don't use this
exact format.)
Output all the words from the dictionary found in the grid on the following lines, one per line.
You may output these in any order and you may output the same word more than once, but you
should not output any string that isn't in the dictionary, or output any valid word that does
not appear anywhere in the grid. I will assign a small amount of extra credit if you can only
output each valid word once and another little bit of extra credit if you output these words in
alphabetical order. You can only get the extra credit if your solution is 100% correct.
Sample Input Sample Output (using posted dicationary.txt)
2 Words Found Grid #1:
4 4 trap
syrt part
gtrp cats
faaq Words Found Grid #2:
pmrc swing
5 6 wing
swingh letter
abcdef
rettel
ayzgfd
cmtydh
Specification Details
You must use dynamic memory allocation to store the input dictionary and each individual word
search grid. You must free your memory appropriately. You must read the input dictionary from
the file dictionary.txt, which will be posted online.
Deliverables
Please turn in a single source file, wordsearch.c, with your solution to this problem via
Webcourses before the due date/time for the assignment. Make sure that your program reads the
puzzles from standard in and outputs all information to standard out, as previously shown in lab.
Note that the dictionary will be read in from a file.

Explanation / Answer

First solution - Recursion + Binary Search:

In this approach, we recurse (using backtracking) through the board and generate all possible words. For each word that are three or more letters long we check to see if it's in the dictionary. If it is, we have a match!

Here is the algorithm steps:

1. Read in the dictionary in to a container in memory.
2. Sort the dictionary.
3. Using backtracking, search the board for words.
4. If a word is found and it contains 3 or more letters, do a binary search on the dictionary to see if the word is there.
5. If searching was successful in the previous step, print the letter out.
6. Continue step 3-5 as long as there are more words to construct on the board.

-------------------------------------------

Second Solution - Pruned Recursion + Prefix Tree (also known as a Trie):

From the previous approach, our major concern was the enormous search space on the board. Fortunately, using a a prefix tree or trie data structure we could significantly cut down on this search space. The reasoning behind this improvement is that, if a word "abc" does not occur as a prefix to any word in the dictionary there is no reason to keep searching for words after we encounter "abc" on the board. This actually cut down the run time a lot.

Here is the algorithm steps:

1. Read a word from the dictionary file.
2. Insert it into a prefix tree data structure in memory.
3. Repeat steps 1-2 until all words in the dictionary have been inserted into the prefix tree.
4. Using backtracking, search the board for words.
5. If a word is found and it contains 3 or more letters, search the prefix tree for the word.
6. If searching was *not* successful in the previous step, return from this branch of the backtracking stage. (There is no point to continue searching in this branch, nothing in the dictionary as the prefix tree says).
7. If searching was successful in step 5, continue searching by constructing more words along this branch of backtracking and stop when the leaf node has been reached in the prefix tree. (at that point there is nothing more to search).
8. Repeat steps 4-7 as long as there are more words to search in the backtracking.

-------------------------------------------------------------

Third and Final Solution - No search space + Dynamic Programming:

The 2nd approach mentioned above was good enough until the board size was 5. Unfortunately with a board size of 6, that too was taking forever to complete!





It turns out, we can use a nifty dynamic programming technique to quickly check whether a word (from the dictionary in this case) can be constructed from the board or not!

Here is core point of the dynamic programming idea:


For a word of length k to be found (end location) at the [i, j]-th location of the board, the k-1'th letter of that word must be located in one of the adjacent cells of [i, j].



The base case is k = 1.

A letter of length 1 will be found (end location) in the [i, j]-th cell of the board of the only letter in the word matches the letter in the [i, j]-th location of the board.

Once our dynamic programming table is populated with the base case, we can build on top of that for any word of length k, k > 1.

Here is a sample code for this:

for (k = 2; k < MAX_WORD_LENGTH; ++k)
    for (i = 0; i < N; ++i)
        for (j = 0; j < N; ++j)
            if (board[i][j] == word[k])
            {
                 for all the "adjacent" cells of board[i, j]
                     if we table[k-1][adjacent_i][adjacent_j] is true
                         then table[k][i][j] = true;
             }

--------------------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.