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.

Recommended Answers

All 6 Replies

did you try printing out the contents of the array to see if anything is off or increasing the size of the puzzle by either a column or a row or both by all sides of the puzzle to see if it makes a difference in the results
for example put a new line of text at the beginning so p from 'develop' will be found at the second row

you could also try to minimize the puzzle and print out the contents and results to scope out where the problem occurs

Ok, I tood your advice and put print statments in that helped to see that if I changed the line:
while((j < Data.qury.size()) && (Data.qury[j]==ArrayCol[i+j]))
to
while((j < Data.qury.size()) && (Data.qury[j]==ArrayCol[i+j+1]))
in the function that searches from bottom to top
it would catch the last letter of a search that ended on the top row of the puzzle.
However, this has the conseqense of making a search that starts at the bottom most row of the puzzle always come of no found. Suggestions?

However when I search for develop the program can not find it.

It appears that you may have a logic issue in your searchForVerticalBtoT function
Please note that the D in DEVELOP begins at position #5 (Zero based index)

But the following code will never execute since SIZE equals 12 and Data.qury.size() equals 7
and i equals 5. That is, when i gets to index 5 which is the D, the for loop code will not execute
because i is EQUAL to SIZE- Data.qury.size()

for(int i= 0; i < (SIZE - Data.qury.size()); i++)
        {

11 P
10 O
9 L
8 E
7 V
6 E
5 D
4 F
3 G
2 C
1 O
0 R

Ok, so from that I see that if I change the line
for(int i= 0; i < (SIZE - Data.qury.size()); i++)
into
for(int i= 0; i < ((SIZE+1) - Data.qury.size()); i++)
my problems should be fixed. Right?

Ok, so from that I see that if I change the line
for(int i= 0; i < (SIZE - Data.qury.size()); i++)
into
for(int i= 0; i < ((SIZE+1) - Data.qury.size()); i++)
my problems should be fixed. Right?

Yes, it will find DEVELOP. But you're using a brute force algorithm. Thus, there may be other anomalies that aren't addressed.

Ok, thanks for the help it appears that if I increase size by one in all of my searches that it fixes the problem of not being able to find terms near the edge of the puzzle. I ran a search from all directions and found my search term at the correct spot everytime.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.