Trying to complete a wordsearch solver

[froseph]

Been trying for a while now to complete a physics degree first year computing task I've been assigned, which is to create a wordsearch solver to read to an array a wordsearch from a .txt file and find words in all directions (x+,x-y+ etc.).

I have a feeling the program is almost complete, but will stop looking for the word once the first character of the word has already come up. For example, if I'm searching for computer, and a c exists in an array element before it, the program will stop searching.

I have included my code and the wordsearch file beneath, any help in fixing this problem would be greatly appreciated.

#include <stdio.h>#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h> //Used for the'toupper' function


int main()
{
    int a,X,Y,i,length;
    char array[26][26], string[50];
    /* Above defines the 26X26 array in which to fit the wordsearch
       as well as a search string of length 50 (more than enough to search for words within the wordsearch) */
    printf("WORDSEARCH SOLVER - PRESS CTRL-C TO QUIT\n\n");
    FILE *wsearch=fopen("computerwordsearchdata.txt","r");
    if (wsearch!=NULL) //Checking file eXists/opens correctlY
    {
        for (Y=0; Y<26 ;Y++)
        {
            for(X=0;X<26;X++)
            {
                fscanf(wsearch,"%c\n",&array[Y][X]); //Inputting each character into array
                array[Y][X]=toupper(array[Y][X]);
            }
        }
        fclose(wsearch);
        for (Y=0;Y<26;Y++)
        {
            for (X=0;X<26;X++)
            {
                printf("%c",array[Y][X]); //Printing output to screen
            }
            printf("\n");
        }
        printf("\nPlease enter the word to be searched:\n");
        fgets(string,50,stdin); //Using the fgets function to read in the string from keyboard - prevents buffer overflow
        for(i=0;string[i]!='\0';i++)
        {
            string[i]=toupper(string[i]); //Converts string all into uppercase to prevent errors
        }
        length=strlen(string);
        for (Y=0;Y<26;Y++)
        {
            for(X=0;X<26;X++)
            {
                if(array[Y][X]==(string[0]))
                {
            printf("\nLetter 1 of %sis found at %d,%d\n",string,X,Y);
        //Success in finding first letter of string - Now trY in other directions
        if (array[--Y][X]==string[1])
        {
            //Success in finding in Y+ direction
            printf("Letter 2 of %sis found at %d,%d",string,X,Y);
            for (a=2;a<length;a++)
            {
                if (array[--Y][X]==string[a])
                    printf("\nLetter %d of %sis found at %d,%d",a+1,string,X,Y);
            }
            printf("\n\nWord found in Y+ direction");
            break;
        }
        else if (array[Y][++X]==string[1])
        {
            //Success in finding in Y+X+ direction
            printf("Letter 2 of %sis found at %d,%d",string,X,Y);
            for (a=2;a<length;a++)
            {
                if (array[--Y][++X]==string[a])
                    printf("\nLetter %d of %sis found at %d,%d",a+1,string,X,Y);


            }
            printf("\n\nWord found in Y+X+ direction");
            break;
        }
        else if (array[++Y][X]==string[1])
        {
            //Success in finding in X+ direction
            printf("Letter 2 of %sis found at %d,%d",string,X,Y);
            for (a=2;a<length;a++)
            {
                if (array[Y][++X]==string[a])
                    printf("\nLetter %d of %sis found at %d,%d",a+1,string,X,Y);
            }
            printf("\n\nWord found in X+ direction");
            break;
        }
        else if (array[++Y][X]==string[1])
        {
            //Success in finding in X+Y- direction
            printf("Letter 2 of %sis found at %d,%d",string,X,Y);
            for (a=2;a<length;a++)
            {
                if (array[++Y][++X]==string[a])
                    printf("\nLetter %d of %sis found at %d,%d",a+1,string,X,Y);
            }
            printf("\n\nWord found in X+Y- direction");
            break;
        }
        else if (array[Y][--X]==string[1])
        {
            //Success in finding in Y- direction
            printf("Letter 2 of %sis found at %d,%d",string,X,Y);
            for (a=2;a<length;a++)
            {
                if (array[++Y][X]==string[a])
                    printf("\nLetter %d of %sis found at %d,%d",a+1,string,X,Y);
            }
            printf("\n\nWord found in Y- direction");
            break;
        }
        else if (array[Y][--X]==string[1])
        {
            //Success in finding in X-Y- direction
            printf("Letter 2 of %sis found at %d,%d",string,X,Y);
            for (a=2;a<length;a++)
            {
                if (array[++Y][--X]==string[a])
                    printf("\nLetter %d of %sis found at %d,%d",a+1,string,X,Y);
            }
            printf("\n\nWord found in X-Y- direction");
            break;
        }
        else if (array[--Y][X]==string[1])
        {
            //Success in finding in X- direction
            printf("Letter 2 of %sis found at %d,%d",string,X,Y);
            for (a=2;a<length;a++)
            {
                if (array[Y][--X]==string[a])
                    printf("\nLetter %d of %sis found at %d,%d",a+1,string,X,Y);
            }
            printf("\n\nWord found in X- direction");
            break;
        }
        else if (array[--Y][X]==string[1])
        {
            //Success in finding in X-Y+ direction
            printf("Letter 2 of %sis found at %d,%d",string,X,Y);
            for (a=2;a<length;a++)
            {
                if (array[--Y][--X]==string[a])
                    printf("\nLetter %d of %sis found at %d,%d",a+1,string,X,Y);
            }
            printf("\n\nWord found in X-Y+ direction");
            break;
        }
        else
        {
            //If word is not found in any direction
            printf("Word not found.");
            break;
        }
                    }
            }
            break;
        }


    } //End of file opening correctly process
    else //If file does not open correctly
    {
        printf("File not found"); //Shows when file is not in folder
    }
    printf("\n");
    return 0;
}

