// Verificador de minimize_dfa. El juez lo llama así:  verificador NN.in NN.out salida
// Termina con 0 si la salida es correcta. Si no, escribe el motivo y termina con 1.
// Una salida es correcta si:
//   1. es un DFA bien formado y completo, en formato .dfa, sobre el alfabeto de la entrada;
//   2. tiene tantos estados como el DFA de NN.out, que es el mínimo;
//   3. reconoce el mismo lenguaje que el DFA de la entrada.
// Los nombres y el orden de los estados no importan. Como el mínimo es único salvo los
// nombres, un DFA equivalente con ese número de estados es el mínimo.
#include <cstddef>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

struct Dfa {
    std::vector<std::string> states;      // Q
    std::vector<char> alphabet;           // Σ
    std::vector<std::vector<int>> delta;  // δ, por posiciones
    int start = 0;                        // q0
    std::vector<bool> accept;             // F
};

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;
}

static bool valid_name(const std::string& name) {
    if (name.empty() || name.size() > 20 || name[0] == '#' || name.back() == ':') {
        return false;
    }
    for (char c : name) {
        if (static_cast<unsigned char>(c) <= ' ' || static_cast<unsigned char>(c) == 127) {
            return false;
        }
    }
    return true;
}

// Lee un DFA comprobando todo lo que el formato exige. Lanza std::runtime_error con el motivo.
static Dfa read_dfa(const std::string& path) {
    std::ifstream in(path);
    if (!in) {
        throw std::runtime_error("no se pudo abrir " + path);
    }
    int number = 0;
    auto fail = [&number](const std::string& message) {
        throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
    };
    auto next_line = [&in, &number](std::vector<std::string>& words) {
        std::string line;
        while (std::getline(in, line)) {
            number++;
            if (!line.empty() && line[0] == '#') {
                continue;
            }
            words = split_words(line);
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    auto field = [&next_line, &fail](const std::string& name) {
        std::vector<std::string> words;
        if (!next_line(words) || words[0] != name + ":") {
            fail("se esperaba el campo " + name + ":");
        }
        words.erase(words.begin());
        return words;
    };

    Dfa m;
    std::map<std::string, int> index;
    m.states = field("states");
    if (m.states.empty()) {
        fail("un DFA tiene al menos un estado");
    }
    for (const std::string& state : m.states) {
        if (!valid_name(state)) {
            fail("nombre de estado no válido: " + state);
        }
        if (!index.insert({state, static_cast<int>(index.size())}).second) {
            fail("estado repetido en states: " + state);
        }
    }
    std::map<char, int> symbol_index;
    for (const std::string& symbol : field("alphabet")) {
        if (symbol.size() != 1 || symbol[0] == '#') {
            fail("un símbolo es un solo carácter distinto de #: " + symbol);
        }
        if (!symbol_index.insert({symbol[0], static_cast<int>(symbol_index.size())}).second) {
            fail("símbolo repetido en alphabet: " + symbol);
        }
        m.alphabet.push_back(symbol[0]);
    }
    std::vector<std::string> start = field("start");
    if (start.size() != 1 || index.count(start[0]) == 0) {
        fail("start: lleva exactamente un estado de states");
    }
    m.start = index.at(start[0]);
    m.accept.assign(m.states.size(), false);
    for (const std::string& state : field("accept")) {
        if (index.count(state) == 0) {
            fail("el estado de aceptación " + state + " no está en states");
        }
        m.accept[static_cast<std::size_t>(index.at(state))] = true;
    }
    if (!field("delta").empty()) {
        fail("después de delta: las transiciones van una por línea");
    }
    m.delta.assign(m.states.size(), std::vector<int>(m.alphabet.size(), -1));
    std::vector<std::string> words;
    while (next_line(words)) {
        if (words.size() != 3 || words[1].size() != 1) {
            fail("una transición se escribe: estado símbolo destino");
        }
        if (index.count(words[0]) == 0 || index.count(words[2]) == 0) {
            fail("transición con un estado que no está en states");
        }
        if (symbol_index.count(words[1][0]) == 0) {
            fail("transición con un símbolo que no está en alphabet: " + words[1]);
        }
        int& target = m.delta[static_cast<std::size_t>(index.at(words[0]))]
                             [static_cast<std::size_t>(symbol_index.at(words[1][0]))];
        if (target != -1) {
            fail("transición repetida para (" + words[0] + ", " + words[1] + ")");
        }
        target = index.at(words[2]);
    }
    for (std::size_t i = 0; i < m.states.size(); i++) {
        for (std::size_t a = 0; a < m.alphabet.size(); a++) {
            if (m.delta[i][a] == -1) {
                throw std::runtime_error("falta la transición de " + m.states[i] + " con " +
                                         std::string(1, m.alphabet[a]) + ": la función de transición es total");
            }
        }
    }
    return m;
}

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cerr << "uso: verificador NN.in NN.out salida\n";
        return 2;
    }
    Dfa original, expected, answer;
    try {
        original = read_dfa(argv[1]);
        expected = read_dfa(argv[2]);
    } catch (const std::runtime_error& error) {
        std::cout << "error en los archivos del caso: " << error.what() << '\n';
        return 2;
    }
    try {
        answer = read_dfa(argv[3]);
    } catch (const std::runtime_error& error) {
        std::cout << "la salida no es un DFA: " << error.what() << '\n';
        return 1;
    }

    // 1. El mismo alfabeto, en cualquier orden.
    std::set<char> sigma_in(original.alphabet.begin(), original.alphabet.end());
    std::set<char> sigma_out(answer.alphabet.begin(), answer.alphabet.end());
    if (sigma_in != sigma_out) {
        std::cout << "el alfabeto de la salida no es el de la entrada\n";
        return 1;
    }
    // 2. El número de estados del mínimo.
    if (answer.states.size() != expected.states.size()) {
        std::cout << "la salida tiene " << answer.states.size() << " estados y el DFA mínimo tiene "
                  << expected.states.size() << '\n';
        return 1;
    }
    // 3. El mismo lenguaje. Se recorren a lo ancho los pares (p, q) a los que se llega leyendo
    // la misma cadena en los dos autómatas. Si en algún par uno acepta y el otro no, esa cadena
    // los separa, y es de las más cortas.
    std::size_t n1 = original.states.size();
    std::size_t n2 = answer.states.size();
    std::vector<int> column(original.alphabet.size());  // símbolo de la entrada → columna de la salida
    for (std::size_t a = 0; a < original.alphabet.size(); a++) {
        for (std::size_t b = 0; b < answer.alphabet.size(); b++) {
            if (answer.alphabet[b] == original.alphabet[a]) {
                column[a] = static_cast<int>(b);
            }
        }
    }
    const int unseen = -2;
    std::vector<int> parent(n1 * n2, unseen);  // de qué par se llegó, o -1 para el inicial
    std::vector<char> by(n1 * n2, 0);          // y con qué símbolo
    std::vector<std::size_t> order;
    std::size_t first = static_cast<std::size_t>(original.start) * n2 + static_cast<std::size_t>(answer.start);
    parent[first] = -1;
    order.push_back(first);
    for (std::size_t head = 0; head < order.size(); head++) {
        std::size_t p = order[head] / n2;
        std::size_t q = order[head] % n2;
        if (original.accept[p] != answer.accept[q]) {
            std::string w;
            for (std::size_t at = order[head]; parent[at] != -1; at = static_cast<std::size_t>(parent[at])) {
                w += by[at];
            }
            w = std::string(w.rbegin(), w.rend());
            std::cout << "no reconoce el mismo lenguaje: la cadena " << (w.empty() ? "vacía" : w)
                      << (original.accept[p] ? " está en el lenguaje y la salida la rechaza"
                                             : " no está en el lenguaje y la salida la acepta")
                      << '\n';
            return 1;
        }
        for (std::size_t a = 0; a < original.alphabet.size(); a++) {
            std::size_t next = static_cast<std::size_t>(original.delta[p][a]) * n2 +
                               static_cast<std::size_t>(answer.delta[q][static_cast<std::size_t>(column[a])]);
            if (parent[next] == unseen) {
                parent[next] = static_cast<int>(order[head]);
                by[next] = original.alphabet[a];
                order.push_back(next);
            }
        }
    }
    return 0;
}
