#include <forward_list>
#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>

using namespace std;

const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";

void openDictionary(set<string> &words, const string &path) {
    ifstream input;
    input.open(path);
    string word;
    while (input >> word) {
        words.insert(word);
    }
    input.close();
}

/*
 * Populate `neighbours` with all valid word neighbours
 * (words with only one char differing) from `words`.
 */
void getValidNeighbours(forward_list<string> &neighbours, const string &word, const set<string> &words) {
    for (int i = 0; i < word.length(); i++) {
        string new_word = word;
        char cur_c = word[i];
        for (char new_c : ALPHABET) {
            if (new_c != cur_c) {
                new_word[i] = new_c;
                if (words.count(new_word)) {
                    neighbours.push_front(new_word);
                }
            }
        }
    }
}

/*
 * Find the shortest word chain between `w1` and `w2`
 * and store it in `chain`.
 */
void wordchain(stack<string> &chain, const string &w1, const string &w2, const set<string> &words) {
    stack<string> firstChain;
    firstChain.push(w1);

    queue<stack<string>> chains;
    chains.push(firstChain);

    set<string> seenWords;
    while (!chains.empty()) {
        stack<string> curChain = chains.front();
        chains.pop();
        forward_list<string> validNeighbours;
        getValidNeighbours(validNeighbours, curChain.top(), words);
        for (string &w : validNeighbours) {
            if (w == w2) {
                // done
                chain.push(w);
                while (!curChain.empty()) {
                    chain.push(curChain.top());
                    curChain.pop();
                }
                return;
            }
            if (seenWords.count(w) == 0) {
                seenWords.insert(w);
                stack<string> newChain = curChain;
                newChain.push(w);
                chains.push(newChain);
            }
        }
    }
}

int main() {
    cout << "Welcome to TDDD86 Word Chain." << endl;
    cout << "If you give me two English words, I will transform the" << endl;
    cout << "first into the second by changing one letter at a time." << endl;
    cout << endl;

    cout << "Please type two words: ";

    string word1, word2;
    cin >> word1 >> word2;

    cout << "Reading valid words..." << endl;
    set<string> words;
    openDictionary(words, "res/dictionary.txt");
    cout << "Done." << endl;

    cout << "Searching..." << endl;
    stack<string> chain;
    wordchain(chain, word1, word2, words);
    cout << "Done." << endl;

    while (!chain.empty()) {
        cout << chain.top() << " ";
        chain.pop();
    }
    cout << endl;
}