// Verificador de "De NFA a DFA": verificador ENTRADA ESPERADA SALIDA
// Hay muchos DFA correctos para un mismo NFA, así que no compara textos. Comprueba que SALIDA
//   1. es un DFA bien formado, en formato .dfa, con el mismo alfabeto que el NFA de ENTRADA;
//   2. respeta los límites del enunciado: a lo sumo 10 000 estados, nombres de hasta 20 caracteres;
//   3. reconoce el mismo lenguaje que el NFA.
// Para el punto 3 recorre a la vez el NFA (con su conjunto de estados activos) y el DFA
// entregado, como en la construcción del producto, y busca un par alcanzable en el que uno
// acepte y el otro no. Si lo encuentra, imprime la cadena más corta que lleva hasta él.
// ESPERADA (una respuesta correcta) no se usa. Termina con 0 si la salida es correcta.
#include <cstddef>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using Mask = std::uint64_t;

constexpr std::size_t MAX_STATES = 10000;
constexpr std::size_t MAX_NAME = 20;

struct Nfa {
    std::vector<std::string> states;
    std::vector<char> alphabet;
    std::vector<std::vector<Mask>> delta;  // delta[i][j]: destinos del estado i con alphabet[j]
    std::vector<Mask> eps;                 // eps[i]: destinos del estado i con ε
    int start = 0;
    Mask accept = 0;
};

struct Dfa {
    std::vector<std::string> states;
    std::vector<std::vector<int>> delta;  // delta[i][j]: destino del estado i con el símbolo j del NFA
    int start = 0;
    std::vector<bool> accept;
};

static std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

// Las líneas de una descripción que no son comentarios ni están vacías, ya separadas en palabras.
static std::vector<std::vector<std::string>> read_lines(std::istream& in) {
    std::vector<std::vector<std::string>> lines;
    std::string line;
    while (std::getline(in, line)) {
        if (!line.empty() && line[0] == '#') {
            continue;
        }
        std::vector<std::string> words = split_words(line);
        if (!words.empty()) {
            lines.push_back(words);
        }
    }
    return lines;
}

// La entrada la escribió el curso: se lee sin revisar.
static Nfa read_nfa(std::istream& in) {
    Nfa n;
    std::map<std::string, int> index;
    std::map<char, int> column;
    bool in_delta = false;
    for (const std::vector<std::string>& words : read_lines(in)) {
        if (in_delta) {
            int from = index.at(words[0]);
            for (std::size_t i = 2; i < words.size(); i++) {
                Mask bit = Mask{1} << index.at(words[i]);
                if (words[1] == "eps") {
                    n.eps[from] |= bit;
                } else {
                    n.delta[from][column.at(words[1][0])] |= bit;
                }
            }
        } else if (words[0] == "states:") {
            n.states.assign(words.begin() + 1, words.end());
            for (std::size_t i = 0; i < n.states.size(); i++) {
                index[n.states[i]] = static_cast<int>(i);
            }
        } else if (words[0] == "alphabet:") {
            for (std::size_t i = 1; i < words.size(); i++) {
                column[words[i][0]] = static_cast<int>(n.alphabet.size());
                n.alphabet.push_back(words[i][0]);
            }
        } else if (words[0] == "start:") {
            n.start = index.at(words[1]);
        } else if (words[0] == "accept:") {
            for (std::size_t i = 1; i < words.size(); i++) {
                n.accept |= Mask{1} << index.at(words[i]);
            }
        } else if (words[0] == "delta:") {
            in_delta = true;
            n.delta.assign(n.states.size(), std::vector<Mask>(n.alphabet.size(), 0));
            n.eps.assign(n.states.size(), 0);
        }
    }
    return n;
}

