Word Search Concepts Covered: The assignment is to write a word searching progra
ID: 3537233 • Letter: W
Question
Word Search
Concepts Covered:
The assignment is to write a word searching program. The program takes as input an NxN square filled with letters, and a list of words. There are words buried in the square, either left to right, right to left, top to bottom, bottom to top, diagonally, and so on. This is best explained by an example dataq file and the output. Suppose that this is the input file:
T A E D Q Q
Z H P N I U
C K E W D I
V U X O F C
B P I R G K
N R T B R B
EXIT
THE
QUICK
BROWN
FOX
Before explaining the program, let me describe the data in more detail. For reading in the square, there is a space after each letter in the square, including the last letter in each row. Looking at the first row, it is "T", then space, then "A", then space, etc and there is a space and a newline character after the last "Q". By reading the first line of data, we can tell that this will be a six-by-six square. With respect to the words, they are just a word followed immediately by a newline character. The words will not contain spaces, numbers, etc.
This is a word searching problem. The words such as "EXIT" are contained in the square, oriented in one of eight ways, including left to right, right to left, diagonally down, etc. The output of the program should be the array with the non-used letters removed. Thus, only the words found are printed. The output should be printed exactly like the input square, but with blanks replacing those letters that are never contained within a word.
Here is the output from the above input file:
T Q
H N U
E W I
X O F C
I R K
T B
The output must be properly formatted. There should be no blank lines before or after the puzzle and each row of the puzzle is followed by a space and then a newline. So in the example above, there WOULD be a space after the Q in the first row of the solution, there is also a space after the space in the last row.
The square will never be larger than 50 by 50, so you can declare an array of that size. The words will never be longer than the width of the square - six in this example.
Your data files to use for this assignment are on the Loki machine:
/home/pcavanaugh/CSCI1840/assignfiles/data1
/home/pcavanaugh/CSCI1840/assignfiles/data2
/home/pcavanaugh/CSCI1840/assignfiles/data3
Make sure to write your program to accept the exact format of the test files. To test, redirect the data file into your program:
cat data1 | ./word_search
or
./word_search < data1
Explanation / Answer
#include <stdio.h>
#include <string.h>
typedef struct data_store
{
char character;
int flag;
}DATA_STORE;
DATA_STORE data1[2500];
typedef struct word_list
{
char word_value[50];
int len;
}WORD_LIST;
WORD_LIST word[50];
void find_word(WORD_LIST* word,char *data2,char* data3, char* data4 ,char* data5,int k,int i,int row_word){
char *string1,*string2,*string3,*string4,*string5;
char *pos1,*pos2,*pos3,*pos4;
int index1=-1,index2=-1,index3=-1,index4=-1;
int len,l,quo,rem,n;
string1=word[k].word_value;
string2=data2;
string3=data3,
string4=data4;
string5=data5;
//printf("%s,%d ,%s ,%s ,%s ,%s ",string1,word[k].len,string2,string3,string4,string5);
if(pos1= strstr(string2,string1)){
index1=pos1-string2;
if(index1!=-1){
len=word[k].len;
for(l=0;l<len;l++){
data1[index1+l].flag=1;
}
}
}
if(pos2= strstr(string3,string1)){
index2=pos2-string3;
if(index2!=-1){
len=word[k].len;
index2=(row_word*(row_word+1))-index2-2;
for(l=0;l<len;l++){
data1[index2-l].flag=1;
}
}
}
if(pos3= strstr(string4,string1)){
index3=pos3-string4;
if(index3!=-1){
len=word[k].len;
quo=index3/(row_word+1);
rem=index3%(row_word+1);
index3=rem*(row_word+1)+(quo);
for(l=0;l<len;l++){
n=index3+(l*(row_word+1));
data1[n].flag=1;
}
}
}
if(pos4= strstr(string5,string1)){
index4=pos4-string5;
if(index4!=-1){
len=word[k].len;
quo=index4/(row_word+1);
rem=index4%(row_word+1);
index4=rem*(row_word+1)+(quo);
index4=(row_word*(row_word+1))-index4-2;
for(l=0;l<len;l++){
data1[index4-(l*(row_word+1))].flag=1;
}
}
}
//printf(" %d,%d,%d,%d",index1,index2,index3,index4);
return;
}
void main(){
//char *pos1,*pos2,*pos3,*pos4;
//int index1=-1,index2=-1,index3=-1,index4=-1;
int i,j,k,m,z,row_word,sqr_size,flag1=0,end=0;
char space,character_temp;
char *data2,*data3,*data4,*data5;
for(i=0,j=0;end!=1;i++)
{
if(scanf("%c",&character_temp)==1)
{
if(character_temp!=' ')
{
data1[i].character=character_temp;
data1[i].flag=0;
if(flag1==0)
scanf("%c",&space);
if(space!=' ' && flag1==0)
{
row_word=j;
flag1=1;
i++;
data1[i].character=space;
data1[i].flag=0;
}
}
else
{
data1[i].character=character_temp;
data1[i].flag=1;
j++;
}
}
else
{
end=1;
}
}
data1[i-1].character=' ';
data1[i-1].flag=1;
//printf(" i:%d,j:%d,row_word:%d ",i,j,row_word);
for(k=0;k<=i-1;k++){
if(data1[k].character==' ')
break;
}
sqr_size=k;
//printf(" %d",sqr_size);
data2=(char *)malloc((row_word*row_word+row_word)*sizeof(char));
data3=(char *)malloc((row_word*row_word+row_word)*sizeof(char));
data4=(char *)malloc((row_word*row_word+row_word)*sizeof(char));
data5=(char *)malloc((row_word*row_word+row_word)*sizeof(char));
for(k=0,m=row_word*row_word+row_word-2;k<row_word*row_word+row_word;k++,m--){
*(data2+k)=data1[k].character;
*(data3+k)=data1[m].character;
}
*(data3+k-1)='';
*(data2+k-1)='';
//printf(" ");
//printf("%s",data2);
//printf(" ");
//printf("%s",data3);
for(k=0,z=0;k<row_word;k++){
for(m=0;m<row_word;m++){
*(data4+z)=*(data2+m*(row_word+1)+k);
z++;
}
*(data4+z)=' ';
z++;
}
*(data4+z-1)='';
//printf(" ");
//printf("%s",data4);
for(k=0,z=0;k<row_word;k++){
for(m=0;m<row_word;m++){
*(data5+z)=*(data3+m*(row_word+1)+k);
z++;
}
*(data5+z)=' ';
z++;
}
*(data5+z-1)='';
//printf(" ");
//printf("%s",data5);
for(k=row_word*row_word+row_word,m=0,z=0;k<i;k++){
if (data1[k].character!=' ')
{
/* code */
word[m].word_value[z]=data1[k].character;
z++;
}
if(data1[k].character==' '){
word[m].word_value[z]='';
word[m].len=z;
m++;
z=0;
}
}
for(k=0;k<m;k++){
//printf("%s,%d ",word[k].word_value,word[k].len);
find_word(word,data2,data3,data4,data5,k,i,row_word);
}
printf(" ");
for(k=0;k<i;k++){
if(data1[k].flag==1)
printf("%c ",data1[k].character);
else
printf(" ");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.