// Pruebas de la sesión B sobre máquinas de varias cintas: la máquina de dos cintas decide
// { 0^n 1^n } en tiempo lineal, y la simulación con una sola cinta mantiene, paso a paso, la
// misma configuración que la máquina simulada, dentro de la cota cuadrática de los apuntes.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <random>
#include <string>
#include <vector>

#include "multitape.h"
#include "tm.h"

static bool is_zeros_ones(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');
}

// Ejecuta M y la simulación S a la vez y compara después de cada paso de M.
// Devuelve los pasos de S. Comprueba las cotas de los apuntes:
//   - la cinta de S ocupa a lo sumo n + 2k + 1 + k·t celdas después de t pasos de M;
//   - simular un paso cuesta a lo sumo (2k + 6)·L pasos de S, con L celdas en uso al terminar;
//   - preparar la cinta cuesta a lo sumo 2(n + 2k + 1) pasos.
static long long check_simulation(const MultiTm& m, const std::string& w, long long limit) {
    const long long k = static_cast<long long>(m.tapes);
    const long long n = static_cast<long long>(w.size());
    MultiConfig c = initial_config(m, w);
    Simulation s = start_simulation(m, w);
    assert(s.tape.head == 0);
    assert(same_config(decode(m, s), c));
    assert(s.setup <= 2 * (n + 2 * k + 1));
    assert(s.length == (n == 0 ? 1 : n) + 2 * k);
    long long t = 0;
    while (!halted(m, c) && t < limit) {
        long long before = s.tape.steps;
        step(m, c);
        simulate_step(m, s);
        t++;
        assert(s.rounds == t);
        assert(s.tape.head == 0);
        assert(same_config(decode(m, s), c));
        assert(s.length <= n + 2 * k + 1 + k * t);
        assert(s.tape.steps - before <= (2 * k + 6) * s.length);
    }
    assert(s.tape.steps <= 2 * (n + 2 * k + 1) + t * (2 * k + 6) * (n + 2 * k + 1 + k * t));
    return s.tape.steps;
}

static void test_two_tapes() {
    MultiTm m = two_tape_zeros_ones();
    std::size_t strings = 0;
    for (const std::string& w : all_strings(m.alphabet, 11)) {
        MultiRun r = run_multi(m, w, 1000);
        assert(r.outcome != Outcome::Limit);
        assert((r.outcome == Outcome::Accept) == is_zeros_ones(w));
        assert(r.steps <= static_cast<long long>(w.size()) + 3);  // tiempo lineal
        SimulationRun sim = run_simulation(m, w, 1000);
        assert(sim.outcome == r.outcome && sim.rounds == r.steps);
        assert(check_simulation(m, w, 1000) == sim.steps);
        strings++;
    }
    std::printf("  dos cintas: %zu cadenas, la simulación coincide paso a paso\n", strings);
}

// Los números de la tabla de los apuntes.
static void test_table() {
    MultiTm m = two_tape_zeros_ones();
    Tm one = load_tm("machines/zeros_ones.tm");
    const std::vector<std::vector<long long>> rows = {
        {5, 61, 13, 992},        {10, 221, 23, 3012},       {20, 841, 43, 10352},     {40, 3281, 83, 38232},
        {80, 12961, 163, 146792}, {160, 51521, 323, 575112}, {320, 205441, 643, 2276552}};
    for (const std::vector<long long>& row : rows) {
        std::string w = std::string(row[0], '0') + std::string(row[0], '1');
        assert(run(one, w, 10000000).steps == row[1]);
        assert(run_multi(m, w, 10000000).steps == row[2]);
        assert(row[2] == 2 * row[0] + 3);
        assert(run_simulation(m, w, 10000000).steps == row[3]);
    }
    // La simulación del ejemplo corto.
    SimulationRun sim = run_simulation(m, "01", 100);
    assert(sim.outcome == Outcome::Accept && sim.rounds == 5 && sim.steps == 168);
    Simulation s = start_simulation(m, "01");
    assert(to_string(s.tape) == "#[0]1#[_]#" && s.setup == 12);
    simulate_step(m, s);
    assert(to_string(s.tape) == "#[0]1#$[_]#" && s.tape.steps == 36);
    simulate_step(m, s);
    assert(to_string(s.tape) == "#0[1]#$0[_]#" && s.tape.steps == 64);
    Simulation empty = start_simulation(m, "");
    assert(to_string(empty.tape) == "#[_]#[_]#" && empty.setup == 10);
}

// Máquinas de 1, 2 y 3 cintas con transiciones al azar (semilla fija): la simulación tiene que
// coincidir con cualquier máquina, no solo con la del capítulo. Ejercita los movimientos L en
// la primera celda, los S y los corrimientos en cada cinta.
static void test_random_machines() {
    std::mt19937 rng(7007);
    const std::string gamma = "01_";
    long long machines = 0;
    for (std::size_t k = 1; k <= 3; k++) {
        for (int round = 0; round < 60; round++) {
            MultiTm m;
            m.tapes = k;
            m.states = {"p0", "p1", "p2", "q_accept", "q_reject"};
            m.alphabet = {'0', '1'};
            m.tape = {'0', '1', BLANK};
            m.start = "p0";
            m.accept = "q_accept";
            m.reject = "q_reject";
            std::size_t combos = 1;
            for (std::size_t i = 0; i < k; i++) {
                combos *= gamma.size();
            }
            for (std::size_t q = 0; q < 3; q++) {
                for (std::size_t combo = 0; combo < combos; combo++) {
                    std::string read;
                    std::size_t rest = combo;
                    for (std::size_t i = 0; i < k; i++) {
                        read += gamma[rest % gamma.size()];
                        rest /= gamma.size();
                    }
                    unsigned kind = rng() % 20;
                    if (kind == 0) {
                        continue;  // sin transición: va a q_reject
                    }
                    MultiAction action;
                    action.state = (kind == 1) ? "q_accept" : m.states[rng() % 3];
                    for (std::size_t i = 0; i < k; i++) {
                        action.write += gamma[rng() % gamma.size()];
                        action.move += "LRRS"[rng() % 4];
                    }
                    m.delta[{m.states[q], read}] = action;
                }
            }
            for (const std::string& w : all_strings(m.alphabet, 4)) {
                check_simulation(m, w, 60);
            }
            machines++;
        }
    }
    std::printf("  %lld máquinas al azar de 1, 2 y 3 cintas: la simulación coincide paso a paso\n", machines);
}

int main() {
    std::printf("test_multitape:\n");
    test_two_tapes();
    test_table();
    test_random_machines();
    std::printf("test_multitape: ok\n");
}
