// Verificador de "¿Son equivalentes dos DFA?". Lo llama el juez: verificador NN.in NN.out salida
// Cuando los autómatas son distintos hay muchas respuestas correctas, así que no se compara el
// texto. Se comprueba que la cadena entregada tiene la longitud de la respuesta de referencia,
// que es la mínima, y que de verdad un autómata la acepta y el otro no.
#include <algorithm>
#include <cstddef>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>

struct Dfa {
    std::vector<std::string> states;
    std::vector<char> alphabet;
    std::vector<int> delta;  // delta[i * |Σ| + j]
    int start = 0;
    std::vector<bool> accept;
    int symbol_index[256];
};

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

static Dfa read_dfa(std::istream& in) {
    Dfa m;
    std::fill(m.symbol_index, m.symbol_index + 256, -1);
    std::unordered_map<std::string, int> index;
    bool in_delta = false;
    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()) {
            continue;
        }
        if (words.size() == 1 && words[0] == "---") {
            break;
        }
        if (in_delta) {
            int from = index.at(words[0]);
            int symbol = m.symbol_index[static_cast<unsigned char>(words[1][0])];
            m.delta[static_cast<std::size_t>(from) * m.alphabet.size() + static_cast<std::size_t>(symbol)] =
                index.at(words[2]);
        } else if (words[0] == "states:") {
            for (std::size_t i = 1; i < words.size(); i++) {
                index[words[i]] = static_cast<int>(m.states.size());
                m.states.push_back(words[i]);
            }
        } else if (words[0] == "alphabet:") {
            for (std::size_t i = 1; i < words.size(); i++) {
                m.symbol_index[static_cast<unsigned char>(words[i][0])] = static_cast<int>(m.alphabet.size());
                m.alphabet.push_back(words[i][0]);
            }
        } else if (words[0] == "start:") {
            m.start = index.at(words[1]);
        } else if (words[0] == "accept:") {
            m.accept.assign(m.states.size(), false);
            for (std::size_t i = 1; i < words.size(); i++) {
                m.accept[static_cast<std::size_t>(index.at(words[i]))] = true;
            }
        } else if (words[0] == "delta:") {
            m.delta.assign(m.states.size() * m.alphabet.size(), 0);
            in_delta = true;
        }
    }
    return m;
}

// ¿M acepta w? Devuelve false en ok si w tiene un símbolo que no es del alfabeto.
static bool accepts(const Dfa& m, const std::string& w, bool& ok) {
    std::size_t q = static_cast<std::size_t>(m.start);
    for (char c : w) {
        int symbol = m.symbol_index[static_cast<unsigned char>(c)];
        if (symbol < 0) {
            ok = false;
            return false;
        }
        q = static_cast<std::size_t>(m.delta[q * m.alphabet.size() + static_cast<std::size_t>(symbol)]);
    }
    return m.accept[q];
}

static std::vector<std::string> read_words(const char* path) {
    std::ifstream file(path);
    std::vector<std::string> words;
    std::string word;
    while (file >> word) {
        words.push_back(word);
    }
    return words;
}

static int wrong(const std::string& message) {
    std::cout << message << '\n';
    return 1;
}

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cerr << "uso: verificador NN.in NN.out salida\n";
        return 2;
    }
    std::ifstream input(argv[1]);
    Dfa a = read_dfa(input);
    Dfa b = read_dfa(input);
    std::vector<std::string> expected = read_words(argv[2]);
    std::vector<std::string> got = read_words(argv[3]);

    if (got.empty()) {
        return wrong("la salida está vacía");
    }
    if (got[0] != "equivalentes" && got[0] != "distintos") {
        return wrong("la primera palabra debe ser equivalentes o distintos, salió " + got[0].substr(0, 30));
    }
    if (got[0] != expected[0]) {
        return wrong("esperaba " + expected[0] + ", salió " + got[0]);
    }
    if (got[0] == "equivalentes") {
        return got.size() == 1 ? 0 : wrong("después de equivalentes no va nada");
    }
    if (got.size() != 2) {
        return wrong("después de distintos va exactamente una cadena (eps si es la vacía)");
    }
    std::string w = got[1] == "eps" ? "" : got[1];
    std::string reference = expected[1] == "eps" ? "" : expected[1];
    bool ok = true;
    bool in_a = accepts(a, w, ok);
    bool in_b = accepts(b, w, ok);
    if (!ok) {
        return wrong("la cadena tiene símbolos que no son del alfabeto");
    }
    if (in_a == in_b) {
        return wrong(std::string("la cadena no separa a los autómatas: los dos la ") + (in_a ? "aceptan" : "rechazan"));
    }
    if (w.size() > reference.size()) {
        return wrong("la cadena separa a los autómatas pero no es de las más cortas: mide " +
                     std::to_string(w.size()) + " y hay una de " + std::to_string(reference.size()));
    }
    if (w.size() < reference.size()) {
        return wrong("la cadena es más corta que la de referencia: el caso está mal, avisen al docente");
    }
    return 0;
}
