// Pruebas de la construcción de subconjuntos (sesión B): el DFA construido acepta lo mismo
// que el NFA, sigue al conjunto de estados activos cadena por cadena, y tiene los estados que
// dicen los apuntes.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <random>
#include <set>
#include <string>
#include <vector>

#include "kth.h"
#include "nfa.h"
#include "strings.h"
#include "test_helpers.h"

// El lema de la construcción: δ_D*(E({q0}), w) es el conjunto de estados activos de N con w.
// Y lo que importa: D acepta w si y solo si N acepta w. Devuelve cuántas cadenas revisó.
static std::size_t check_equivalent(const Nfa& n, const Dfa& d, std::size_t max_len) {
    std::vector<std::string> words = all_strings(n.alphabet, max_len);
    for (const std::string& w : words) {
        assert(delta_star(d, d.start, w) == set_name(n, delta_star(n, {n.start}, w)));
        assert(accepts(d, w) == accepts(n, w));
    }
    return words.size();
}

static void test_machines_of_notes() {
    // Tercero desde el final: 4 estados en el NFA, 8 subconjuntos alcanzables de 16.
    Nfa third = load_nfa("machines/third_from_end.nfa");
    std::vector<StateSet> subsets;
    Dfa d3 = subset_construction(third, &subsets);
    assert(d3.states.size() == 8 && subsets.size() == 8);
    assert(reachable(d3).size() == 8);
    assert(d3.start == "{q0}");
    assert(d3.accept == (std::set<std::string>{"{q0,q3}", "{q0,q1,q3}", "{q0,q2,q3}", "{q0,q1,q2,q3}"}));
    // Algunas casillas de la tabla de los apuntes.
    assert(step(d3, "{q0}", '1') == "{q0,q1}");
    assert(step(d3, "{q0,q1}", '0') == "{q0,q2}");
    assert(step(d3, "{q0,q1,q2}", '0') == "{q0,q2,q3}");
    assert(step(d3, "{q0,q3}", '0') == "{q0}");
    assert(step(d3, "{q0,q1,q2,q3}", '1') == "{q0,q1,q2,q3}");
    // Todos los subconjuntos alcanzables contienen a q0, y cada uno es de aceptación si tiene a q3.
    for (std::size_t i = 0; i < subsets.size(); i++) {
        assert(subsets[i].count("q0") == 1);
        assert((d3.accept.count(d3.states[i]) > 0) == (subsets[i].count("q3") > 0));
    }
    // La ejecución del DFA es la de run_nfa, conjunto por conjunto.
    assert(run(d3, "0110") ==
           (std::vector<std::string>{"{q0}", "{q0}", "{q0,q1}", "{q0,q1,q2}", "{q0,q2,q3}"}));
    check_equivalent(third, d3, 10);
    // El estado recuerda los tres últimos símbolos: las 8 cadenas de longitud 3 van a 8 estados distintos.
    std::set<std::string> ends;
    for (const std::string& w : all_strings({'0', '1'}, 3)) {
        if (w.size() == 3) {
            ends.insert(delta_star(d3, d3.start, w));
        }
    }
    assert(ends.size() == 8);

    // Contiene 101 o 11: con ε. 6 alcanzables.
    Nfa either = load_nfa("machines/contains_101_or_11.nfa");
    Dfa d_either = subset_construction(either);
    assert(d_either.states.size() == 6 && d_either.start == "{q0}");
    assert(step(d_either, "{q0}", '1') == "{q0,q1,q2}");  // la clausura ε agrega q2
    assert(step(d_either, "{q0,q1,q2}", '0') == "{q0,q2}");
    check_equivalent(either, d_either, 10);

    // a*b*c*: el inicial del DFA es E({qa}), y aparece el conjunto vacío como estado trampa.
    Nfa blocks = load_nfa("machines/abc_blocks.nfa");
    Dfa d_blocks = subset_construction(blocks);
    assert(d_blocks.states == (std::vector<std::string>{"{qa,qb,qc}", "{qb,qc}", "{qc}", "{}"}));
    assert(d_blocks.start == "{qa,qb,qc}" && d_blocks.accept.count("{qa,qb,qc}") == 1);
    assert(d_blocks.accept.count("{}") == 0);
    for (char a : blocks.alphabet) {
        assert(step(d_blocks, "{}", a) == "{}");
    }
    check_equivalent(blocks, d_blocks, 7);

    // Termina en 01: el NFA de 3 estados da un DFA de 3 estados, con el mismo lenguaje que el de la semana 1.
    Nfa ends_nfa = load_nfa("machines/ends_01.nfa");
    Dfa d_ends = subset_construction(ends_nfa);
    Dfa week1 = load_dfa("machines/ends_01.dfa");
    assert(d_ends.states == (std::vector<std::string>{"{q0}", "{q0,q1}", "{q0,q2}"}));
    for (const std::string& w : all_strings({'0', '1'}, 10)) {
        assert(accepts(d_ends, w) == accepts(week1, w));
    }
    check_equivalent(ends_nfa, d_ends, 10);

    // Un DFA pasado por la construcción sale igual, con cada estado q convertido en {q}.
    Dfa again = subset_construction(to_nfa(week1));
    assert(again.states == (std::vector<std::string>{"{q0}", "{q1}", "{q2}"}));
}

// La tabla de los apuntes: para "el k-ésimo símbolo desde el final es 1", el NFA tiene k + 1
// estados y la construcción da exactamente 2^k.
static void test_kth_table() {
    for (int k = 1; k <= 12; k++) {
        Nfa n = kth_from_end(k);
        Dfa d = subset_construction(n);
        assert(n.states.size() == static_cast<std::size_t>(k) + 1);
        assert(d.states.size() == (std::size_t{1} << k));
        if (k <= 6) {
            for (const std::string& w : all_strings({'0', '1'}, 10)) {
                bool in_language = w.size() >= static_cast<std::size_t>(k) && w[w.size() - k] == '1';
                assert(accepts(d, w) == in_language);
            }
        }
    }
}

static int test_random() {
    std::mt19937 rng(30303);
    int machines = 0;
    for (int round = 0; round < 200; round++) {
        Nfa n = random_nfa(rng, 1 + static_cast<int>(rng() % 6));
        Dfa d = subset_construction(n);
        assert(d.states.size() <= (std::size_t{1} << n.states.size()));
        assert(reachable(d).size() == d.states.size());
        check_equivalent(n, d, 6);
        // Y contra la definición por caminos, que no usa conjuntos.
        for (const std::string& w : all_strings(n.alphabet, 5)) {
            assert(accepts(d, w) == accepts_by_paths(n, w));
        }
        machines++;
    }
    return machines;
}

int main() {
    test_machines_of_notes();
    test_kth_table();
    int machines = test_random();
    std::printf("test_subset: ok (4 autómatas de los apuntes, k de 1 a 12, %d NFA al azar)\n", machines);
}
