// Pruebas de la sesión A: la división del lema sacada de un DFA, y las partidas del capítulo.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>

#include "dfa.h"
#include "distinguish.h"
#include "pumping.h"

// El lema, comprobado en un DFA: para toda cadena w con |Q| ≤ |w| ≤ max_len, la división que
// sale del primer estado repetido cumple las tres condiciones con p = |Q|.
static std::size_t check_lemma(const Dfa& m, std::size_t max_len) {
    std::size_t p = m.states.size();
    std::size_t checked = 0;
    for (const std::string& w : all_strings(m.alphabet, max_len)) {
        if (w.size() < p) {
            continue;
        }
        PumpSplit found = pump_split(m, w);
        const Split& s = found.split;
        assert(s.x + s.y + s.z == w);
        assert(!s.y.empty());                   // |y| > 0
        assert(s.x.size() + s.y.size() <= p);  // |xy| ≤ p
        // El ciclo: x lleva al estado repetido, e y vuelve a él.
        assert(delta_star(m, m.start, s.x) == found.state);
        assert(delta_star(m, found.state, s.y) == found.state);
        // Por eso x y^i z termina donde termina w: si w ∈ L, todas están en L.
        for (std::size_t i = 0; i <= 5; i++) {
            assert(delta_star(m, m.start, pumped(s, i)) == delta_star(m, m.start, w));
        }
        checked++;
    }
    return checked;
}

static void test_lemma_on_machines() {
    std::size_t total = 0;
    for (const char* path : {"machines/ends_01.dfa", "machines/contains_101.dfa", "machines/multiple_of_3.dfa",
                             "machines/ends_01_seven.dfa", "machines/contains_1001.dfa",
                             "machines/count_attempt.dfa", "machines/last_3.dfa"}) {
        total += check_lemma(load_dfa(path), 11);
    }
    assert(total > 20000);

    // Las dos ejecuciones copiadas en los apuntes.
    Dfa three = load_dfa("machines/multiple_of_3.dfa");
    PumpSplit a = pump_split(three, "10101");
    assert(a.split.x == "10" && a.split.y == "1" && a.split.z == "01");
    assert(a.state == "r2" && a.first == 2 && a.second == 3);
    for (const char* w : {"1001", "10101", "101101", "1011101", "10111101"}) {
        assert(accepts(three, w));  // 9, 21, 45, 93, 189: múltiplos de 3
    }
    Dfa attempt = load_dfa("machines/count_attempt.dfa");
    PumpSplit b = pump_split(attempt, "00000000111");
    assert(b.split.x == "000" && b.split.y == "0" && b.split.z == "0000111");
    assert(b.state == "z3" && b.first == 3 && b.second == 4);
}

// El intento de la introducción: acierta con 0^n 1^n hasta n = 3 y después acepta de más.
static void test_count_attempt() {
    Dfa attempt = load_dfa("machines/count_attempt.dfa");
    assert(attempt.states.size() == 8);
    for (const char* w : {"", "01", "0011", "000111"}) {
        assert(accepts(attempt, w));
    }
    assert(accepts(attempt, "00000111") && !in_zeros_ones("00000111"));   // acepta de más
    assert(!accepts(attempt, "00001111") && in_zeros_ones("00001111"));   // y de menos
    for (const std::string& w : all_strings({'0', '1'}, 12)) {
        std::size_t zeros = count_symbol(w, '0');
        std::size_t ones = count_symbol(w, '1');
        bool expected = is_block_pair(w, '0', '1') && ((zeros <= 3 && ones == zeros) || (zeros >= 3 && ones == 3));
        assert(accepts(attempt, w) == expected);
    }
}

static const Game& game_named(const std::vector<Game>& games, const char* name) {
    for (const Game& game : games) {
        if (game.name == name) {
            return game;
        }
    }
    assert(false);
    return games[0];
}

