// Pruebas de la minimización: las particiones de los apuntes, que el resultado es equivalente
// al original y que no se puede reducir más.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <optional>
#include <random>
#include <set>
#include <string>
#include <vector>

#include "dfa.h"
#include "distinguish.h"
#include "minimize.h"

using Blocks = std::vector<std::vector<std::string>>;

static bool same_up_to(const Dfa& m1, const Dfa& m2, std::size_t max_len) {
    for (const std::string& w : all_strings(m1.alphabet, max_len)) {
        if (accepts(m1, w) != accepts(m2, w)) {
            return false;
        }
    }
    return true;
}

// Lo que tiene que cumplir el resultado de minimize, sea cual sea la máquina.
static void check_minimal(const Dfa& m, std::size_t expected_states, std::size_t max_len) {
    Dfa minimal = minimize(m);
    assert(minimal.states.size() == expected_states);
    // Equivalente: con todas las cadenas hasta max_len, y sin límite con el recorrido de pares.
    assert(same_up_to(m, minimal, max_len));
    assert(!difference_witness(m, minimal));
    // Mínimo: todos sus estados son alcanzables y distinguibles dos a dos.
    assert(reachable(minimal).size() == minimal.states.size());
    for (const std::string& p : minimal.states) {
        for (const std::string& q : minimal.states) {
            assert((p == q) == !state_distinguishing_suffix(minimal, p, q));
        }
    }
    // Minimizar otra vez no cambia nada, y coincide con el autómata de las clases.
    assert(isomorphic(minimal, minimize(minimal)));
    assert(isomorphic(minimal, nerode_dfa(m)));
    assert(equivalent(m, minimal));
}

// El ejemplo paso a paso de los apuntes.
static void test_contains_1001() {
    Dfa m = load_dfa("machines/contains_1001.dfa");
    assert(m.states.size() == 8 && reachable(m).size() == 7 && reachable(m).count("q7") == 0);
    Dfa trimmed = remove_unreachable(m);
    std::vector<Partition> rounds = moore_rounds(trimmed);
    assert(rounds.size() == 4);  // P0, P1, P2, P3; la ronda 4 ya no cambia nada
    assert(blocks_of(trimmed, rounds[0]) == (Blocks{{"q0", "q1", "q2", "q3", "q4"}, {"q5", "q6"}}));
    assert(blocks_of(trimmed, rounds[1]) == (Blocks{{"q0", "q1", "q2", "q4"}, {"q3"}, {"q5", "q6"}}));
    assert(blocks_of(trimmed, rounds[2]) == (Blocks{{"q0", "q1", "q4"}, {"q2"}, {"q3"}, {"q5", "q6"}}));
    assert(blocks_of(trimmed, rounds[3]) == (Blocks{{"q0", "q4"}, {"q1"}, {"q2"}, {"q3"}, {"q5", "q6"}}));
    assert(refine(trimmed, rounds[3]) == rounds[3]);

    // P_k junta exactamente a los estados que ningún sufijo de longitud ≤ k separa.
    for (std::size_t k = 0; k < rounds.size(); k++) {
        for (const std::string& p : trimmed.states) {
            for (const std::string& q : trimmed.states) {
                std::optional<std::string> z = state_distinguishing_suffix(trimmed, p, q);
                bool separated_by_short = z.has_value() && z->size() <= k;
                assert((rounds[k].block.at(p) == rounds[k].block.at(q)) == !separated_by_short);
            }
        }
    }

    check_minimal(m, 5, 12);
    Dfa minimal = minimize(m);
    assert(minimal.states == (std::vector<std::string>{"{q0,q4}", "q1", "q2", "q3", "{q5,q6}"}));
    assert(minimal.start == "{q0,q4}" && minimal.accept == (std::set<std::string>{"{q5,q6}"}));
    for (const std::string& w : all_strings({'0', '1'}, 12)) {
        assert(accepts(minimal, w) == (w.find("1001") != std::string::npos));
    }
    // q0 y q1 "se parecen" y no son equivalentes: el sufijo más corto que los separa mide 3.
    assert(*state_distinguishing_suffix(m, "q0", "q1") == "001");
    assert(!state_distinguishing_suffix(m, "q0", "q4"));
    assert(!state_distinguishing_suffix(m, "q5", "q6"));

    // Sin quitar q7 primero, el resultado tiene un estado de más: 6.
    std::vector<Partition> with_all = moore_rounds(m);
    assert(with_all.back().count == 6);
    Dfa six = quotient(m, with_all.back());
    assert(six.states.size() == 6 && same_up_to(six, m, 12) && reachable(six).size() == 5);
}