// Lee el DFA entregado, revisando todo. Si algo está mal, deja el motivo en error y devuelve false.
static bool read_dfa(std::istream& in, const Nfa& n, Dfa& d, std::string& error) {
    std::vector<std::vector<std::string>> lines = read_lines(in);
    const char* fields[] = {"states:", "alphabet:", "start:", "accept:", "delta:"};
    if (lines.size() < 5) {
        error = "la salida no tiene los cinco campos states:, alphabet:, start:, accept: y delta:";
        return false;
    }
    for (int i = 0; i < 5; i++) {
        if (lines[i][0] != fields[i]) {
            error = std::string("se esperaba el campo ") + fields[i] + " y salió " + lines[i][0];
            return false;
        }
    }

    // states:
    d.states.assign(lines[0].begin() + 1, lines[0].end());
    if (d.states.empty()) {
        error = "states: no tiene ningún estado";
        return false;
    }
    if (d.states.size() > MAX_STATES) {
        error = "el DFA tiene " + std::to_string(d.states.size()) + " estados, y el límite es " +
                std::to_string(MAX_STATES) + ": construyan solo los subconjuntos alcanzables";
        return false;
    }
    std::unordered_map<std::string, int> index;
    for (std::size_t i = 0; i < d.states.size(); i++) {
        const std::string& name = d.states[i];
        if (name.size() > MAX_NAME) {
            error = "el nombre " + name.substr(0, 30) + "… pasa de " + std::to_string(MAX_NAME) + " caracteres";
            return false;
        }
        if (name.back() == ':') {
            error = "el nombre " + name + " termina con dos puntos";
            return false;
        }
        if (!index.insert({name, static_cast<int>(i)}).second) {
            error = "el estado " + name + " está repetido en states:";
            return false;
        }
    }

    // alphabet: los mismos símbolos que el NFA, en cualquier orden.
    std::map<char, int> column;
    for (std::size_t j = 0; j < n.alphabet.size(); j++) {
        column[n.alphabet[j]] = static_cast<int>(j);
    }
    std::set<char> sigma;
    for (std::size_t i = 1; i < lines[1].size(); i++) {
        const std::string& symbol = lines[1][i];
        if (symbol.size() != 1 || column.count(symbol[0]) == 0) {
            error = "el símbolo " + symbol + " no está en el alfabeto del NFA";
            return false;
        }
        if (!sigma.insert(symbol[0]).second) {
            error = "el símbolo " + symbol + " está repetido en alphabet:";
            return false;
        }
    }
    if (sigma.size() != n.alphabet.size()) {
        error = "al alfabeto del DFA le faltan símbolos del NFA";
        return false;
    }

    // start: y accept:
    if (lines[2].size() != 2 || index.count(lines[2][1]) == 0) {
        error = "start: lleva exactamente un estado, que debe estar en states:";
        return false;
    }
    d.start = index[lines[2][1]];
    d.accept.assign(d.states.size(), false);
    for (std::size_t i = 1; i < lines[3].size(); i++) {
        if (index.count(lines[3][i]) == 0) {
            error = "el estado de aceptación " + lines[3][i] + " no está en states:";
            return false;
        }
        d.accept[index[lines[3][i]]] = true;
    }

    // delta: exactamente una línea por cada par de estado y símbolo.
    if (lines[4].size() != 1) {
        error = "después de delta: las transiciones van una por línea";
        return false;
    }
    d.delta.assign(d.states.size(), std::vector<int>(n.alphabet.size(), -1));
    for (std::size_t k = 5; k < lines.size(); k++) {
        const std::vector<std::string>& words = lines[k];
        if (words.size() != 3) {
            error = "una transición de un DFA se escribe: estado símbolo destino. Salió una línea con " +
                    std::to_string(words.size()) + " palabras que empieza con " + words[0].substr(0, 30);
            return false;
        }
        if (index.count(words[0]) == 0 || index.count(words[2]) == 0) {
            error = "la transición " + words[0] + " " + words[1] + " " + words[2] + " usa un estado que no está en states:";
            return false;
        }
        if (words[1].size() != 1 || column.count(words[1][0]) == 0) {
            error = "la transición " + words[0] + " " + words[1] + " " + words[2] + " usa un símbolo que no está en el alfabeto";
            return false;
        }
        int& cell = d.delta[index[words[0]]][column[words[1][0]]];
        if (cell != -1) {
            error = "hay dos transiciones para δ(" + words[0] + ", " + words[1] + "): no es un DFA";
            return false;
        }
        cell = index[words[2]];
    }
    for (std::size_t i = 0; i < d.states.size(); i++) {
        for (std::size_t j = 0; j < n.alphabet.size(); j++) {
            if (d.delta[i][j] == -1) {
                error = "falta la transición δ(" + d.states[i] + ", " + n.alphabet[j] + "): en un DFA, δ es total";
                return false;
            }
        }
    }
    return true;
}

