#include <iostream.h>
#include <fstream.h>

#include "apstring.h"
#include "apqueue.h"

/****************************************************************************/
/* word ladder                                                              */
/* user enters two words.  if possible, a word ladder is made between the   */
/* words such that any single step changes only one letter.  example:       */
/* path from "money" to "greed":                                            */
/*    money coney covey cover coyer foyer fryer freer freed greed           */
/* takes 4 seconds (uses binary search of selected words)                   */
/*                                                                          */
/* .r.frank 4-Dec-1999                                                      */
/****************************************************************************/

const apstring DATAFILE = "knuth.dat";

// structure to keep track of words and how we got to them.
// consists of the current word and an apqueue of word indexes
// that ladder to this word.
// 
struct wordPath {
    apstring cWord;             // current word
    apqueue <int> path;         // indices of how we got here
};

// load five-letter words from file into an apvector.
// using Knuth's unmodified list of 5 letter words, ignore any line
// that begins with an asterisk and strip any characters past the fifth.
//
void LoadWords(apvector<apstring>& wordList, apvector<bool>& wordsUsed)
{
    int wordcount = 0;
    apstring tmp;
    ifstream infile;
    
    infile.open(DATAFILE.c_str());
    assert(!infile.fail());
    while ( getline(infile,tmp) ) {
        if ( tmp[0] != '*' ) {    
            if (wordcount == wordList.length())
                wordList.resize(wordList.length()+1000);
            wordList[wordcount] = tmp.substr(0,5);
            wordcount++;
        }
    }               
    wordList.resize(wordcount);
    wordsUsed.resize(wordcount);
    for (int i=0; i<wordcount; i++)
        wordsUsed[i] = false;                 // word at this index not used yet
    infile.close();
}

// a word has been found that is one letter different.
// if this word does not already appear in our path, add it to
// the tail of the wordPath queue.
//
void onQueue(int wc,
             wordPath baseWord, 
             const apvector<apstring> &wordList,
             apvector<bool> &wordsUsed,
             apqueue<wordPath> &q)
{
    if ( !wordsUsed[wc] ) {
        wordPath newWord = baseWord;    // copy word and path to here
        newWord.cWord = wordList[wc];   
        newWord.path.enqueue(wc);       // index of this word into path queue 
        q.enqueue(newWord);             
        wordsUsed[wc] = true;
    }
}

// check for test word
// if test word is in word list, return true
bool checkFor(apstring testWord, const apvector<apstring> &wordList, int &where)
{
    int high, low, guess, lastGuess = -1;
    high = wordList.length()-1;
    low = 0;
    guess = (high + low)/2;
    while ( wordList[guess] != testWord && guess != lastGuess) {
        if (wordList[guess] < testWord)
            low = guess;
        else
            high = guess;
        lastGuess = guess;
        guess = (high + low)/2;
    }
    if (wordList[guess] == testWord) {
        where = guess;
        return true;
    }
    else
        return false;
}

// find words that are different in one letter only from given word
// result returned in wordPath queue with new words at end of queue
//
void FindWords(wordPath baseWord, 
               const apvector<apstring> &wordList,
               apvector<bool> &wordsUsed,
               apqueue<wordPath> &q)
{
    char ch;
    int wc = 0;
    wordPath testWord;
    for (ch='a'; ch<='z'; ch++) {

        testWord = baseWord;
        testWord.cWord[0] = ch;
        if ( checkFor(testWord.cWord, wordList, wc) )
            onQueue(wc, testWord, wordList, wordsUsed, q);   

        testWord = baseWord;
        testWord.cWord[1] = ch;
        if ( checkFor(testWord.cWord, wordList, wc) )
            onQueue(wc, testWord, wordList, wordsUsed, q);   

        testWord = baseWord;
        testWord.cWord[2] = ch;
        if ( checkFor(testWord.cWord, wordList, wc) )
            onQueue(wc, testWord, wordList, wordsUsed, q);   

        testWord = baseWord;
        testWord.cWord[3] = ch;
        if ( checkFor(testWord.cWord, wordList, wc) )
            onQueue(wc, testWord, wordList, wordsUsed, q);   

        testWord = baseWord;
        testWord.cWord[4] = ch;
        if ( checkFor(testWord.cWord, wordList, wc) )
            onQueue(wc, testWord, wordList, wordsUsed, q);   
    }    
}    

int main()
{
    wordPath word, final;
	apvector <apstring> wordList;
    apvector <bool> wordsUsed;
    apqueue  <wordPath> words1off, WordPathQueue;
    bool found = false;
    wordPath firstWord, searchWord;
  
    // get all the words
    LoadWords(wordList, wordsUsed);

    apstring startWord, endWord; 
    cout << "enter start word: " << flush;
    cin >> startWord;
    cout << "enter end word:   " << flush;
    cin >> endWord;         
    
    firstWord.cWord = startWord;
    WordPathQueue.enqueue(firstWord);
    
    while ( !WordPathQueue.isEmpty() && !found ) {
        WordPathQueue.dequeue(searchWord);
        FindWords(searchWord, wordList, wordsUsed, words1off); 

        // have new candidates, add to end of queue
        while ( !words1off.isEmpty() ) {  
            words1off.dequeue(word);
            if (word.cWord == endWord) {
                found = true;
                final = word;
            }
            WordPathQueue.enqueue(word);
        }
    }
    
    if (found) {
        cout << "\npath from \"" << startWord << "\" to \"" << endWord << endl;
        while ( !final.path.isEmpty() )
        {
            int index;
            final.path.dequeue(index);
            cout << wordList[index] << endl;
        }
    }
    else {
        cout << "no path found from " << startWord << " to " << endWord << endl;
    }
    return 0;
}