/* ------------------------------------------------
 *
 *
 * Class: Program #3 for CS 141, Fall 2019
 * System: Codio
 * Author: Craig Yong & Nathan Baxter
 *
*/
#include <iostream>
#include <string>
#include <fstream>      // For file input
#include <vector>       // For dictionary vector
#include <iomanip>      // For setw()
#include <cctype>       // For tolower()
using namespace std;


//---------------------------------------------------------------
// Display ID info
//
void displayIdInfo()
{
    cout << " \n"
         << "Program #3: Work Play  \n"
         << "Author: Craig Yong & Nathan Baxter      \n"
         << "Lab: Tues 12pm + Tues 11am          \n"
         << "System:  Codio         \n"
         << " \n";
}


//-----------------------------------------------------------------------------------------
//  You should use parameters for the dictionary, the word lengths array,
//  the length of words to use, and the total number of words.
//
//
void readInWordsFromFile(int wordLengthCount[30],int lengthOfWordsToUse,vector<string>& dictionary)
{
    ifstream inputFileStream;

    string fileName = "dictionary.txt"; // C string (array of char) to store filename
    string inputWord;                   // stores each word as it is read
    int x = 0;
    string outputWord;
    int arraySum = 0;

    // Open input file
    inputFileStream.open( fileName.c_str() );

   // Verify that the open worked
    if( !inputFileStream.is_open()) {
        cout << "Could not find input file " << fileName << "  Exiting..." << endl;
        exit( -1);
    }

    // Read all the words from the file, and display them
    while( inputFileStream >> inputWord) {
       //cout << inputWord;
        //outputWord = inputWord;
        x = inputWord.length();
        if (x == lengthOfWordsToUse){
           for (int i=0; i<(inputWord.length()); i++){
               inputWord[i] = tolower(inputWord[i]);
        }
        dictionary.push_back(inputWord);
        }
        wordLengthCount[x] = wordLengthCount[x] + 1;
        }

    inputFileStream.close();    // Close the input file.


    for (int i = 0; i < 30; i++){ //For loop to count the amount of word in the dictionary at each length
        arraySum = arraySum + wordLengthCount[i];

    }
    cout << "Total number of words in dictionary file: " << arraySum << endl;
    cout << "\n" << "Word lengths where there are more than 1400 words: " << endl
         << "Length  How Many  " << endl
         << "------  --------  " << endl;

    for (int i = 0; i < 30; i++){
        if (wordLengthCount[i] >= 1400){
            cout << setw(5);
            cout << i << setw(10);
            cout << wordLengthCount[i] << endl;
        }
    }
}

//--------------------------------------------------------------------------------------
// Use binary search to look up the search word in the dictionary vector, returning
// the word's index if found, -1 otherwise.
//
long binarySearch(
            string searchWord,            // word to be looked up
            vector< string> dictionary)   // the dictionary of words
{
    long low, mid, high;     // array indices for binary search
    long searchResult = -1;  // Stores index of word if search succeeded, else -1

    // Binary search for word
    low = 0;
    high = dictionary.size() - 1;
    while ( low <= high)  {
        mid = (low + high) / 2;
        // SearchResult negative value means word is to the left, positive value means
        // word is to the right, value of 0 means word was found
        searchResult = searchWord.compare( dictionary[ mid] );
        if ( searchResult == 0)  {
            // Word IS in dictionary, so return the index where the word was found
            return mid;
        }
        else if (searchResult < 0)  {
            high = mid - 1; // word should be located before the mid location
        }
        else  {
            low = mid + 1; // word should be located after the mid location
        }
    }

    // Word was not found
    return -1;
}//end binarySearch()

 //Menu Option 4
void WordChangeGame(string startWord, string endWord, int lengthOfWordsToUse, vector<string> dictionary){
        int i = 1;
        int killValue = 0;
        int numCharsDifferent = 0;
        string previousWord = " ";
        string nextWord = " ";
        if (startWord.empty() || endWord.empty()){
            cout << "Error. Strings are EMPTY!!!. back to the menu.";
            killValue = 1;
        }
        previousWord = startWord;

    do{
        cout << i << ". Previous word is '" << previousWord << "'.  Next word: ";
        cin >> nextWord; //Displays the previous word

        if (nextWord == "exit"){ //Allows user input of 'exit' to leave the do while loop
            killValue = 1;
        }

        if (nextWord.length() != lengthOfWordsToUse){
            cout << "Word is too long...or too short. Restart." << endl; //Checks for matching word length
            i = i + 1;
            continue;
        }

        if (binarySearch(nextWord,dictionary) == -1){//binary search checks for valid words in the dictionary
           cout << "Word is not in dictionary. Or Binary Search is broken..." << endl;
            i = i + 1;
            continue;
        }
        numCharsDifferent = 0;
        for (int p = 0; p < lengthOfWordsToUse; p++){  //This loop checks for the amount of characters the user changes
            if (previousWord[p] != nextWord[p]){
                numCharsDifferent = numCharsDifferent + 1;
            }
        }

        if (numCharsDifferent != 1){ //When the number of characters different exceeds one, then the user is prompted to restart with a new input
            cout << "Words differ too much. Change less." << endl;
            numCharsDifferent = 0;
            i = i + 1;
            continue;
        }

        if (nextWord == endWord){ //Win condition for the word change game, when the user reaches the end word.
            cout << "Nice one." << endl;
            killValue = 1;
        }

        previousWord = nextWord;
        i = i + 1;

    } while(killValue == 0);

}//End of Word Change Game
 //Menu Option 5
