The Problem Given an input dictionary read in from a file to use for all test ca

Question

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 first line of the input file will contain a single positive integer, c (c S 10), 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 Srs 300, and c (4 S c S 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 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 ut any string that isn't in the dictiona should not ou ut any valid word that does or ou 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. Sam Sample Out e Input ut (usin osted dicational txt Words Found Grid #1 4 4 trap syrt part gtrp Cats faaq Words Found Grid #2 swing prtr C 5 6 wing swingh letter abcdef rettel ayzg fd cmtydh. 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.

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define listlength 149256
#define maxWordLen 19

char** getWords(int rows, int cols);
void freeArray(char** array, int rows);
char** makeGridArray(int rows, int cols);
int binsearch(char** dictionary, char** puzzle, int low, int high);
char wordSearch(char** dictionary, char** puzzle, int row, int col);
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};

int main(){

//read in dictionary
int i,j,x=0, numCases, gridRow, gridCol;
char** words = getWords(listlength, maxWordLen);

//Get number of cases.

printf("enter number of cases: ");
scanf("%d", &numCases);

//process each case.

while(x < numCases){

scanf("%d%d",&gridRow,&gridCol);

//make word search grid
char** grid = makeGridArray(gridRow+1, gridCol);

/* for testing if grid is storing properly

for(i=0; i<gridRow+1;i++){
printf("%s ",grid[i]);
}

*/
printf("Words Found Grid #%d:",x+1);
wordSearch(words, grid, gridRow+1, gridCol);
x++;
freeArray(grid,gridRow+1);
}
freeArray(words, listlength);

}

char** getWords(int rows, int cols){

int i;

//allocate top level of pointers.
char** words = malloc(sizeof(char*)*rows);

//allocate each individual array
for(i=0; i<rows; i++){
words[i] = malloc(sizeof(char)*cols+1);
}

//read dictionary.txt
FILE *dictionary = fopen("dictionary.txt", "r");
for(i=0; i<rows; i++){
fgets(words[i], cols+1,dictionary);
}

fclose(dictionary);
return words;
}

char** makeGridArray(int rows, int cols){

//allocate top level of pointers.
char** grid = malloc(sizeof(char*)*rows);
int i,j;

//allocate each individual array
for(i=0; i<rows;i++){
grid[i] = malloc(sizeof(char)*cols+1);
}
//read in user input grid
for(i=0;i<rows;i++){
gets(grid[i]);
}
return grid;
}

int binsearch(char** dictionary, char** puzzle, int low, int high){

int mid;

if(low == 0 && high == 0){
return 0;
}

mid = (low+high)/2 ;

if(strcmp(*puzzle,dictionary[mid]) == 0){
//found a match
return 1;
}

else if(strcmp(*puzzle,dictionary[mid]) > 0){
//check upper half
return binsearch(dictionary,puzzle,mid+1,high);
}

else if(strcmp(*puzzle,dictionary[mid]) < 0){
//check lower half
return binsearch(dictionary,puzzle,low,mid-1);
}
else return 0;

}

char wordSearch(char** dictionary, char** puzzle, int row, int col){

int i, X, Y, dir = 0;
char* wordsfound[20]= {''};
for (X=0;X<row+1;X++){
for(Y=0;Y<col;Y++){
for(dir=0;dir<DX_SIZE;dir++) //check every direction
for(i=0;i<19;i++){
//will continue in direction DX,DY starting at x,y
int nextX = X + DX[dir] * i;
int nextY = Y + DY[dir] * i;
if(nextX < 0 || nextX >= row) break; //keep in bounds
if(nextY < 0 || nextY >= col) break;
//store the string of letters
wordsfound[i] = (puzzle[nextX][nextY]);
   //wordsfound[i+1] = '';
if(i>2){ //minimum word is 3
//if the string of letters is actually a word, print
int bin = binsearch(dictionary,&&wordsfound,1,listlength);
if(bin){
printf("%s ",wordsfound);
}
}
}
}
}

}

void freeArray(char** array, int rows){
//free arrays
int i;
for(i=0; i<rows; i++){
free(array[i]);
}
free(array);
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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