Hello EvilZone,
This is the first time I've posted in awhile, but that's because I've been in college for computer engineering! Anyway, I realized I've been doing some programming for my intro courses, and so I thought I'd post my solution to one of my assignments here. Keep in mind this is really basic stuff, and since I had programming experience going into the course, this stuff was child's play. This was the hardest assignment we had last quarter.
The Assignment: Our assignment was to write a program in C (not C++) that reads in 2 files: one that contains a word search puzzle, and one that contains the words to search for. The size of the puzzles are always 10x10, but one could easily implement a way to allow that size to vary. Once the program reads in the puzzle, it loops through each word and searches for it. The specific algorithm I've chosen for searching is explained in the comments at the top of the program, and the rest of the program is well-commented too. Results of the search are then printed to the standard output. These results will either be the row and column of the first letter, along with the orientation of the word (right, up, up-right, etc.), or it will simply let the user know the word was not found. The puzzle itself is also printed before any of the searching begins.
* Note that the rows and columns in the results are numbered from 0-9, not 1-10.
* If a word occurs twice in a puzzle, it will find the first occurrence and print the results. The second will be ignored.
The Code:/* General method: In order to find the words in the puzzle, searchWord() searches
* for every occurance of the first letter. Once the first letter is found, the
* second letter is searched for all around the first. For every occurence the
* first and second letters are found next to each other, the orientation (up, right,
* down, left, diagonals, etc.) is saved in an orientation_t struct and the
* searchRestOfWord() function is used. searchRestOfWord recursively searches
* for the rest of the word in the orientation specified. If the rest is found,
* then the row, column, and orientation of the word is saved and printed to the screen */
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define UP -1
#define DOWN 1
#define RIGHT 1
#define LEFT -1
typedef struct
{
int upDown;
int leftRight;
char orient_id[30];
}orientation_t;
int searchWord(char word[], char puzzle[][10], orientation_t *orient, int *row, int *col); /* returns 0 or 1 for not found/found */
int searchRestOfWord(char word[], char puzzle[][10], orientation_t orient, int row, int col, int wordIndex); /* returns 0 or 1 for found/not found */
void readPuzzle(char fileName[], char puzzle[][10]);
void printPuzzle(char puzzle[][10]);
int main(int argc, char *argv[])
{
FILE *words;
int end, row = 0, col = 0;
char currentWord[30];
char puzzle[10][10];
orientation_t orient;
if(argc == 3)
{
orient.upDown = 0;
orient.leftRight = 0;
readPuzzle(argv[1], puzzle);
printPuzzle(puzzle);
words = fopen(argv[2], "r");
end = fscanf(words, "%s", currentWord);
while(end != EOF)
{
if(searchWord(currentWord, puzzle, &orient, &row, &col) == 1)
{
/* found: do stuff */
printf("%s: (%s) row: %d column: %d\n", currentWord, orient.orient_id, row, col);
}
else
{
/* not found: do stuff */
printf("%s: word not found\n", currentWord);
}
end = fscanf(words, "%s", currentWord);
}
}
else
{
printf("usage: ./wordsearch puzzleFile wordFile\n");
}
return 0;
}
/* searchWord - searches for a word in the puzzle
*
* args:
* char word[] - the word to search for
* char puzzle[][10] - the puzzle to search inside
* orientation_t *orient - pointer to the orientation
* structure to fill with the word's orientation
* in the puzzle (if found)
* int *row - pointer to the row to be filled if found
* int *col - pointer to the col to be filled if found
*
* return value: returns 1 if found and 0 if not found */
int searchWord(char word[], char puzzle[][10], orientation_t *orient, int *row, int *col)
{
/* search for first letter */
int i, j;
for(i = 0; i<10; i++)
{
for(j = 0; j<10; j++)
{
if(puzzle[i][j] == word[0])
{
/* first letter found, search for second letter */
if(j!=9)
{
if(puzzle[i][j+1] == word[1])
{
orient->upDown = 0;
orient->leftRight = RIGHT;
strcpy(orient->orient_id, "FORWARD");
if(searchRestOfWord(word, puzzle, *orient, i, j+1, 2) == 1)
{
*row = i;
*col = j;
return 1;
}
}
}
if(j!=0)
{
if(puzzle[i][j-1] == word[1])
{
orient->upDown = 0;
orient->leftRight = LEFT;
strcpy(orient->orient_id, "BACKWARD");
if(searchRestOfWord(word, puzzle, *orient, i, j-1, 2) == 1)
{
*row = i;
*col = j;
return 1;
}
}
}
if(i!=9)
{
if(puzzle[i+1][j] == word[1])
{
orient->upDown = DOWN;
orient->leftRight = 0;
strcpy(orient->orient_id, "DOWN");
if(searchRestOfWord(word, puzzle, *orient, i+1, j, 2) == 1)
{
*row = i;
*col = j;
return 1;
}
}
}
if(i!=0)
{
if(puzzle[i-1][j] == word[1])
{
orient->upDown = UP;
orient->leftRight = 0;
strcpy(orient->orient_id, "UP");
if(searchRestOfWord(word, puzzle, *orient, i-1, j, 2) == 1)
{
*row = i;
*col = j;
return 1;
}
}
}
if(j != 9 && i != 0)
{
if(puzzle[i-1][j+1] == word[1])
{
orient->upDown = UP;
orient->leftRight = RIGHT;
strcpy(orient->orient_id, "UP-RIGHT");
if(searchRestOfWord(word, puzzle, *orient, i-1, j+1, 2) == 1)
{
*row = i;
*col = j;
return 1;
}
}
}
if(j != 9 && i != 9)
{
if(puzzle[i+1][j+1] == word[1])
{
orient->upDown = DOWN;
orient->leftRight = RIGHT;
strcpy(orient->orient_id, "DOWN-RIGHT");
if(searchRestOfWord(word, puzzle, *orient, i+1, j+1, 2) == 1)
{
*row = i;
*col = j;
return 1;
}
}
}
if(j != 0 && i != 0)
{
if(puzzle[i-1][j-1] == word[1])
{
orient->upDown = UP;
orient->leftRight = LEFT;
strcpy(orient->orient_id, "UP-LEFT");
if(searchRestOfWord(word, puzzle, *orient, i-1, j-1, 2) == 1)
{
*row = i;
*col = j;
return 1;
}
}
}
if(j != 0 && i != 9)
{
if(puzzle[i+1][j-1] == word[1])
{
orient->upDown = DOWN;
orient->leftRight = LEFT;
strcpy(orient->orient_id, "DOWN-LEFT");
if(searchRestOfWord(word, puzzle, *orient, i+1, j-1, 2) == 1)
{
*row = i;
*col = j;
return 1;
}
}
}
}
}
}
return 0;
}
/* searchRestOfWord - after a word's orientation is found, this function searches recursively
* until the end of the word is found
*
* args:
* char word[] - the word being searched for
* char puzzle[][10] - the puzzle to search in
* orientation_t orient - the orientation of the word
* int row - the current row
* int col - the current col
*
* return value: returns 1 if the entire word is found and 0 if not */
int searchRestOfWord(char word[], char puzzle[][10], orientation_t orient, int row, int col, int wordIndex)
{
if(word[wordIndex] == puzzle[row+orient.upDown][col+orient.leftRight]) /* if next letter matches */
{
if(wordIndex == strlen(word)-1)
{
return 1;
}
else
{
return searchRestOfWord(word, puzzle, orient, row+orient.upDown, col+orient.leftRight, wordIndex+1);
}
}
else
{
/* next letter doesn't match - return false */
return 0;
}
}
/* readPuzzle - read in the puzzle from a file
*
* args:
* char fileName[] - the file to read
* char puzzle[][10] - the puzzle to read into
*
* return value: none */
void readPuzzle(char fileName[], char puzzle[][10])
{
FILE *in;
int i = 0, j = 0, end;
char c;
in = fopen(fileName, "r");
end = fscanf(in, "%c", &c);
while(end != EOF && i < 10)
{
if(c == '\n')
{
i++;
j = 0;
}
else if(isalpha(c))
{
puzzle[i][j] = c;
j++;
}
end = fscanf(in, "%c", &c);
}
fclose(in);
}
/* printPuzzle - prints the puzzle to the terminal
*
* args:
* char puzzle[][10] - the puzzle to print
*
* return value: none */
void printPuzzle(char puzzle[][10])
{
int i, j;
printf("Puzzle:\n");
for(i = 0; i < 10; i++)
{
for(j = 0; j < 10; j++)
{
printf("%c", puzzle[i][j]);
}
printf("\n");
}
}Here's a picture of an example run:
I can post more of my assignments on here if some want me to - I have a whole quarter's worth of C programs. That being said, they're very basic programs that would only be useful to beginners. This quarter we're working with Java and object-oriented programming, so hopefully they give me more assignments worth posting.