void debugWord(int lengthOfWordsToUse, string startWord, string endWord, vector<string> dictionary){

    vector< string> treeVector;
    treeVector.push_back(startWord);
    string testStr = "";
    string tempStr = "";
    string tempStrNested = "";
    int vectorPosition = 0;
    string outputHolder = "";
    int searchIndex = 0;

    int daleReed = 0;

    do{

        testStr = treeVector.at(vectorPosition);
        for (int p = 0; p < lengthOfWordsToUse; p++){
            if (vectorPosition != 0){
                if (testStr[0] != (treeVector.at(vectorPosition-1))[0]){
                    continue;
            }
            }
            for(int i = 1; i <= 26; i++){

                 //LOOPALLSHIT from dog   aog -> doz
                for (int q = 0; q < lengthOfWordsToUse; q++){
                      for(int z = 1; z <= 26; z++){

                        if (testStr[q] != z+96){
                            tempStrNested = testStr;
                            tempStrNested[q] = (z+96);
                            if (tempStrNested == endWord){
                                daleReed = 1;
                                cout << tempStrNested << "WiNNER 1" << endl;
                                break;
                                 }
                        }
                      }
                    if (tempStrNested == endWord){
                                cout << tempStrNested << "WiNNER 2" << endl;
                                break;
                                 }
                }//ENDLOOPALLSHIT from dog aog ->doz



                if (tempStrNested == endWord){
                    daleReed = 1;
                    cout << "brain magic";
                    break;
                }

                if (daleReed == 1){
                    break;
                }

                if (testStr[p] != i+96){
                    tempStr = testStr;
                    tempStr[p] = (i+96);

                }
                if (binarySearch(tempStr,dictionary) == -1){

                    continue;
                } // FINISH <- failed condition , word not in dictionary
                if (binarySearch(tempStr,treeVector) != -1){
                 //   cout << tempStr << "fail" << endl;
                    continue;
                }

                treeVector.push_back(tempStr);
            //    cout << tempStr << "       " << testStr << endl;



                if (tempStrNested == endWord || daleReed == 1){  // FINISH <-- win condition
                    cout << tempStrNested << "WiNNER 3" << endl;
                    break;
                }
            }        //End of 'for(int i = 0; i < 26; i++)'  --- iterating each letters of alphabet


        if (tempStrNested == endWord || daleReed == 1){  // FINISH <-- win condition
                cout << tempStrNested << "WiNNER 4" << endl;
                break;
                }

    }//End of loop iterating char position
        vectorPosition = vectorPosition + 1;
        testStr = treeVector.at(vectorPosition);
        cout << treeVector.at(vectorPosition) << "   " << testStr << endl;



        if (tempStrNested == endWord){  // FINISH <-- win condition
                    break;
                }
        if (tempStrNested == endWord){
                    daleReed = 1;
                    break;
                }

    } while(daleReed == 0);




testStr = "";
tempStrNested = "";

/* for (int t = 0; t < treeVector.size(); t++){
   outputHolder = treeVector.at(t);
   cout << "\n" << t << ". " << outputHolder << ":   ";


   for (int n = 0; n < lengthOfWordsToUse; n++){
        for(int a = 1; a <= 26; a++){
           if (outputHolder[n] == a+96){
               continue;
           }
               tempStrNested = outputHolder;
               tempStrNested[n] = (a+96);


                if (binarySearch(tempStrNested,dictionary) != -1){
                    searchIndex = binarySearch(tempStrNested,treeVector);
                    if (searchIndex == -1){
                        treeVector.push_back(tempStrNested);
                        cout << (treeVector.size()-1) << ": " << tempStrNested << " ";
                    }
                    else if (searchIndex != -1){
                        cout << searchIndex << ":" << tempStrNested << " ";
                    }




                }
                    if (tempStrNested == endWord){
                                break;
                                 }
                      }
                    if (tempStrNested == endWord){
                                break;
                                 }
                }

    if (tempStrNested == endWord){
                cout << "\n";
                break;
    }


} */
}//End of debugWord







