#include <iostream>
#include <string>
#include <fstream>

#include <list>
#include <map>
#include <set>

using namespace std;

void openDictionary(map<int, list<string>> &wordsByLength, 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();
}

/*
 * Given a word and a previous prototype, update the prototype with the char `guess`.
 */
void getWordPrototype(string &wordPrototype, string &word, char guess) {
    for (int i = 0; i < word.size(); i++) {
        if (word[i] == guess) {
            wordPrototype[i] = guess;
        }
    }
}

/*
 * Populate `wordGroup` with the largest word group after a `guess` was made,
 * given a previous word group. Returns whether the prototype has changed or not.
 */
bool getWordGroup(list<string> &wordGroup, string &wordPrototype, char guess, int guesses) {
    map<string, list<string>> wordGroups; // { prototype: [ match1, match2, .. ] }
    for (string &word: wordGroup) {
        if (word.find(guess) == string::npos) {
            // word doesn't contain guess
            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);
            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) {
        if (guesses == 1 && n.first == wordPrototype) {
            wordGroup = n.second;
            return false;
        }
        int size = n.second.size();
        if (size > maxSize) {
            maxSize = size;
            maxPrototype = n.first;
        }
    }
    wordGroup = wordGroups[maxPrototype];
    if (wordPrototype == maxPrototype) {
        return false;
    } else {
        wordPrototype = maxPrototype;
        return true;
    }
}

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

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

    int wordLength;
    while (cout << "Choose a word length to guess: " && cin >> wordLength) {
        if (wordsByLength.count(wordLength) == 0) {
            cout << "No words of that length found." << endl;
        } else {
            break;
        }
    }
    int guesses;
    cout << "Choose number of guesses: ";
    cin >> guesses;
    
    bool showWordsLeft;
    {
        char response;
        cout << "Would you like to see the number of words left? [Y/n]: ";
        cin >> response;
        showWordsLeft = (response != 'n');
    }

    string wordPrototype;
    for (int i = 0; i < wordLength; i++) {
        wordPrototype.push_back('-');
    }

    list<string> wordGroup = wordsByLength[wordLength];
    set<char> guessedChars;

    bool won = false;
    while (guesses > 0 && !won) {
        if (showWordsLeft) {
            cout << "(" << wordGroup.size() << ") ";
        }
        cout << wordPrototype << " with " << guesses << " guesses left. Guessed characters: ";
        for (char c: guessedChars) {
            cout << c;
        }
        cout << endl;
        cout << "Guess a letter: ";
        char guess;
        cin >> guess;
        if (getWordGroup(wordGroup, wordPrototype, guess, guesses)) {
            // new prototype, correct guess
            won = (wordPrototype.find('-') == string::npos);
        } else {
            // wrong guess
            guessedChars.insert(guess);
            guesses--;
        }
    }
    if (won) {
        cout << "Well done!" << endl;
    } else {
        cout << "The word was '" << wordGroup.front() << "'. Better luck next time." << endl;
    }
}