// Pruebas de la reducción de A_TM a PCP en casos pequeños: las fichas tienen solución
// exactamente cuando la máquina acepta, y la solución lleva escrita la historia de cómputo.
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

#include "tm_pcp.h"

// ¿Intenta la máquina moverse a la izquierda desde la primera celda en los primeros pasos?
// La construcción supone que no.
static bool moves_left_at_first_cell(const Tm& m, const Run& run) {
    for (const Configuration& c : run.configurations) {
        if (!c.left.empty() || halted(m, c)) continue;
        const auto it = m.delta.find({c.state, c.right.empty() ? '_' : c.right[0]});
        if (it != m.delta.end() && it->second.move == 'L') return true;
    }
    return false;
}

// Quita los blancos del final de cada configuración, para comparar historias.
static Tokens without_trailing_blanks(const Tokens& history) {
    Tokens result;
    auto trim = [&result]() {
        while (!result.empty() && result.back() == "_") result.pop_back();
    };
    for (const std::string& token : history) {
        if (token == "#") trim();
        result.push_back(token);
    }
    trim();
    return result;
}

int main() {
    // El ejemplo de los apuntes: 18 fichas, solución de 15, y la cadena que se lee.
    {
        const Tm m = load_tm("machines/starts_01.tm");
        const TmDominoes instance = tm_to_mpcp(m, "01");
        assert(instance.dominoes.size() == 18);
        assert(instance.dominoes[0].top == "#" && instance.dominoes[0].bottom == "#A01#");
        const PcpResult r = solve_pcp(instance.dominoes, 100, 0);
        assert(r.found && r.sequence.size() == 15);
        assert(r.sequence == (std::vector<int>{0, 1, 7, 9, 3, 9, 2, 7, 9, 6, 15, 9, 11, 9, 17}));
        assert(concatenate(instance.dominoes, r.sequence, true) == "#A01#0B1#C01#0D1#0D#D##");
        // Sin la condición de la primera ficha: 20 fichas y una solución de 16.
        const std::vector<Domino> pcp = mpcp_to_pcp(instance.dominoes);
        assert(pcp.size() == 20);
        const PcpResult free = solve_pcp(pcp, 100);
        assert(free.found && free.sequence.size() == 16 && free.sequence.front() == 0 && free.sequence.back() == 19);
        // Con la entrada 00 la máquina rechaza y la búsqueda se agota: no hay solución.
        const PcpResult none = solve_pcp(tm_to_mpcp(m, "00").dominoes, 100, 0);
        assert(!none.found && none.exhausted);
    }

    struct Case {
        std::string machine;
        std::vector<std::string> inputs;
    };
    const std::vector<Case> cases{
        {"machines/starts_01.tm", {"", "0", "1", "00", "01", "10", "11", "010", "011", "0100"}},
        {"machines/zeros_ones.tm", {"", "0", "1", "01", "10", "001", "011"}},
        {"machines/loop_on_0.tm", {"", "0", "1", "00", "01", "10", "000"}},
        {"machines/empty_ok.tm", {"", "0", "1"}},
    };
    const int bound = 40;
    int accepted = 0;
    int total = 0;
    for (const Case& c : cases) {
        const Tm m = load_tm(c.machine);
        for (const std::string& w : c.inputs) {
            const Run run = run_tm(m, w, 2000);
            assert(!moves_left_at_first_cell(m, run));
            const TmDominoes instance = tm_to_mpcp(m, w);
            const PcpResult fixed = solve_pcp(instance.dominoes, bound, 0);
            const PcpResult free = solve_pcp(mpcp_to_pcp(instance.dominoes), bound);
            // Acepta si y solo si hay solución (hasta la cota, cuando no acepta).
            assert(fixed.found == run.accepted);
            assert(free.found == run.accepted);
            ++total;
            if (!run.accepted) continue;
            ++accepted;
            assert(is_solution(instance.dominoes, fixed.sequence));
            assert(free.sequence.size() == fixed.sequence.size() + 1);
            // La cadena de la solución empieza con # y la historia de aceptación de M con w.
            Tokens decoded = decode_match(instance, concatenate(instance.dominoes, fixed.sequence, true));
            assert(decoded.front() == "#");
            decoded.erase(decoded.begin());
            std::size_t end = 0;
            while (decoded[end] != m.accept) ++end;
            while (decoded[end] != "#") ++end;
            const Tokens history(decoded.begin(), decoded.begin() + static_cast<long>(end));
            assert(check_history(m, w, history).empty());
            assert(without_trailing_blanks(history) == without_trailing_blanks(history_tokens(run.configurations)));
        }
    }
    std::cout << "test_tm_pcp: ok (" << total << " pares de máquina y entrada, " << accepted
              << " con aceptación; sin solución hasta " << bound << " fichas en los demás)\n";
    return 0;
}
