#include <iostream>
#include <string>
#include <fstream>
#include <list>
#include <map>
#include <set>

using namespace std;

static const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";

/*
 * Populate `wordsByLength` with lists of strings from file `path`.
 *
 * `wordsByLength` is "indexed" by the length of the words in the list.
 */
void openDictionary(map<int, list<string>> &wordsByLength, const string &path) {
    ifstream input;
    input.open(path);
    string word;
    while (input >> word) {
        int length = word.length();
        if (wordsByLength.count(length) == 0) {
            wordsByLength[length] = list<string>();
        }
        wordsByLength[length].push_front(word);
    }
    input.close();
}

/*
 * Update the prototype with the char `guess` to match `word`.
 */
void getWordPrototype(string &wordPrototype, const string &word, const char guess) {
    for (int i = 0; i < word.size(); i++) {
        if (word[i] == guess) {
            wordPrototype[i] = guess;
        }
    }
}

/*
 * Update `wordGroup` with the largest word group after `guess` was made,
 * given a previous word group and prototype. Returns whether the guess
 * was correct or not and updates the prototype.
 */
bool getWordGroup(list<string> &wordGroup, string &wordPrototype, const char guess) {
    map<string, list<string>> wordGroups; // { prototype: [ match1, match2, .. ], ..  }
    for (string &word : wordGroup) {
        if (word.find(guess) == string::npos) { // word doesn't contain guess
            // initial empty list
            if (wordGroups.count(wordPrototype) == 0) {
                wordGroups[wordPrototype] = list<string>();
            }
            wordGroups[wordPrototype].push_back(word);
        } else { // word contains guess at least once
            string newWordPrototype(wordPrototype);
            getWordPrototype(newWordPrototype, word, guess);
            // initial empty list
            if (wordGroups.count(newWordPrototype) == 0) {
                wordGroups[newWordPrototype] = list<string>();
            }
            wordGroups[newWordPrototype].push_back(word);
        }
    }

    // find largest word group
    int maxSize = 0;
    string maxPrototype;
    for (auto &n : wordGroups) {
        int size = n.second.size();
        if (size > maxSize) {
            maxSize = size;
            maxPrototype = n.first;
        }
    }

    // set wordgroup and prototype
    wordGroup = wordGroups[maxPrototype];
    if (wordPrototype == maxPrototype) {
        return false;
    } else {
        wordPrototype = maxPrototype;
        return true;
    }
}

/*
 * Play (evil) hangman with the given parameters.
 *
 * `wordLength` is the length of the word to guess.
 * `guesses` is the total amount of guesses.
 * `showWordsLeft` is whether to print how many valid words are left in each stage.
 * `wordGroup` is the initial group of valid words.
 */
bool hangman(const int wordLength, const int guesses, const bool showWordsLeft, list<string> &wordGroup) {
    string wordPrototype;
    for (int i = 0; i < wordLength; i++) {
        wordPrototype.push_back('-');
    }

    set<char> guessedChars;
    int guesses_left = guesses;
    string line;

    bool won = false;
    while (guesses_left > 0 && !won) {
        // print status
        if (showWordsLeft) {
            cout << "(" << wordGroup.size() << ") ";
        }
        cout << wordPrototype << " with " << guesses_left << " guesses left. Guessed characters: ";
        for (char c : guessedChars) {
            cout << c;
        }
        cout << endl;

        // ask for guess
        char guess;
        bool done = false;
        while (!done) {
            cout << "Guess a letter: ";
            getline(cin, line);
            if (line.size() != 1) {
                cout << "Please input one character only." << endl;
                continue;
            }
            guess = line[0];
            if (ALPHABET.find(guess) == string::npos) {
                cout << "Please input a valid (lower-case) character." << endl;
                continue;
            }
            if (guessedChars.count(guess)) {
                cout << "You have already guessed this character." << endl;
                continue;
            }
            done = true;
        }
        guessedChars.insert(guess);

        // check guess
        if (getWordGroup(wordGroup, wordPrototype, guess)) {
            // correct guess, new prototype
            won = (wordPrototype.find('-') == string::npos);
        } else {
            // wrong guess
            guesses_left--;
        }
    }
    return won;
}

int main() {
    cout << "Welcome to Hangman." << endl;

    cout << "Reading dictionary... " << endl;
    map<int, list<string>> wordsByLength;
    openDictionary(wordsByLength, "res/dictionary.txt");
    cout << "done" << endl;

    bool play = true;
    while (play) {
        string line;
        int wordLength;
        bool done = false;
        while (!done) {
            cout << "Choose a word length to guess: ";
            getline(cin, line);
            try {
                wordLength = stoi(line);
            } catch (const invalid_argument &) {
                cout << "Not a number." << endl;
                continue;
            }
            if (wordsByLength.count(wordLength) == 0) {
                cout << "No words of that length found." << endl;
            } else {
                done = true;
            }
        }
        int guesses;
        done = false;
        while (!done) {
            cout << "Choose number of guesses: ";
            getline(cin, line);
            try {
                guesses = stoi(line);
            } catch (const invalid_argument &) {
                cout << "Not a number." << endl;
                continue;
            }
            if (guesses <= 0) {
                cout << "Non-positive number of guesses doesn't make sense." << endl;
                continue;
            }
            done = true;
        }

        cout << "Would you like to see the number of words left? [Y/n]: ";
        getline(cin, line);
        bool showWordsLeft = (line != "n");

        list<string> wordGroup = wordsByLength[wordLength];

        if (hangman(wordLength, guesses, showWordsLeft, wordGroup)) {
            cout << "Well done!" << endl;
        } else {
            cout << "The word was '" << wordGroup.front() << "'. Better luck next time." << endl;
        }
        cout << "Play again? [Y/n]: ";
        getline(cin, line);
        play = (line != "n");
    }
    cout << "Goodbye" << endl;
}