Hacker Challenge: Word Search Solver

The word search solver

If you’re an avid newspaper reader or just curious about word games, you must have played the word search game before. Even if you haven’t, there is no need to worry; the animation below gives you a rundown of how the game works:

As you can see above, a word search game consists of an $M \times N$ grid of characters, where the player has to match them horizontally, vertically, or diagonally to form words.

Task

In this lesson, we’ll implement a word search solver. This solver will read an $M \times N$ grid from the file WordGrid.txt and a list of words to find in the grid from the file WordList.txt. For each word the solver reads, it’s supposed to output the index of the starting point and the direction in which the word is formed. If the word doesn’t exist inside the grid in any orientation, then that is printed on the screen.

Example

The widget below shows how the solver is supposed to work:

Your implementation

Understand the format of WordGrid.txt and WordList.txt and write your code in the widget below.

Implementation walkthrough

From here onward, we’ll provide you with a guide on implementing the solution for the word search solver (word solver) that you can follow along in the playground above. The guide contains both an explanation and the implementation of the functions. You should look at the solution if you feel stuck. Best of luck!

The main() function

The WordGrid.txt file contains the number of rows and columns on the first line of the grid, and the remaining file contains the rows of the grid. The WordList.txt file contains a single word on each line with no count of how many total words we have in the file. Therefore, we’ll take the following approach:

• We’ll first read the WordGrid.txt file using the load2DArray() function and load the grid in the WordGrid array.
• Then, we’ll print the WordGrid on the console via the print2DArray() function.
• Since the WordList.txt file doesn’t contain a number specifying the count of words, we’ll read one word, process it, and then repeat this procedure until the file runs out of words. To do this, we’ll do the following:
  • Open an ifstream named wordRdr for the WordList.txt file and declare a char array named word.
  • Then, we use a while loop with the condition wordRdr >> word. This ensures that the word is read from the file and stored inside the word array, and then the loop is executed. If the file runs out of words, the condition will yield false; hence, the loop will be terminated.
  • Inside the loop, we output the word and declare two int variables, rFound and cFound, which represent the starting position of the word found in the WordGrid.
  • Next, we make a call to the findWordOccurrence() function that returns an integer in the range 0-8 (inclusive), where 0 suggests that the word is not found and the other values represent the direction in which the word is found. It is important to note that this function takes the rFound and cFound variables as references (&), hence allowing it to return the starting position of the word that is found.
  • Lastly, we use the printDirectionMsg() function to output the direction and starting point of the word that’s found.

Loading the puzzle-map

The load2DArray() function loads a 2-D array of characters from a file.

Signature

void load2DArray(ifstream & rdr, char Array[][maxCols], int & rows, int & cols);

Parameters

• ifstream & rdr: This is the file stream from where the data is to be read.
• char Array[][maxCols]: This stores the word grid read from the file.
• int & rows: This specifies the number of rows of the word grid read from the file.
• int & cols: This specifies the number of columns of the word grid read from the file.

Implementation details

The implementation for this function is pretty straightforward. We first read the number of rows and columns of the word grid into the rows and columns variables via the >> operator. Then we iterate for said dimensions and, in each iteration, we read one character and store it inside the Array.

Printing the puzzle-map

The print2DArray() function prints the specified array onto the console.

Prototype

void print2DArray(const char MSG[], char Array[][maxCols], int rows, int cols);

Parameters

• const char MSG[]: This specifies the text to be printed before printing the array.

  The use of the keyword const before char in the function parameter const char MSG[] indicates that the function will not modify the array’s contents passed as the argument. This means that the function cannot change the values of the elements within the array.

• char Array[][maxCols]: This contains the word grid.
• int rows: This specifies the number of rows of the word grid.
• int cols: This specifies the number of columns of the word grid.

Implementation details

The implementation for this function is pretty straightforward. First, we simply output the MSG onto the screen via the << operator. Then we iterate for the specified dimensions (rows and columns), where, in each iteration, we output one element of the Array. Lastly, after all elements of a row are printed onto the console, we output two new-line characters (\n) to ensure that we get a grid-like output.

Finding the word occurrence

The findWordOccurrence() function figures out the position of the word and its orientation in the grid.

Prototype