//-----------------------------------------------------------------------------------------
int main()
{
    vector< string> dictionary;         // Vector of dictionary words read in from file
    int lengthOfWordsToUse = 3;         // Default length of word to use in word transformation
    string startWord = "dog";           // The start word for transformation
    string endWord = "cat";             // The end word for transformation
    int menuOption = -1;                // User menu option selection
    int wordLengthCount[30];

    for (int i = 0; i < 30; i++){
        wordLengthCount[i] = 0;
       }

    // Display ID info
    displayIdInfo();

    // Seed the random number generator
    srand( 1);  // Change 1 to time(0) for non-predictable results, but leave as 1 for testing
    readInWordsFromFile(wordLengthCount, lengthOfWordsToUse, dictionary);


     do {
        cout << "Currently we have " << dictionary.size() << " words of length "
             << lengthOfWordsToUse << " in the dictionary.  \n"
             << "Changing from '" << startWord << "' to '" << endWord << "'" << endl
             << endl;
       //The menu with options
        cout << "Choose from the following options:  \n"
             << "   1. Change the word length        \n"
             << "   2. Display some dictionary words \n"
             << "   3. Get start and end words       \n"
             << "   4. Play the word change game     \n"
             << "   5. Find the end word with debug  \n"
             << "   6. Find the end word             \n"
             << "   7. Display an answer sequence    \n"
             << "   8. Exit the program              \n"
             << "Your choice -> ";
        cin >> menuOption; //Stores user input from the menu
        cout << "\n";


        // Menu option handling
        if (menuOption < 1 || menuOption > 8){//When the menu option provided is out of the range, the user is prompted to put a new option that is in the range.
            cout << "Invalid choice. Please try again: ";
            cin >> menuOption;
        }

        if (menuOption == 1){
           cout << "What length words do you want to use? ";
            cin >> lengthOfWordsToUse;
            dictionary.clear();
            startWord = "";
            endWord = "";
            readInWordsFromFile(wordLengthCount, lengthOfWordsToUse, dictionary);



            }//End of menuOption 1



        if (menuOption == 2){
            int startValue = 0;
            int endValue = 0;
            cout << "Enter the start and end index values of words to display: ";
            cin >> startValue >> endValue;
            for (int i = startValue; i <= endValue; i++){
                cout << i << " " << dictionary.at(i) << endl;
            }

        } //End of menuOption 2
        if (menuOption == 3){
            do{
            cout << "Enter starting word, or 'r' for a random word: ";
            cin >> startWord;
            if (startWord == "exit" | endWord == "exit"){
                menuOption = 8;
                break;
                }


            if (startWord == "r"){
                startWord = dictionary[ rand()%dictionary.size()];
            }
            if (endWord == "r"){
                endWord = dictionary[ rand()%dictionary.size()];
            }
            if (startWord.length() != lengthOfWordsToUse || endWord.length() != lengthOfWordsToUse ){
                cout << "Words need to be of length " << lengthOfWordsToUse << ". Please try again" << endl;
                continue;
            }
            if ( (binarySearch(startWord,dictionary) == -1) || (binarySearch(endWord,dictionary) == -1)){
                cout << "Words need to exist...  Please try again.";
                continue;
            }
            cout << "\n Enter ending word, or 'r' for a random word: ";
            cin >> endWord;

            if (startWord == "exit" | endWord == "exit"){
                menuOption = 8;
                break;
                }


            if (startWord == "r"){
                startWord = dictionary[ rand()%dictionary.size()];
            }
            if (endWord == "r"){
                endWord = dictionary[ rand()%dictionary.size()];
            }
            if (startWord.length() != lengthOfWordsToUse || endWord.length() != lengthOfWordsToUse ){
                cout << "Words need to be of length " << lengthOfWordsToUse << ". Please try again" << endl;
                continue;
            }
            if ( (binarySearch(startWord,dictionary) == -1) || (binarySearch(endWord,dictionary) == -1)){
                cout << "Words need to exist...  Please try again.";
                continue;
            }

            break;
            } while(true);

         }//End of menuOption 3

        if (menuOption == 4){

            WordChangeGame(startWord, endWord, lengthOfWordsToUse, dictionary);


        }//End of menuOption 4
        if (menuOption == 5){

           debugWord(lengthOfWordsToUse, startWord, endWord, dictionary);


        }//End of menuOption 5
        if (menuOption == 6){}
        if (menuOption == 7){}

        if (menuOption == 8){
            cout << "Exiting the program" << endl;
            break;
        }

    } while( true);


       return 0;
}