computerwordsearchdata.txt - Wordsearch .txt file

Thanks in advance

[Adak]

I'm looking at the wordsearchdata.txt file, and would like to check if it's correctly formatted. It shows no newlines - so just ONE very long line of text?

Should this be one block of letters, with each row ending at the space at the 27th char?

So

Mniparogocomputerhardwarey
woieeoonodsmecivedegarotsp
esdfnidpctatrtnytrrrorcreo 
ggimtnatosotmdroeoamupeuci

etc.

In line 35 of your code, you have input via fgets(), and never remove the newline char that fgets puts at the end of your input:

fgets: in string[]= word\n\0. You need to remove the \n

Instead of using all these if statements, why not have the search continue in a vector, as long as the next letter matches the target's next letter? A while loop would do that for you.

[froseph]

I believe so, at least that's how I interpreted it - The .txt file was provided for us to use

[Adak]

Yes, that's the only way it makes sense, if an 8 direction search is to be made.

if(string[strlen(string)-1]=='\n'
   string[strlen(string)-1]='\0';

will overwrite your newline in the string input. Then re-check your code. I prefer while loops, but there's always more than one way to do things.

[froseph]

Thanks for the prompt replies, and for fixing the string newline issue - I'm a real beginner at this, had no idea that a newline indicator was placed at the end of a string upon its creation. I have experimented with implementing while loops to go through the search, but always end up in loops that I can't the program can't get out of, with no real result in finding the word - Is it possible to initiate the search (line 47 onwards) using a while loop and continue with else if loops?

[Adak]

Keep trying your if loops, as long as you think it's fruitful. That's the exercise. Note that scanf() doesn't add the newline (it's left in the keyboard buffer). Both can be a pain, but you just have to get used to dealing with 'em. gets() is nice but simply TERRIBLE to use, because of it's lack of security (and now it's been deprecated out of the standard)

I have a big work unit going back to Stanford in a few minutes. I will be off the net for about an hour. Back in 60.

[froseph]

Ah okay, that makes more sense. Really appreciate the help for the moment, thanks very much.

[oogabooga]

It's better to handle the file-not-found error right away instead of handling it 145 (!) lines away. Something like this:

    fin = fopen(INPUT_FILE, "r");
    if (fin == NULL) {
        fprintf(stderr, "Error: cannot open %s\n", INPUT_FILE); 
        exit(EXIT_FAILURE);
    }

It also allows you to remove an indentation level.

You shouldn't have the \n in your fscanf format specifier. In fact, it's kind of pointless to use fscanf at all to read single characters when fgetc will do. Also, you're not skipping the space character at the end of each "line".

It would be useful to null-terminate the lines so that you can easily print out the matrix to check that it was read properly. This would require adding one to the column size of "array" and assigning '\0' to column 26. Speaking of 26, it's better to use a define for such numbers.

"array" is not a very good name as it gives no information about what it's for. "puzzle" would be better. And using uppercase for the variables X and Y is a little unusual. Lowercase is preferred. All-uppercase is usually used for macro names.

[anduril462]

Everything that has been said so far is good advice. The only improvements/changes I might make is:
Adak's method to remove the new line results in 2 calls to strchr, which is unnecessarily inefficient. Other options:

size_t len = strlen(string);
if (string[len - 1] == '\n') {
    string[len - 1] = '\0';
}
// my preference
char *p = strchr(string, '\n');
if (p) {
    *p = '\0';
}

Also, oogabooga gave you great advice, #define a constant instead of using a literal 26 everywhere. To expand, you should avoid all magic numbers. Always use (well named) constants. That means 26 should become something like GRID_SIZE and 50 should become something like MAX_INPUT (though 50 is small for an input buffer -- users suck at providing reasonable input). Not only do such constants improve readability, they make your program easier to modify, should you want to change the size of your word search grid later. Note that MAX_INPUT should be large enough to handle "any" input. Realistically that probably means a few hundred characters, so use BUFSIZ (defined in stdio.h, guaranteed to be at least 256). Consider that it makes no sense to allow a word to search for that is longer than any dimension of the grid, so you should check the input the user provide, and make sure it's no larger than GRID_SIZE.

Another thing to note: you have 166 lines all in your main function. You should use a helper function. In fact, this problem is an excellent example of when to use recursion and backtracking. It can probably be reduced by close to 100 lines. Notice how the body of each if/else-if from line 49-146 is virtually identical? Think about how you can make this a recursive function that takes a starting location, a direction to check, and the remainder of the string to look for.

EDIT:
Good job using fgets for the input, and on handling different cases (using toupper). However, if you read the documentation for fgets, it retains the newline (from when the user pressed enter). Remove it with following strchr trick. Also note, I use sizeof as the length parameter, so if you change the size of the input buffer, you only need change MAX_INPUT, no other lines need change:

char string[BUFSIZ];
char *p;
fgets(string, sizeof(string), stdin);
p = strchr(string, '\n');
if (p) {
    *p = '\0';
}

Note, you could wrap the check for newline and null termination (i.e. the strchr trick) into your uppercase loop. I'll leave that as "an exercise for the reader".

[Adak]

Recursion is fine, but he probably hasn't been taught it yet. That's why he began the program using an iterative design.


Backtracking isn't useful here:

   for(r=0;r<ROWS;r++) {
      for(c=0;c<COLS;c++) {

         //check up to 8 directions clockwise
         r1=r; c1=c; i=0;  //12 o'clock
         while(r1>=0 && buff[i]==jumble[r1][c1]) {
            --r1;
            ++i;
         }
         if(i==len)
             printf("found it on row: %d  beginning at column: %d \n",r,c);
   
         ...

[anduril462]

Recursion is fine, but he probably hasn't been taught it yet. That's why he began the program using an iterative design.


Backtracking isn't useful here:

Ahh, yes, I suppose that's not an ideal solution since, once you figure out which direction to go from the start letter, it's a straight line.

[froseph]

Recursion is fine, but he probably hasn't been taught it yet. That's why he began the program using an iterative design.


Backtracking isn't useful here:

   for(r=0;r<ROWS;r++) {
      for(c=0;c<COLS;c++) {

         //check up to 8 directions clockwise
         r1=r; c1=c; i=0;  //12 o'clock
         while(r1>=0 && buff[i]==jumble[r1][c1]) {
            --r1;
            ++i;
         }
         if(i==len)
             printf("found it on row: %d  beginning at column: %d \n",r,c);
   
         ...

What does this piece of code do?

[Adak]

It's a snippet of code from my jumble word searcher. That part specifically handles the checks upward to 12 o'clock. (There are 8 directions that need to be checked.)

A Jumble puzzle has several words in it, and you have to take parts of each word to discover the solution word. That program snippet is from a program that does what you're doing, not strictly a Jumble puzzle solver. It finds words, including those in your data file.

[froseph]

Thanks for the help guys - Sorted everything out now.

Joe