static Mask eps_closure(const Nfa& n, Mask set) {
    Mask closure = set;
    for (bool changed = true; changed;) {
        changed = false;
        for (std::size_t i = 0; i < n.states.size(); i++) {
            if (((closure >> i) & 1) && (n.eps[i] & ~closure) != 0) {
                closure |= n.eps[i];
                changed = true;
            }
        }
    }
    return closure;
}

// Un par alcanzable: el conjunto de estados activos del NFA y el estado del DFA entregado,
// con el par del que se llegó y el símbolo, para reconstruir la cadena.
struct Pair {
    int subset;
    int state;
    int parent;
    char symbol;
};

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cout << "uso: verificador ENTRADA ESPERADA SALIDA\n";
        return 2;
    }
    std::ifstream input(argv[1]);
    std::ifstream output(argv[3]);
    if (!input || !output) {
        std::cout << "no se pudo abrir la entrada o la salida\n";
        return 2;
    }
    Nfa n = read_nfa(input);
    Dfa d;
    std::string error;
    if (!read_dfa(output, n, d, error)) {
        std::cout << error << '\n';
        return 1;
    }

    // closed[i][j] = E(δ(i, alphabet[j])).
    std::size_t symbols = n.alphabet.size();
    std::vector<std::vector<Mask>> closed(n.states.size(), std::vector<Mask>(symbols, 0));
    for (std::size_t i = 0; i < n.states.size(); i++) {
        for (std::size_t j = 0; j < symbols; j++) {
            closed[i][j] = eps_closure(n, n.delta[i][j]);
        }
    }

    // Recorrido en anchura de los pares (conjunto activo del NFA, estado del DFA).
    std::vector<Mask> subsets = {eps_closure(n, Mask{1} << n.start)};
    std::unordered_map<Mask, int> number = {{subsets[0], 0}};
    std::vector<Pair> pairs = {{0, d.start, -1, ' '}};
    std::unordered_set<std::uint64_t> seen = {static_cast<std::uint64_t>(d.start)};
    for (std::size_t at = 0; at < pairs.size(); at++) {
        Pair current = pairs[at];
        Mask set = subsets[current.subset];
        bool nfa_accepts = (set & n.accept) != 0;
        bool dfa_accepts = d.accept[current.state];
        if (nfa_accepts != dfa_accepts) {
            std::string w;
            for (int k = static_cast<int>(at); pairs[k].parent != -1; k = pairs[k].parent) {
                w = pairs[k].symbol + w;
            }
            std::string shown = w.empty() ? "la cadena vacía" : "la cadena " + (w.size() > 60 ? w.substr(0, 60) + "…" : w);
            std::cout << "no reconocen el mismo lenguaje: " << shown
                      << (nfa_accepts ? " la acepta el NFA y la rechaza el DFA" : " la rechaza el NFA y la acepta el DFA")
                      << '\n';
            return 1;
        }
        for (std::size_t j = 0; j < symbols; j++) {
            Mask target = 0;
            for (std::size_t i = 0; i < n.states.size(); i++) {
                if ((set >> i) & 1) {
                    target |= closed[i][j];
                }
            }
            auto [it, is_new] = number.insert({target, static_cast<int>(subsets.size())});
            if (is_new) {
                subsets.push_back(target);
            }
            int next_state = d.delta[current.state][j];
            std::uint64_t key = static_cast<std::uint64_t>(it->second) * (MAX_STATES + 1) +
                                static_cast<std::uint64_t>(next_state);
            if (seen.insert(key).second) {
                pairs.push_back({it->second, next_state, static_cast<int>(at), n.alphabet[j]});
            }
        }
    }
    return 0;
}