int findWordOccurrence(const char WordGrid[][maxCols], const char word[], 
                        int rows, int cols, int wordSize, 
                            int & rFound, int & cFound);

Parameters

• const char WordGrid[][maxCols]: This contains the word grid.

We use const to ensure that the original data is not accidentally modified. Using const is also helpful in situations where the array is located in a read-only memory and we want to make sure that the function can only read from it and not write to it.

• const char word[]: This contains the word to find.
• int rows: This specifies the number of rows of the word grid.
• int cols: This specifies the number of columns of the word grid.
• int wordSize: This specifies the number of characters in the word.
• int & rFound: This specifies the row of the grid where the word is found.
• int & cFound: This specifies where the word is found in the grid’s column.

Implementation details

The function iterates for all elements of the word grid. In each iteration, it invokes the word finder functions listed in the table below. If any of these functions resolve to true, the findWordOccurrence() function then returns immediately with the appropriate direction int. Otherwise, it returns 0.

Finding a word horizontally (left to right)

The horizontalRt() function checks whether the specified word is in the grid in the horizontal-right orientation at the specified position.

Prototype

bool horizontalRt(const char WordGrid[][maxCols], const char word[], int ri, int ci, 
                    int rows, int cols, int wordSize);

Parameters

• const char WordGrid[][maxCols]: This contains the word grid.
• const char word[]: This contains the word to find.
• int ri: This specifies the row of the grid where the word is found.
• int ci: This specifies the column of the grid where the word is found .
• int rows: This specifies the number of rows of the word grid.
• int cols: This specifies the number of columns of the word grid.
• int wordSize: This specifies the number of characters in the word.

Returns

bool

• True: This is returned when the word is found at the specified index in the word grid.
• False: This is returned when the word is not found at the specified index in the word grid.

Note that the same parameters and return type will be the other seven directions.

Sample output

Word Grid:
-----
-eat-
-----
-----

Word: eat
Found "Horizontal Right" at: [1, 1]

Implementation details

The function first checks whether the wordSize can cause our search to go out of bounds of the grid’s dimensions. Since we have to search in the horizontal-right direction, the ci will increment. Therefore, the last character of the word would supposedly be at the index ci + wordSize - 1. Hence, we place a boundary condition ci + wordSize >= cols which, if it evaluates to true, means that the function will go out of bounds, so we return false. Otherwise, we continue and iterate wordSize number of times and, in each iteration, check whether the characters mismatch. If they do, we return false. So, if all the characters of the word array match with their counterparts in the WordGrid, we return true at the end of the function.

Exercise: Finding a word horizontally (right to left)

The horizontalLt() function checks whether the specified word is in the grid in the horizontal-left orientation at the specified position.

Prototype

bool horizontalLt(const char WordGrid[][maxCols], const char word[], int ri, int ci, 
                    int rows, int cols, int wordSize);

Sample output

Word Grid:
-----
-tae-
-----
-----

Word: eat
Found "Horizontal Left" at: [1, 3]

Since we have already implemented the horizontalRt() function, you can use it as a reference to implement this function. Carefully think about the following while implementing this function:

• Boundary condition(s)
• Iteration step—whether to increment or decrement
• Whether to keep the ri fixed, ci fixed, or both

Finding a word vertically (top to bottom)

The verticalDn() function checks whether the specified word is in the grid in the vertical-down orientation at the specified position.

Prototype

bool verticalDn(const char WordGrid[][maxCols], const char word[], int ri, int ci, 
                    int rows, int cols, int wordSize);

Sample output

Word Grid:
--e--
--a--
--t--
-----

Word: eat
Found "Vertical Down" at: [0, 2]

Implementation details

The function first checks whether the wordSize can cause our search to go out of bounds of the grid’s dimensions. Since we have to search in the vertical-down direction, the ri will increment. Therefore, the last character of the word would supposedly be at the index ri + wordSize - 1. Hence, we place a boundary condition ri + wordSize >= rows which, if it evaluates to true, means that the function will go out of bounds, so we return false. Otherwise, we continue and iterate wordSize number of times and, in each iteration, check whether the characters mismatch. If they do, we return false. So, if all the characters of the word array match with their counterparts in WordGrid, we return true at the end of the function.

Exercise: Finding a word vertically (bottom to top)

The verticalUp() function checks whether the specified word is in the grid in the vertical-up orientation at the specified position.

