Hi I have a CS class assinment that invloves solving a word search puzzle with a brute force string matching algorithm. I have made a lot of head way in getting the four search methods to work, however when I search for words that end along the edges of the puzzle they are never found. Some help getting this part done would be nice, thanks!'
#include<iostream>
#include<cstdlib>
#include<string>
#include<iomanip>
#include<fstream>
#include<cctype>
#define SIZE 12
//Global variable to hold the size of 2D array.
using namespace std;
//******************************************************************************
//structure defintion
struct arrayData
{
string qury;
//Variable to hold the term being searched for.
int row;
int col;
//row and column number of string if found.
//it proved necessary to add a found term for each method of search possible.
bool found_L_to_R;
bool found_R_to_L;
bool found_T_to_B;
bool found_B_to_T;
bool found;
//Structure functions
void inittilize()
{
row, col = -1;
found_L_to_R = false;
found_R_to_L = false;
found_T_to_B = false;
found_B_to_T = false;
//these will be togled to false if the individual searches do not yield a
//result.
found = false;
}//function intilizes the required fields in the struct.
void reset()
{
row= -1;
col= -1;
found_L_to_R = false;
found_R_to_L = false;
found_T_to_B = false;
found_B_to_T = false;
found = false;
qury.clear();
} //function resets all fields in the struct to prepare for the next quary.
};
//function prototypes
void getArray(char array[][SIZE]);
//Gets the array to be used as the puzzle.
void printArray(char array[][SIZE]);
//Prints the array that contains the puzzle.
bool searchForHorizontalRtoL(char array[][SIZE], struct arrayData &Data);
//Searches the array for the desired word in the R to L method.
bool searchForHorizontalLtoR(char array[][SIZE], struct arrayData &Data);
//Searches the array for the desired word in the L to R method.
bool searchForVerticalTtoB(char array[][SIZE], struct arrayData &Data);
//Searches the array for the desired word in the T to B method.
bool searchForVerticalBtoT(char array[][SIZE], struct arrayData &Data);
//Searches the array for the desired word in the B to T method.
void search(char array[][SIZE], struct arrayData &Data);
//Function that will preform all of the searches.
void printData(struct arrayData &Data);
//prints the data about the search ran through the puzzle.
void askForSearchTerm(struct arrayData &Data);
//Gets a term to search for from the user.
bool askIfRepeat();
//function to ask the user if they want to do another search.
//******************************************************************************
//******************************************************************************
int main()
{
char array[SIZE][SIZE];
arrayData Data;
Data.inittilize();
getArray(array);
printArray(array);
bool repeat= true;
while(repeat==true)
{
askForSearchTerm(Data);
search(array, Data);
printData(Data);
Data.reset();
repeat=askIfRepeat();
}
return 0;
}
//******************************************************************************
//******************************************************************************
void getArray(char array[][SIZE])
{
ifstream inputfile;
inputfile.open("puzzle2.txt");
//both comands are used to open the file puzzle.txt.
for(int row=0; row < SIZE; row++)
{
for(int col=0; col < SIZE; col++)
{
inputfile >> array[row][col];
//takes a single char from the file and puts it into
// a cell in the array.
}
}
inputfile.close();
}
//******************************************************************************
void printArray(char array[][SIZE])
{
int rowNum=0;
int colNum=0;
cout << endl << "Word Seach Puzzle" << endl;
cout << " ";
for(int n=0; n < 12; n++)
{
cout << setw(2) << rowNum << " ";
rowNum++;
}
rowNum=0;
cout << endl;
//Outputs the title and the rownumber.
for(int row=0; row < SIZE; row++)
{
cout << setw(2) << colNum << " ";
colNum++;
for(int col=0; col < SIZE; col++)
{
cout << setw(2) << array[row][col] << " ";
}
cout << endl;
}
//Outputs the colum number and the puzzle.
cout << " ";
for(int n=0; n < 12; n++)
{
cout << setw(2) << rowNum << " ";
rowNum++;
}
cout << endl;
//outputs the row number.
}
//******************************************************************************
bool searchForHorizontalLtoR(char array[][SIZE], struct arrayData &Data)
{
char ArrayRow[SIZE];
int row = 0;
while(row < SIZE)
{
for(int n=0; n < SIZE; n++)
{
ArrayRow[n]=array[row][n];
} //loads the next row of matrix as a string to be searched.
for(int i= 0; i < (SIZE - Data.qury.size()); i++)
{
int j=0;
while((j < Data.qury.size()) && (Data.qury[j]==ArrayRow[i+j]))
{
j++;
}
if(j==Data.qury.size())
{
Data.col = i;
Data.row = row;
//saves row number and column and returns found.
return true;
}
}//book algorithm to search the individual row for the term.
row++;
//Prepars to load the next row of the matrix for searching.
}
Data.row= -1;
return false;
//Only encountered if term not found, lets the structure know
//that the term could not be found via this method.
}
//******************************************************************************
void printData(struct arrayData &Data)
{
cout << endl << endl;
cout << "The data for the search you just ran will now be printed to screen.";
cout << endl;
//the three adbove lines are for testing only.
if( Data.found_L_to_R == true || Data.found_R_to_L == true ||
Data.found_T_to_B == true || Data.found_B_to_T == true)
{
Data.found = true;
}
if(Data.found == true)
{
cout << endl;
cout << "Your search term was found in the word search matrix.";
cout << endl;
cout << "Your search term began at: ";
cout << "Row number: " << Data.row << endl;
cout << "Column number: " << Data.col << endl;
cout << "The orintation of your search term was: ";
if(Data.found_L_to_R == true)
{
cout << "LR" << endl;
}
else if(Data.found_R_to_L == true)
{
cout << "RL" << endl;
}
else if(Data.found_T_to_B == true)
{
cout << "TB" << endl;
}
else if(Data.found_B_to_T == true)
{
cout << "BT" << endl;
}
}
else if(Data.found == false)
{
cout << endl;
cout << "Sorry, your seach term was not found in the word search matrix.";
cout << endl;
}
cout << endl << endl;
}
//******************************************************************************
void askForSearchTerm(struct arrayData &Data)
{
string input;
cout << endl;
cout << "Please enter a word to search the above puzzle for: ";
cin >> input;
for(int n=0; n < input.size(); n++)
{
input[n]= toupper(input[n]);
//multistep procedure that converts the string to upper case
//without having to first put it into a char variable.
}
cout << endl << "You asked to search for the term: " << input << endl;
Data.qury = input;
}
//******************************************************************************
bool askIfRepeat()
{
string choice;
bool decision;
cout << endl << "Your search is now complete, would you like to do another?";
cout << endl << "Please enter y, Y, yes, or YES to do a search again.";
cout << endl << "Or you may enter n, N, NO, or no to exit the program.";
cout << endl << "Enter your choice now: ";
cin >> choice;
for(int n=0; n < choice.size(); n++)
{
choice[n]= toupper(choice[n]);
}
if(choice == "YES" || choice == "Y")
{
decision = true;
}
else if(choice == "NO" || choice == "N" || choice == "EXIT" || choice == "Q")
{
decision = false;
}
else
{
string secondChanceChoice;
cout << endl << endl << endl;
cout << "You did not enter a valid choice." << endl;
cout << "Please enter another choice of either YES or NO only." << endl;
while(true)
{
cout << endl << "Enter your choice now : ";
cin >> secondChanceChoice;
for(int n=0; n < secondChanceChoice.size(); n++)
{
secondChanceChoice[n]= toupper(secondChanceChoice[n]);
}
if(secondChanceChoice== "YES" || secondChanceChoice == "Y" ||
secondChanceChoice== "NO" || secondChanceChoice == "N")
{
if(secondChanceChoice == "YES" || secondChanceChoice == "Y")
{
decision = true;
break;
}
else if(secondChanceChoice == "NO" || secondChanceChoice == "N")
{
decision = false;
break;
}
}
//the if the input is still not satisfactory the while loop
//continues indefinatly until the user enters valid input.
}
}
return decision;
}
//******************************************************************************
bool searchForHorizontalRtoL(char array[][SIZE], struct arrayData &Data)
{
char ArrayRow[SIZE];
int row = 0;
int inverseRow = 0;
while(row < SIZE)
{
inverseRow = 0;
for(int n=(SIZE-1); n >= 0; n--)
{
ArrayRow[inverseRow]=array[row][n];
inverseRow++;
} //loads the next row of matrix as a string to be searched.
for(int i= 0; i < (SIZE - Data.qury.size()); i++)
{
int j=0;
while((j < Data.qury.size()) && (Data.qury[j]==ArrayRow[i+j]))
{
j++;
}
if(j==Data.qury.size())
{
Data.col = 11 - i;
Data.row = row;
//saves row number and column and returns found.
return true;
}
}//book algorithm to search the individual row for the term.
row++;
//Prepars to load the next row of the matrix for searching.
}
Data.row= -1;
return false;
//Only encountered if term not found, lets the structure know
//that the term could not be found via this method.
}
//******************************************************************************
bool searchForVerticalTtoB(char array[][SIZE], struct arrayData &Data)
{
char ArrayCol[SIZE];
int col= 0;
while(col < SIZE)
{
for(int n=0; n < SIZE; n++)
{
ArrayCol[n]=array[n][col];
} //loads the next column of matrix as a string to be searched.
for(int i= 0; i < (SIZE - Data.qury.size()); i++)
{
int j=0;
while((j < Data.qury.size()) && (Data.qury[j]==ArrayCol[i+j]))
{
j++;
}
if(j==Data.qury.size())
{
Data.col = col;
Data.row = i;
//saves row number and column and returns found.
return true;
}
}//book algorithm to search the individual column for the term.
col++;
//Prepars to load the next column of the matrix for searching.
}
Data.col= -1;
return false;
//Only encountered if term not found, lets the structure know
//that the term could not be found via this method.
}
//******************************************************************************
bool searchForVerticalBtoT(char array[][SIZE], struct arrayData &Data)
{
char ArrayCol[SIZE];
int col= 0;
while(col < SIZE)
{
int inverseCol = 0;
for(int n=(SIZE-1); n >= 0; n--)
{
ArrayCol[inverseCol]=array[n][col];
inverseCol++;
} //loads the next column of matrix as a string to be searched.
for(int i= 0; i < (SIZE - Data.qury.size()); i++)
{
int j=0;
while((j < Data.qury.size()) && (Data.qury[j]==ArrayCol[i+j]))
{
j++;
}
if(j==Data.qury.size())
{
Data.col = col;
Data.row = 11 - i;
//saves row number and column and returns found.
return true;
}
}//book algorithm to search the individual column for the term.
col++;
//Prepars to load the next column of the matrix for searching.
}
Data.col= -1;
return false;
//Only encountered if term not found, lets the structure know
//that the term could not be found via this method.
}
//******************************************************************************
void search(char array[][SIZE], struct arrayData &Data)
{
//call all of the search functions.
Data.found_L_to_R=searchForHorizontalLtoR(array, Data);
if(Data.found_L_to_R==false)
{
Data.found_R_to_L=searchForHorizontalRtoL(array, Data);
}
if(Data.found_L_to_R==false && Data.found_R_to_L==false)
{
Data.found_T_to_B=searchForVerticalTtoB(array, Data);
}
if(Data.found_L_to_R==false && Data.found_R_to_L==false &&
Data.found_T_to_B==false)
{
Data.found_B_to_T=searchForVerticalBtoT(array, Data);
}
}
The text of the puzzle being searched is as follows:
GRETUPMOCGBY
EAAHIODKYNAZ
FIGCOLDJNINW
DNQIFEXNEJUP
PKTRAVERSALA
VLBTWERMOWSH
HBOALDCNBKXL
EMCUGFSGEPZQ
JCOMEGAUGNAL
DHQUICKSORTV
RLDQSOVNQIJK
UATCTRFALLTM
And for example I am supposed to be able to find the words computer, develop, and fall.
I find computer at [0,8] RL and fall at [11,6] LR. However when I search for develop the program can not find it. But, the program can find develo with the p left off. I don't know if its a problem with the searching algorithm or with me storing the individual rows or columns for searching.