// Los otros autómatas de machines/.
static void test_machines() {
    // El de 7 estados de la semana 1 se reduce al de 3, que es el mismo salvo nombres.
    Dfa seven = load_dfa("machines/ends_01_seven.dfa");
    Dfa three = load_dfa("machines/ends_01.dfa");
    check_minimal(seven, 3, 12);
    std::vector<Partition> rounds = moore_rounds(seven);
    assert(rounds.size() == 2);
    assert(blocks_of(seven, rounds[0]) == (Blocks{{"e", "0", "1", "00", "10", "11"}, {"01"}}));
    assert(blocks_of(seven, rounds[1]) == (Blocks{{"e", "1", "11"}, {"0", "00", "10"}, {"01"}}));
    assert(isomorphic(minimize(seven), three));
    assert(equivalent(seven, three));

    Dfa mod6 = load_dfa("machines/multiple_of_3_mod6.dfa");
    check_minimal(mod6, 3, 12);
    assert(isomorphic(minimize(mod6), load_dfa("machines/multiple_of_3.dfa")));

    // Ya eran mínimos.
    check_minimal(three, 3, 12);
    check_minimal(load_dfa("machines/contains_101.dfa"), 4, 12);
    check_minimal(load_dfa("machines/multiple_of_3.dfa"), 3, 12);
    check_minimal(load_dfa("machines/count_attempt.dfa"), 8, 12);
    check_minimal(load_dfa("machines/last_3.dfa"), 8, 12);

    // Dos lenguajes distintos, y la cadena más corta que los separa.
    Dfa a = load_dfa("machines/contains_101.dfa");
    Dfa b = load_dfa("machines/contains_1001.dfa");
    assert(!equivalent(a, b));
    assert(*difference_witness(a, b) == "101");
}

// El k-ésimo símbolo desde el final: 2^k estados antes y después, y k − 1 rondas que cambian algo.
static void test_last_k() {
    for (int k = 1; k <= 8; k++) {
        Dfa m = last_k_dfa(k);
        std::vector<Partition> rounds = moore_rounds(m);
        assert(rounds.size() == static_cast<std::size_t>(k));
        assert(rounds.back().count == (1 << k));
        assert(minimize(m).states.size() == (std::size_t{1} << k));
    }
    check_minimal(last_k_dfa(4), 16, 10);
    // El de k = 6, que es el del laboratorio: 64 estados, y el mínimo también.
    Dfa six = last_k_dfa(6);
    Dfa minimal = minimize(six);
    assert(minimal.states.size() == 64 && isomorphic(minimal, six) && !difference_witness(six, minimal));
}

// Casos de borde: F = ∅ y F = Q dan un solo estado.
static void test_edges() {
    Dfa m = load_dfa("machines/contains_1001.dfa");
    Dfa none = m;
    none.accept.clear();
    check_minimal(none, 1, 10);
    assert(initial_partition(none).count == 1);
    Dfa all = m;
    all.accept = std::set<std::string>(m.states.begin(), m.states.end());
    check_minimal(all, 1, 10);
    assert(minimize(all).accept.size() == 1 && minimize(none).accept.empty());
}

// DFA al azar, con semilla fija: el número de estados del mínimo coincide con el número de
// comportamientos distintos, contados por fuerza bruta con todas las cadenas hasta |Q|.
static void test_random() {
    std::mt19937 rng(40404);
    for (int round = 0; round < 120; round++) {
        std::size_t n = 1 + rng() % 7;
        std::size_t symbols = 1 + rng() % 3;
        Dfa m;
        for (std::size_t i = 0; i < n; i++) {
            m.states.push_back("s" + std::to_string(i));
        }
        for (std::size_t a = 0; a < symbols; a++) {
            m.alphabet.push_back(static_cast<char>('a' + a));
        }
        m.start = m.states[rng() % n];
        for (const std::string& state : m.states) {
            if (rng() % 3 == 0) {
                m.accept.insert(state);
            }
            for (char a : m.alphabet) {
                m.delta[{state, a}] = m.states[rng() % n];
            }
        }
        std::vector<std::string> suffixes = all_strings(m.alphabet, n);
        std::set<std::vector<bool>> behaviours;
        for (const std::string& state : reachable(m)) {
            std::vector<bool> behaviour;
            for (const std::string& z : suffixes) {
                behaviour.push_back(m.accept.count(delta_star(m, state, z)) > 0);
            }
            behaviours.insert(behaviour);
        }
        check_minimal(m, behaviours.size(), 7);
        // El sufijo más corto que separa dos estados mide a lo sumo |Q| − 1.
        for (const std::string& p : m.states) {
            for (const std::string& q : m.states) {
                std::optional<std::string> z = state_distinguishing_suffix(m, p, q);
                assert(!z || z->size() + 1 <= n);
            }
        }
    }
}

int main() {
    test_contains_1001();
    test_machines();
    test_last_k();
    test_edges();
    test_random();
    std::printf("test_minimize: ok\n");
}