// Las partidas bien jugadas: para cada p, la cadena está en L, mide al menos p, y en TODAS las
// divisiones permitidas el exponente del capítulo saca la cadena de L.
static void test_games() {
    std::vector<Game> games = chapter_games();
    for (const char* name : {"0n1n", "iguales", "ww", "cuadrados", "mas-ceros"}) {
        const Game& game = game_named(games, name);
        for (std::size_t p = 1; p <= 12; p++) {
            std::string s = game.choose_string(p);
            assert(game.in_language(s) && s.size() >= p);
            std::vector<Split> splits = legal_splits(s, p);
            assert(splits.size() == p * (p + 1) / 2);
            for (const Split& split : splits) {
                // En las cinco, |xy| ≤ p obliga a que y sea solo ceros.
                assert(count_symbol(split.y, '0') == split.y.size());
                assert(!game.in_language(pumped(split, game.exponent)));
            }
            assert(surviving_splits(game, p).empty());
        }
    }
    // Lo que dicen las demostraciones sobre la cadena bombeada, con y = 0^k.
    for (std::size_t p = 1; p <= 10; p++) {
        for (const Split& split : legal_splits(game_named(games, "ww").choose_string(p), p)) {
            std::size_t k = split.y.size();
            assert(pumped(split, 2) == std::string(p + k, '0') + "1" + std::string(p, '0') + "1");
        }
        for (const Split& split : legal_splits(game_named(games, "cuadrados").choose_string(p), p)) {
            std::size_t length = pumped(split, 2).size();
            assert(p * p < length && length < (p + 1) * (p + 1));  // entre dos cuadrados seguidos
        }
        for (const Split& split : legal_splits(game_named(games, "mas-ceros").choose_string(p), p)) {
            std::size_t k = split.y.size();
            assert(pumped(split, 0) == std::string(p + 1 - k, '0') + std::string(p, '1'));
            for (std::size_t i = 1; i <= 6; i++) {
                assert(in_more_zeros(pumped(split, i)));  // hacia arriba no se sale nunca
            }
        }
    }
}

// Las partidas mal jugadas: el adversario tiene una división que resiste todos los exponentes.
static void test_bad_games() {
    std::vector<Game> games = chapter_games();
    for (std::size_t p = 2; p <= 10; p++) {
        // (01)^p con y = 01: x y^i z = (01)^(p-1+i).
        std::string s = game_named(games, "iguales-mal").choose_string(p);
        Split split = {"", "01", s.substr(2)};
        assert(in_equal(s) && s.size() >= p);
        // 0^(2p) con y = 00.
        std::string t = game_named(games, "ww-mal").choose_string(p);
        Split even = {"", "00", t.substr(2)};
        assert(in_ww(t) && t.size() >= p);
        for (std::size_t i = 0; i <= 8; i++) {
            assert(in_equal(pumped(split, i)));
            assert(in_ww(pumped(even, i)));
        }
        assert(!surviving_splits(game_named(games, "iguales-mal"), p).empty());
        assert(!surviving_splits(game_named(games, "ww-mal"), p).empty());
        // Bombear hacia arriba en { 0^i 1^j : i > j }: resisten todas las divisiones.
        assert(surviving_splits(game_named(games, "mas-ceros-mal"), p).size() == p * (p + 1) / 2);
    }
    // Las salidas copiadas en los apuntes.
    assert(surviving_splits(game_named(games, "iguales-mal"), 3).size() == 2);
}

// Cierre: (tantos 0 como 1) ∩ 0*1* = { 0^n 1^n }.
static void test_closure() {
    for (const std::string& w : all_strings({'0', '1'}, 12)) {
        assert((in_equal(w) && is_block_pair(w, '0', '1')) == in_zeros_ones(w));
    }
}

// El lenguaje que cumple el lema sin ser regular: { a^i b^j c^k : si i = 1 entonces j = k }.
static void test_trap_language() {
    std::size_t checked = 0;
    for (const std::string& s : all_strings({'a', 'b', 'c'}, 8)) {
        if (s.size() < 2 || !in_trap(s)) {
            continue;
        }
        Split split = trap_split(s);
        assert(split.x + split.y + split.z == s);
        assert(!split.y.empty() && split.x.size() + split.y.size() <= 2);  // p = 2
        for (std::size_t i = 0; i <= 6; i++) {
            assert(in_trap(pumped(split, i)));
        }
        checked++;
    }
    assert(checked > 100);
    // Y no es regular: a b^i y a b^j, con i ≠ j, se distinguen con c^i.
    for (std::size_t i = 0; i < 12; i++) {
        for (std::size_t j = 0; j < 12; j++) {
            std::string x = "a" + std::string(i, 'b');
            std::string y = "a" + std::string(j, 'b');
            std::string z(i, 'c');
            assert(in_trap(x + z));
            assert(in_trap(y + z) == (i == j));
        }
    }
}

int main() {
    test_lemma_on_machines();
    test_count_attempt();
    test_games();
    test_bad_games();
    test_closure();
    test_trap_language();
    std::printf("test_pumping: ok\n");
}
