Word Search Dynamically allocated memory in C !!

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 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.

output each valid word once .

output these words in alphabetical order.

Tips :

I: Reading in the Dictionary Write a program that opens the file "dictionary.txt", which stores the dictionary in the format givenin the assignment and read the dictionary into an array of strings. Your program should then printthe dictionary in reverse order (to double check that it was really read in correctly.)

II: Binary Searching for a string in the Dictionary Add the code for this program to the end of the previous one. After reading in the dictionary, askthe user to enter a word and then have your program print out if the word is in the dictionary ornot. Make sure your program implements a binary search and not a linear search.

You should write a function for your binary search with the function signature shown below: int inDictionary(char** words, int numWords, char* searchWord); The function should return true if searchWord appears in the array words and false otherwise.numWords must equal the number of strings in the array words.

III: Write a function which finds a string of a particular length in a particulardirection from a particular start point in a word search grid. The function should return thatstring, null terminated. For this problem, please use the following DX, DY arrays: const int DX[] = {-1,-1,-1,0,0,1,1,1};const int DY[] = {-1,0,1,-1,1,-1,0,1};

Your function should take in the following parameters:

1) char** grid for the word search grid

2) int numRows for the number of rows in the word search grid

3) int numCols for the number of columns in the word search grid

4) int x, for the value of the row number of the starting spot

5) int y, for the value of the column number of the starting spot

6) int len, for the length of the string desired

7) int dir, for the integer direction (based on DX, DY) that we want to move to build our word.

Your function should return a char*, a single string that is dynamically allocated (so it can persistafter the function completes.)

For example, if the grid inputted was:

twttdad

ghsadfb

yaedcad

utbrdtf

abcdeth

Then here are a few function calls and what they should return:

Function Call Return String formString(grid, 5, 7, 3, 2, 3, 0) "bag"

formString(grid, 5, 7, 3, 2, 4, 1) "best"

formString(grid, 5, 7, 3, 4, 3, 2) "dab"

formString(grid, 5, 7, 4, 5, 3, 3) "ted"

formString(grid, 5, 7, 1, 2, 3, 4) "sad"

formString(grid, 5, 7, 1, 6, 3, 5) "bad"

formString(grid, 5, 7, 1, 1, 3, 6) "hat"

formString(grid, 5, 7, 0, 0, 5, 7) "there"

This task requires no dictionary. But one key element is that it requires careful use of the DX, DYarray, dynamic memory allocation for the single string to be returned and placing a null character('\0') at the end of the string before returning it. Your program should read the grid from standardinput, a starting position, a length and a direction, and print out the appropriate string to the screen.

Finally : Print out EVERY string of EVERY LENGTH (4-19) from a specified startingposition in a grid. This program should simply call the function written for the third task multiple times. Yourprogram should ask the user just to enter a starting location in the grid and then should print outevery string of a valid length that can be formed searching in any direction from that position. Be very careful not to do array out of bounds accesses on the grid. (The function you write for thistask should take in 5 parameters: the grid, its dimensions and the start location for each string.)

For example, the function call printWords(grid, 5, 7, 0, 0) should print the followingfor the grid shown above:

twtt

twttd

twttda

twttdad

tgyu

tgyua

ther

there

Sample Input Sample Output (using 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