// Pruebas de la sesión B: el simulador que recibe la máquina como dato, lo que dice y lo que
// no dice un límite de pasos, y las dos máquinas que se alternan.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <sstream>
#include <string>
#include <vector>

#include "tm.h"

static std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
    std::vector<std::string> result = {""};
    std::size_t begin = 0;
    for (std::size_t len = 1; len <= max_len; len++) {
        std::size_t end = result.size();
        for (std::size_t i = begin; i < end; i++) {
            for (char a : alphabet) {
                result.push_back(result[i] + a);
            }
        }
        begin = end;
    }
    return result;
}

static const std::vector<char> BINARY = {'0', '1'};

static bool is_0n1n(const std::string& w) {
    std::size_t n = w.size() / 2;
    return w.size() % 2 == 0 && w == std::string(n, '0') + std::string(n, '1');
}

static bool has_one(const std::string& w) {
    return w.find('1') != std::string::npos;
}

// Un decididor: se detiene con todas las entradas.
static void test_decider() {
    Tm m = load_tm("machines/zeros_ones.tm");
    Outcome traced = simulate(m, "0011", 1000);
    assert(traced.status == Status::Accepted && traced.steps == 13);
    for (const std::string& w : all_strings(BINARY, 10)) {
        Outcome result = simulate(m, w, 1000);
        assert(result.status != Status::Running);
        assert((result.status == Status::Accepted) == is_0n1n(w));
    }
    // El mismo cómputo cortado antes: "no se detuvo en 5 pasos" no dice que no se detenga.
    assert(simulate(m, "0011", 5).status == Status::Running);
    assert(simulate(m, "0011", 12).status == Status::Running);
    assert(simulate(m, "0011", 13).status == Status::Accepted);

    Tm scan = load_tm("machines/has_one.tm");
    for (const std::string& w : all_strings(BINARY, 10)) {
        Outcome result = simulate(scan, w, 1000);
        assert(result.status != Status::Running && result.steps <= static_cast<long>(w.size()) + 1);
        assert((result.status == Status::Accepted) == has_one(w));
    }
    assert(simulate(scan, "000", 1000).steps == 4);
}

// Un reconocedor que no decide: mismo lenguaje que has_one.tm, pero no se detiene sin un 1.
static void test_recognizer() {
    Tm m = load_tm("machines/search_one.tm");
    for (const std::string& w : all_strings(BINARY, 10)) {
        Outcome result = simulate(m, w, 20000);
        if (has_one(w)) {
            assert(result.status == Status::Accepted && result.steps <= static_cast<long>(w.size()));
        } else {
            assert(result.status == Status::Running && result.steps == 20000);
        }
    }
    assert(simulate(m, "0001", 1000).steps == 4);
    // Con 000 nunca se detiene, y aquí se ve por qué: después de t pasos está en el estado
    // scan, con el cabezal en la celda t, y de ahí en adelante solo lee blancos.
    Config c = initial_config(m, "000");
    for (std::size_t t = 1; t <= 5000; t++) {
        step(m, c);
        assert(c.state == "scan" && c.head == t);
        assert(t < 3 || c.tape[c.head] == BLANK);
    }
    for (long limit : {10L, 1000L, 100000L, 1000000L}) {
        assert(simulate(m, "000", limit).status == Status::Running);
    }
}

// La máquina es un dato: de la cadena ⟨M⟩ se recupera una máquina que hace lo mismo.
static void test_encoding() {
    for (const char* path : {"machines/zeros_ones.tm", "machines/has_one.tm", "machines/search_one.tm",
                             "machines/search_end.tm"}) {
        Tm m = load_tm(path);
        std::string description = encode(m);
        std::istringstream in(description);
        Tm again = read_tm(in);
        assert(encode(again) == description);
        for (const std::string& w : all_strings(BINARY, 8)) {
            Outcome a = simulate(m, w, 500);
            Outcome b = simulate(again, w, 500);
            assert(a.status == b.status && a.steps == b.steps);
        }
    }
    assert(encode(load_tm("machines/zeros_ones.tm")).size() == 296);
}

// Dos reconocedores, uno del lenguaje y otro del complemento, alternados: un decididor.
static void test_alternation() {
    Tm yes = load_tm("machines/search_one.tm");
    Tm no = load_tm("machines/search_end.tm");
    for (const std::string& w : all_strings(BINARY, 10)) {
        // Ninguna de las dos decide: cada una se queda corriendo con las cadenas de la otra.
        assert((simulate(yes, w, 200).status == Status::Accepted) == has_one(w));
        assert((simulate(no, w, 200).status == Status::Accepted) == !has_one(w));
        assert(simulate(has_one(w) ? no : yes, w, 200).status == Status::Running);
        // Alternadas, siempre termina, y en pocas rondas.
        Alternation result = alternate(yes, no, w, 10000);
        assert(result.winner == (has_one(w) ? 1 : 2));
        assert(result.rounds <= static_cast<long>(w.size()) + 1);
    }
    assert(alternate(yes, no, "0001", 10000).rounds == 4);
    assert(alternate(yes, no, "000", 10000).rounds == 4);
    // Si las dos máquinas no cubren todas las cadenas, la alternancia no termina.
    assert(alternate(yes, yes, "000", 10000).winner == 0);
}

int main() {
    test_decider();
    test_recognizer();
    test_encoding();
    test_alternation();
    std::printf("test_tm: ok (4 máquinas, 2047 cadenas cada una)\n");
}
