//http://stackoverflow.com/questions/26875913/evil-hangman-implementation-in-python
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <ctime>
#include <algorithm>

const int max_guesses = 8;

std::string rawfile;
std::vector<const char*> wordlist;
std::string targetword;
std::string guessedletters;

void loadwordlist(int length);
bool filter(int length, char newguess);
void finalize();

int main() {
    srand((unsigned)time(NULL));
    int length=rand()%5+rand()%5+rand()%5+3; //random between 3 and 15, normal-ish distribution
    loadwordlist(length);
    targetword.assign(length,'?');
    int guessno = 1;
    int wrongguesses = 0;
    
    std::cout << "Welcome to Hangman!\n"
        "I have selected a word from an english dictionary.\n"
        "I will first show you the length of the secret word\n"
        "as a series of dashes.\n"
        "Your task is to guess the secret word one letter at a time.\n"
        "If you guess a correct letter I will show you the guessed\n"
        "letter(s) in the correct position.\n"
        "You can only make "<<max_guesses<<" wrong guesses before you are hanged\n"
        "\t\tGood luck\n";

    while(wrongguesses < max_guesses)  {
        char newguess = 0;
        std::cout << "Word: " << targetword;
        std::cout << "\nGuessed Letters: " << guessedletters;
        std::cout << "\nWrong Guesses: " << wrongguesses;
        std::cout << "\nGuess #" << guessno << ":";
        std::cin >> newguess;
        std::cout << '\n';

        if (newguess >= 'a' && newguess <= 'z' && guessedletters.find(newguess)==std::string::npos) {
            ++guessno;
            guessedletters += newguess;
            std::sort(guessedletters.begin(), guessedletters.end());

            if (filter(length, newguess))
                ++wrongguesses;

            if (targetword.find('?') == std::string::npos)
                break;
        }
    }
    
    const char* selection = wordlist[rand()%wordlist.size()];
    targetword.assign(selection, length);

    if (wrongguesses == max_guesses)
        std::cout << "You ran out of guesses! The word was: " << targetword;
    else {
        std::cout << "You figured out the word " << targetword << " in " << guessno << " guesses!  What a miracle!";
    }

    return 0;
}

void loadwordlist(int length) {
    std::ifstream file("hangman.txt", std::ios::binary);
    std::getline(file, rawfile, '\0'); //read the entire file
    wordlist.clear();
    wordlist.reserve(rawfile.size()/6);
    for(auto it = rawfile.begin(); it != rawfile.end();) {
        auto it2 = it+1;
        while(it2 != rawfile.end() && *it2 != '\n')
            ++it2;
        if (it2-it == length)
            wordlist.push_back(&*it);
        if (it2 == rawfile.end()) 
            return;
        it = it2+1;
    }
}

bool filter(int length, char newguess) {
    if (wordlist.size() > 1) {
        static std::vector<int> letterpositions;
        letterpositions.assign(1<<length, 0);
        for(const char* s : wordlist) {
            unsigned flag = 0;
            for(int i=0; i<length; ++i) {
                if (s[i]==newguess)
                    flag |= (1<<i);
            }
            letterpositions[flag]++;
        }
        auto maxit = std::max_element(letterpositions.begin(), letterpositions.end());
        unsigned targetflag = maxit-letterpositions.begin();

        auto lambda = [=](const char* s)->bool {
            unsigned flag = 0;
            for(int i=0; i<length; ++i) {
                if (s[i]==newguess)
                    flag |= (1<<i);
            }
            return flag != targetflag;
        };
        auto it = std::remove_if(wordlist.begin(), wordlist.end(), lambda);
        wordlist.erase(it, wordlist.end());
        
        if (targetflag) {
            for(int i=0; i<length; ++i) {
                if ((1<<i) & targetflag)
                    targetword[i] = newguess;
            }
            return false;
        }
        return true;
    }
    bool retval = true;
    for(int i=0; i<length; ++i) {
        if (wordlist[0][i] == newguess) {
            targetword[i] = newguess;
            retval = false;
        }
    }
    return retval;
}