// Pruebas de la sesión B: las instancias de PCP de los apuntes, el comprobador y la búsqueda.
#include <cassert>
#include <fstream>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "pcp.h"

static std::vector<Domino> load(const std::string& path) {
    std::ifstream file(path);
    assert(file);
    return read_pcp(file);
}

// Fuerza bruta: prueba todas las secuencias de a lo sumo `bound` fichas, por longitud creciente.
// Devuelve la longitud de la solución más corta, o 0 si no hay.
static int brute_force(const std::vector<Domino>& dominoes, int bound) {
    const int count = static_cast<int>(dominoes.size());
    for (int length = 1; length <= bound; ++length) {
        std::vector<int> sequence(length, 0);
        while (true) {
            if (is_solution(dominoes, sequence)) return length;
            int at = length - 1;
            while (at >= 0 && sequence[at] == count - 1) sequence[at--] = 0;
            if (at < 0) break;
            ++sequence[at];
        }
    }
    return 0;
}

int main() {
    // La instancia de cuatro fichas: la solución más corta es 2 1 3 2 4 y se lee abcaaabc.
    {
        const std::vector<Domino> d = load("instances/sipser.pcp");
        assert(d.size() == 4);
        const std::vector<int> claimed{1, 0, 2, 1, 3};
        assert(is_solution(d, claimed));
        assert(concatenate(d, claimed, true) == "abcaaabc");
        assert(!is_solution(d, {1, 0, 2}));
        assert(!is_solution(d, {}));
        const PcpResult r = solve_pcp(d, 10);
        assert(r.found && r.sequence == claimed);
        assert(brute_force(d, 5) == 5);
        // Con cota 4 no la encuentra, y tampoco puede decir que no existe.
        const PcpResult low = solve_pcp(d, 4);
        assert(!low.found && !low.exhausted);
        // Repetir una solución da otra solución.
        assert(is_solution(d, {1, 0, 2, 1, 3, 1, 0, 2, 1, 3}));
    }
    // La de tres fichas binarias: 2 1 1 3, y se lee 101111110.
    {
        const std::vector<Domino> d = load("instances/hopcroft.pcp");
        const PcpResult r = solve_pcp(d, 10);
        assert(r.found && r.sequence == (std::vector<int>{1, 0, 0, 2}));
        assert(concatenate(d, r.sequence, false) == "101111110");
    }
    // Tres instancias sin solución, en las que la búsqueda se queda sin excesos nuevos.
    for (const std::string name : {"no_start", "longer_top", "cycle"}) {
        const PcpResult r = solve_pcp(load("instances/" + name + ".pcp"), 1000);
        assert(!r.found && r.exhausted);
    }
    assert(solve_pcp(load("instances/no_start.pcp"), 1000).visited == 0);
    assert(solve_pcp(load("instances/cycle.pcp"), 1000).visited == 1);
    // La instancia de solución larga.
    {
        const std::vector<Domino> d = load("instances/long.pcp");
        const PcpResult r = solve_pcp(d, 200);
        assert(r.found && is_solution(d, r.sequence));
        assert(r.sequence.size() == 45 && r.visited == 1542);
        const PcpResult low = solve_pcp(d, static_cast<int>(r.sequence.size()) - 1);
        assert(!low.found && !low.exhausted);
    }
    // La instancia en la que los excesos se multiplican: con un tope de 100 000, la búsqueda
    // abandona. Buscando desde los dos extremos sale una solución de 75 fichas, y es la más corta.
    {
        const std::vector<Domino> d = load("instances/hard_75.pcp");
        const PcpResult r = solve_pcp(d, 400, -1, 100000);
        assert(!r.found && !r.exhausted && r.gave_up);
        const PcpResult low = solve_pcp(d, 45);
        assert(!low.found && !low.exhausted && !low.gave_up && low.visited == 70718);
        const PcpResult both = solve_pcp_two_ends(d, 40);
        assert(both.found && both.sequence.size() == 75 && is_solution(d, both.sequence));
        assert(!solve_pcp_two_ends(d, 37).found);
    }
    // Las instancias del ejercicio 9: (a) 3 2 3 1; (b) sin solución; (c) 66 fichas.
    {
        const std::vector<Domino> a{{"a", "baa"}, {"ab", "aa"}, {"bba", "bb"}};
        assert(solve_pcp(a, 10).sequence == (std::vector<int>{2, 1, 2, 0}));
        const std::vector<Domino> b{{"ab", "aba"}, {"baa", "aa"}, {"aba", "baa"}};
        assert(solve_pcp(b, 1000).exhausted);
        const PcpResult c = solve_pcp(load("instances/four_66.pcp"), 100);
        assert(c.found && c.sequence.size() == 66 && c.visited == 81441);
    }
    // Las dos búsquedas dan la misma longitud en las otras instancias.
    for (const std::string name : {"sipser", "hopcroft", "long"}) {
        const std::vector<Domino> d = load("instances/" + name + ".pcp");
        const PcpResult both = solve_pcp_two_ends(d, 30);
        assert(both.found && is_solution(d, both.sequence));
        assert(both.sequence.size() == solve_pcp(d, 60).sequence.size());
    }
    for (const std::string name : {"no_start", "longer_top", "cycle"}) {
        assert(!solve_pcp_two_ends(load("instances/" + name + ".pcp"), 30).found);
    }
    // El exceso: un paso de la búsqueda.
    {
        Overhang to;
        assert(extend(Overhang{}, Domino{"a", "ab"}, to) && to.side == 'B' && to.excess == "b");
        assert(extend(Overhang{'B', "b"}, Domino{"b", "ca"}, to) && to.side == 'B' && to.excess == "ca");
        assert(!extend(Overhang{'B', "b"}, Domino{"a", "ab"}, to));
        assert(extend(Overhang{'B', "c"}, Domino{"cab", "a"}, to) && to.side == 'T' && to.excess == "b");
        assert(extend(Overhang{'B', "c"}, Domino{"c", ""}, to) && to.excess.empty());
    }
    // PCP modificado: con la primera ficha fija, la de cuatro fichas ya no tiene la solución 2 1 3 2 4.
    {
        const std::vector<Domino> d = load("instances/sipser.pcp");
        const PcpResult r = solve_pcp(d, 30, 0);
        assert(!r.found);
        const PcpResult second = solve_pcp(d, 30, 1);
        assert(second.found && second.sequence.front() == 1);
    }
    // La búsqueda en anchura contra la fuerza bruta, en instancias pequeñas al azar.
    {
        std::mt19937 random(2024);
        int with_solution = 0;
        const int total = 3000;
        for (int test = 0; test < total; ++test) {
            std::vector<Domino> d(2 + random() % 2);
            for (Domino& domino : d) {
                for (std::string* side : {&domino.top, &domino.bottom}) {
                    const int length = 1 + static_cast<int>(random() % 3);
                    for (int i = 0; i < length; ++i) *side += static_cast<char>('a' + random() % 2);
                }
            }
            const int expected = brute_force(d, 7);
            const PcpResult r = solve_pcp(d, 7);
            assert(r.found == (expected != 0));
            const PcpResult both = solve_pcp_two_ends(d, 4);
            assert(both.found == r.found);
            if (r.found) {
                assert(both.sequence.size() == r.sequence.size() && is_solution(d, both.sequence));
                assert(is_solution(d, r.sequence));
                assert(static_cast<int>(r.sequence.size()) == expected);
                ++with_solution;
            }
        }
        std::cout << "test_pcp: ok (" << total << " instancias al azar, " << with_solution << " con solución)\n";
    }
    return 0;
}