Prototype

bool verticalUp(const char WordGrid[][maxCols], const char word[], int ri, int ci, 
                    int rows, int cols, int wordSize);

Sample output

Word Grid:
-----
--t--
--a--
--e--

Word: eat
Found "Vertical Up" at: [4, 2]

Since we have already implemented the verticalDn() function, you can use it as a reference to implement this function. Carefully think about the following while implementing this function:

• Boundary condition(s)
• Iteration step—whether to increment or decrement
• Whether to keep the ri fixed, ci fixed, or both

Finding a word diagonally (top-left to down-right)

The diagonalDnRt() function checks whether the specified word is in the grid in the diagonal-down-right orientation at the specified position.

Prototype

bool diagonalDnRt(const char WordGrid[][maxCols], const char word[], int ri, int ci, 
                    int rows, int cols, int wordSize);

Word Grid:
-----
--e--
---a-
----t

Word: eat
Found "Diagonal Down Right" at: [1, 2]

Implementation details

The function first checks whether the wordSize can cause our search to go out of bounds of the grid’s dimensions. Since we have to search in the diagonal-down-right direction, both ri and ci will increment. Therefore, the last character of the word would supposedly be at the indexes ri + wordSize - 1 and ci + wordSize - 1. Hence, we place a boundary condition ri + wordSize >= rows && ci + wordSize >= cols which, if it evaluates to true, means that the function will go out of bounds, so we return false. Otherwise, we continue and iterate wordSize number of times and, in each iteration, check whether the characters mismatch. If they do, we return false. So, if all the characters of the word array match with their counterparts in WordGrid, we return true at the end of the function.

Exercise: Finding a word diagonally (down-right to up-left)

The diagonalUpLt() function checks whether the specified word is in the grid in the diagonal-up-left orientation at the specified position.

Prototype

bool diagonalUpLt(const char WordGrid[][maxCols], const char word[], int ri, int ci, 
                    int rows, int cols, int wordSize);

Sample output

Word Grid:
-----
--t--
---a-
----e

Word: eat
Found "Diagonal Up Left" at: [4, 4]

Since we have already implemented the diagonalDnRt() function, you can use it as a reference to implement this function. Carefully think about the following while implementing this function:

• Boundary condition(s)
• Iteration step—whether to increment or decrement
• Whether to keep the ri fixed, ci fixed, or both

Exercise: Finding a word diagonally (up-right to down left)

The diagonalDnLt() function checks whether the specified word is in the grid in the diagonal-down-left orientation at the specified position.

Prototype

bool diagonalDnLt(const char WordGrid[][maxCols], const char word[], int ri, int ci, 
                    int rows, int cols, int wordSize);

Sample output

Word Grid:
-----
--e--
-a---
t----

Word: eat
Found "Diagonal Down Left" at: [1, 2]

Since we have already implemented the diagonalDnRt() function, you can use it as a reference to implement this function. Carefully think about the following while implementing this function:

• Boundary condition(s)
• Iteration step—whether to increment or decrement
• Whether to keep the ri fixed, ci fixed, or both

Exercise: Finding a word diagonally (down-left to up-right)

The diagonalUpRt() function checks whether the specified word is in the grid in the diagonal-up-right orientation at the specified position.

Prototype

bool diagonalUpRt(const char WordGrid[][maxCols], const char word[], 
                  int ri, int ci, int rows, int cols, int wordSize);

Sample output

Word Grid:
-----
--t--
-a---
e----

Word: eat
Found "Diagonal Up Right" at: [4, 0]

Since we have already implemented the diagonalDnRt() function, you can use it as a reference to implement this function. Carefully think about the following while implementing this function:

• Boundary condition(s)
• Iteration step—whether to increment or decrement
• Whether to keep the ri fixed, ci fixed, or both

Printing the direction

The printDirectionMsg function will print the appropriate message for the word found with its corresponding direction and position.

Prototype

void printDirectionMsg(int dir, int rFound, int cFound);

Parameters

• int dir: This specifies the direction as returned by the findWordOccurrence() function.
• int rFound: This specifies the row of the grid where the word is found.
• int cFound: This specifies the column of the grid where the word is found.

Implementation details

The function simply uses a switch statement to map the dir to an appropriate message.