// Pruebas de las historias de cómputo: las de los apuntes y el comprobador local.
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

#include "tm.h"

// Todas las cadenas sobre {0, 1} de longitud a lo sumo n, de la más corta a la más larga.
static std::vector<std::string> binary_strings(int n) {
    std::vector<std::string> all{""};
    for (std::size_t i = 0; all[i].size() < static_cast<std::size_t>(n); ++i) {
        all.push_back(all[i] + "0");
        all.push_back(all[i] + "1");
    }
    return all;
}

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

int main() {
    const Tm m = load_tm("machines/zeros_ones.tm");

    // La historia de 01 que muestran los apuntes: seis configuraciones.
    {
        const Run run = run_tm(m, "01", 1000);
        assert(run.accepted && run.steps == 5 && run.configurations.size() == 6);
        const std::string expected = "q0 0 1 # X q1 1 # q2 X Y # X q0 Y # X Y q3 _ # X Y _ q_accept _";
        assert(join(history_tokens(run.configurations)) == expected);
        assert(check_history(m, "01", split(expected)).empty());
        // No es la historia de otra entrada.
        assert(!check_history(m, "0011", split(expected)).empty());
        // Sin la última configuración no termina en aceptación.
        assert(!check_history(m, "01", split("q0 0 1 # X q1 1 # q2 X Y # X q0 Y # X Y q3 _")).empty());
        // Saltarse una configuración se nota en una ventana.
        assert(!check_history(m, "01", split("q0 0 1 # X q1 1 # X q0 Y # X Y q3 _ # X Y _ q_accept _")).empty());
        // Los blancos de más al final de una configuración no molestan.
        assert(check_history(m, "01", split("q0 0 1 _ # X q1 1 # q2 X Y _ _ # X q0 Y # X Y q3 _ # X Y _ q_accept _")).empty());
    }
    // 0011: catorce configuraciones, y la forma con las pares al revés.
    {
        const Run run = run_tm(m, "0011", 1000);
        assert(run.accepted && run.configurations.size() == 14);
        const Tokens alternate = history_tokens(run.configurations, true);
        const std::string start = "q0 0 0 1 1 # 1 1 0 q1 X # X 0 q1 1 1 #";
        assert(join(alternate).compare(0, start.size(), start) == 0);
    }
    // Con cada cadena corta: acepta exactamente las de la forma 0^n 1^n, y cuando acepta, su
    // historia pasa el comprobador. Además, cambiar un solo símbolo de la historia por cualquier
    // otro la estropea: no hay dos historias de aceptación que difieran en un símbolo.
    int histories = 0;
    long mutations = 0;
    for (const std::string& w : binary_strings(8)) {
        const Run run = run_tm(m, w, 100000);
        assert(run.halted);
        assert(run.accepted == in_zeros_ones(w));
        if (!run.accepted) continue;
        ++histories;
        const Tokens history = history_tokens(run.configurations);
        assert(check_history(m, w, history).empty());
        std::vector<std::string> options{"#"};
        for (const std::string& q : m.states) options.push_back(q);
        for (char a : m.tape) options.push_back(std::string(1, a));
        for (std::size_t i = 0; i < history.size(); ++i) {
            for (const std::string& other : options) {
                if (other == history[i]) continue;
                Tokens changed = history;
                changed[i] = other;
                assert(!check_history(m, w, changed).empty());
                ++mutations;
            }
        }
    }
    assert(histories == 5);

    // La máquina de las cadenas que empiezan con 01: un movimiento a la izquierda.
    {
        const Tm starts = load_tm("machines/starts_01.tm");
        const Run run = run_tm(starts, "01", 100);
        assert(run.accepted);
        assert(join(history_tokens(run.configurations)) == "q0 0 1 # 0 q1 1 # q2 0 1 # 0 q_accept 1");
        assert(check_history(starts, "01", history_tokens(run.configurations)).empty());
        assert(!check_history(starts, "01", split("q0 0 1 # 0 q1 1 # q2 0 0 # 0 q_accept 0")).empty());
        assert(!run_tm(starts, "00", 100).accepted);
    }
    // La que no se detiene: después de 1000 pasos sigue corriendo.
    {
        const Tm loop = load_tm("machines/loop_on_0.tm");
        assert(!run_tm(loop, "00", 1000).halted);
        assert(run_tm(loop, "1", 1000).accepted);
        const Run rejected = run_tm(loop, "01", 1000);
        assert(rejected.halted && !rejected.accepted);
    }
    // L en la primera celda deja el cabezal donde está, y el comprobador lo sabe.
    {
        Tm left = load_tm("machines/starts_01.tm");
        left.delta[{"q0", '1'}] = Transition{"q2", '0', 'L'};
        const Run run = run_tm(left, "1", 100);
        assert(run.accepted);
        assert(join(history_tokens(run.configurations)) == "q0 1 # q2 0 # 0 q_accept _");
        assert(check_history(left, "1", history_tokens(run.configurations)).empty());
    }
    // Una descripción no determinista se rechaza al leerla.
    {
        bool failed = false;
        try {
            load_tm("errors/two_moves.tm");
        } catch (const std::runtime_error&) {
            failed = true;
        }
        assert(failed);
    }
    std::cout << "test_history: ok (" << histories << " historias, " << mutations << " cambios de un símbolo, todos detectados)\n";
    return 0;
}
