// Escribe los autómatas de "el k-ésimo símbolo desde el final es 1" que usa el laboratorio.
// Uso: make_kth K CARPETA
//
//   kthK.nfa          el NFA de k + 1 estados de la semana 2
//   kthK_subsets.dfa  la construcción de subconjuntos, solo los subconjuntos alcanzables
//   kthK_all.dfa      la construcción de subconjuntos con los 2^(k+1) subconjuntos
//   kthK_history.dfa  un DFA escrito a mano: recuerda los últimos k símbolos, o menos si aún
//                     no leyó k; un estado por cada cadena de longitud a lo sumo k
//   kthK_min.dfa      el DFA mínimo, que sale de minimizar kthK_history.dfa
//   kthK_wrong.dfa    el mínimo con dos estados fusionados por error: ya no es equivalente
#include <cstddef>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "decide.h"
#include "dfa.h"
#include "minimize.h"
#include "nfa.h"

// El NFA: q0 se queda en q0 con todo y, con un 1, además adivina que ese es el k-ésimo desde
// el final. Después cuenta k − 1 símbolos más.
static Nfa kth_nfa(int k) {
    Nfa n;
    n.alphabet = {'0', '1'};
    for (int i = 0; i <= k; i++) {
        n.states.push_back("q" + std::to_string(i));
    }
    n.start = "q0";
    n.accept = {"q" + std::to_string(k)};
    n.delta[{"q0", '0'}] = {"q0"};
    n.delta[{"q0", '1'}] = {"q0", "q1"};
    for (int i = 1; i < k; i++) {
        for (char a : n.alphabet) {
            n.delta[{"q" + std::to_string(i), a}] = {"q" + std::to_string(i + 1)};
        }
    }
    return n;
}

// El DFA que recuerda lo último leído. El estado h seguido de una cadena u, con |u| ≤ k, dice:
// "lo leído termina en u" si |u| = k, y "lo leído es exactamente u" si |u| < k.
static Dfa kth_history(int k) {
    Dfa m;
    m.alphabet = {'0', '1'};
    std::vector<std::string> histories = {""};
    for (std::size_t i = 0; i < histories.size(); i++) {
        if (histories[i].size() < static_cast<std::size_t>(k)) {
            histories.push_back(histories[i] + "0");
            histories.push_back(histories[i] + "1");
        }
    }
    for (const std::string& u : histories) {
        std::string name = "h" + u;
        m.states.push_back(name);
        if (u.size() == static_cast<std::size_t>(k) && u[0] == '1') {
            m.accept.insert(name);
        }
        for (char a : m.alphabet) {
            std::string next = u + a;
            if (next.size() > static_cast<std::size_t>(k)) {
                next = next.substr(1);
            }
            m.delta[{name, a}] = "h" + next;
        }
    }
    m.start = "h";
    check_dfa(m);
    return m;
}

static void save(const std::string& path, const std::string& comment, const Dfa& m) {
    std::ofstream file(path);
    if (!file) {
        throw std::runtime_error("no se pudo escribir " + path);
    }
    file << comment;
    write_dfa(file, m);
}

int main(int argc, char** argv) {
    if (argc != 3 || std::atoi(argv[1]) < 1 || std::atoi(argv[1]) > 10) {
        std::cerr << "uso: make_kth K CARPETA, con K de 1 a 10\n";
        return 2;
    }
    try {
        int k = std::atoi(argv[1]);
        std::string base = std::string(argv[2]) + "/kth" + std::to_string(k);
        std::string title = "# El símbolo número " + std::to_string(k) + " desde el final es 1.\n";

        Nfa n = kth_nfa(k);
        {
            std::ofstream file(base + ".nfa");
            if (!file) {
                throw std::runtime_error("no se pudo escribir " + base + ".nfa");
            }
            file << title << "# El NFA de " << k + 1 << " estados.\nstates:";
            for (const std::string& q : n.states) {
                file << ' ' << q;
            }
            file << "\nalphabet: 0 1\nstart: q0\naccept: q" << k << "\ndelta:\n";
            for (const auto& [key, targets] : n.delta) {
                file << key.first << ' ' << key.second;
                for (const std::string& q : targets) {
                    file << ' ' << q;
                }
                file << '\n';
            }
        }
        Dfa subsets = subset_construction(n);
        Dfa all = subset_construction(n, true);
        Dfa history = kth_history(k);
        Dfa minimal = minimize(history);
        save(base + "_subsets.dfa", title + "# Construcción de subconjuntos del NFA: solo los subconjuntos alcanzables.\n", subsets);
        save(base + "_all.dfa", title + "# Construcción de subconjuntos del NFA con todos los subconjuntos, alcanzables o no.\n", all);
        save(base + "_history.dfa", title + "# Recuerda los últimos símbolos leídos: un estado por cada cadena de longitud a lo sumo " +
                                        std::to_string(k) + ".\n", history);
        save(base + "_min.dfa", title + "# El DFA mínimo: sale de minimizar el que recuerda los últimos símbolos.\n", minimal);

        // El error de la semana 4: fusionar dos estados porque "se parecen". Aquí, el estado al
        // que se llega con 11 se fusiona con el estado al que se llega con 10.
        Dfa wrong = minimal;
        std::string kept = delta_star(minimal, minimal.start, "10");
        std::string gone = delta_star(minimal, minimal.start, "11");
        for (auto& [key, target] : wrong.delta) {
            if (target == gone) {
                target = kept;
            }
        }
        wrong = remove_unreachable(wrong);
        save(base + "_wrong.dfa", title + "# El DFA mínimo con dos estados fusionados por error. No es equivalente a los otros.\n", wrong);

        std::cout << "k = " << k << '\n';
        std::cout << "archivo               estados  alcanzables\n";
        auto row = [](const std::string& name, const Dfa& m) {
            std::string count = std::to_string(m.states.size());
            std::string reach = std::to_string(reachable(m).size());
            std::cout << name << std::string(22 - name.size(), ' ') << std::string(7 - count.size(), ' ') << count
                      << std::string(13 - reach.size(), ' ') << reach << '\n';
        };
        std::string stem = "kth" + std::to_string(k);
        row(stem + "_subsets.dfa", subsets);
        row(stem + "_all.dfa", all);
        row(stem + "_history.dfa", history);
        row(stem + "_min.dfa", minimal);
        row(stem + "_wrong.dfa", wrong);
        std::cout << "minimizar " << stem << "_subsets.dfa da " << minimize(subsets).states.size() << " estados\n";
        if (!compare(subsets, all).equivalent || !compare(subsets, history).equivalent ||
            !compare(subsets, minimal).equivalent) {
            throw std::runtime_error("los autómatas generados no son equivalentes");
        }
        std::cout << "los cuatro primeros son equivalentes\n";
        Comparison broken = compare(minimal, wrong);
        if (broken.equivalent) {
            throw std::runtime_error("el autómata con el error salió equivalente");
        }
        std::cout << stem << "_min.dfa y " << stem << "_wrong.dfa se separan con " << show(broken.witness) << '\n';
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
