// Comprueba lo que afirman los apuntes. Se compila con sanitizers.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <vector>

#include "fibonacci.h"
#include "knapsack.h"
#include "sequences.h"
#include "weighted_intervals.h"

namespace {

void test_fibonacci() {
    for (int n = 1; n <= 25; n++) {
        long long plain_calls = 0;
        std::vector<long long> times(static_cast<std::size_t>(n) + 1, 0);
        const long long value = fib_plain(n, plain_calls, times);
        assert(plain_calls == 2 * fib_table(n + 1) - 1);  // llamadas = 2 F(n + 1) - 1
        long long memo_calls = 0;
        std::vector<long long> memo(static_cast<std::size_t>(n) + 1, -1);
        assert(fib_memo(n, memo, memo_calls) == value);
        assert(memo_calls == 2 * n - 1);
        assert(fib_table(n) == value);
        assert(fib_two_vars(n) == value);
    }
    assert(fib_two_vars(0) == 0);
    assert(fib_table(0) == 0);
    assert(fib_table(90) == 2880067194370816120LL);
    assert(fib_two_vars(92) == 7540113804746346429LL);  // el último que cabe en long long
}

void test_weighted_examples() {
    const std::vector<WeightedInterval> valuable = {{0, 2, 1}, {1, 6, 10}, {5, 7, 1}};
    assert(weighted_brute(valuable) == 10);
    assert(greedy_earliest_finish(valuable) == 2);
    assert(weighted_best(valuable) == 10);

    const std::vector<WeightedInterval> long_one = {{0, 10, 5}, {0, 3, 4}, {3, 6, 4}, {6, 10, 4}};
    assert(weighted_brute(long_one) == 12);
    assert(greedy_highest_value(long_one) == 5);
    assert(weighted_best(long_one) == 12);

    std::vector<WeightedInterval> trace = {{0, 3, 2}, {1, 5, 4}, {3, 7, 4}, {4, 9, 6}, {7, 10, 2}, {8, 11, 3}};
    assert(greedy_earliest_finish(trace) == 8);
    assert(greedy_highest_value(trace) == 8);
    assert(weighted_brute(trace) == 9);
    assert(weighted_best(trace) == 9);

    sort_by_finish(trace);
    const std::vector<std::size_t> p = compatible_prefix(trace);
    assert((p == std::vector<std::size_t>{0, 0, 1, 1, 3, 3}));
    const std::vector<std::size_t> closed = compatible_prefix_closed(trace);
    assert((closed == std::vector<std::size_t>{0, 0, 0, 1, 2, 3}));
    assert(weighted_table(trace, closed).back() < weighted_table(trace, p).back());

    // El borde: [0, 3) y [3, 5) son compatibles.
    assert(weighted_best({{0, 3, 1}, {3, 5, 1}}) == 2);
}

void test_weighted_random() {
    std::mt19937 rng(7);
    for (int round = 0; round < 3000; round++) {
        const std::size_t n = rng() % 13;
        std::vector<WeightedInterval> classes;
        for (std::size_t i = 0; i < n; i++) {
            const int start = static_cast<int>(rng() % 15);
            const int finish = start + 1 + static_cast<int>(rng() % 6);
            classes.push_back({start, finish, static_cast<long long>(1 + rng() % 9)});
        }
        const long long expected = weighted_brute(classes);
        sort_by_finish(classes);
        const std::vector<std::size_t> p = compatible_prefix(classes);
        assert(p == compatible_prefix_linear(classes));
        for (std::size_t j = 0; j < n; j++) assert(p[j] <= j);  // solo cuenta clases anteriores
        const std::vector<long long> best = weighted_table(classes, p);
        assert(best.back() == expected);

        const std::vector<std::size_t> chosen = weighted_choose(classes, p, best);
        long long total = 0;
        for (std::size_t x = 0; x < chosen.size(); x++) {
            total += classes[chosen[x]].value;
            for (std::size_t y = x + 1; y < chosen.size(); y++) {
                assert(compatible(classes[chosen[x]], classes[chosen[y]]));
            }
        }
        assert(total == expected);
    }
}

void test_knapsack_examples() {
    const std::vector<Item> items = {{2, 3}, {3, 4}, {4, 5}, {5, 8}};
    assert(knapsack_brute(items, 9) == 13);
    assert(knapsack_table(items, 9)[4][9] == 13);
    assert(greedy_by_ratio(items, 9) == 11);
    assert(greedy_by_value(items, 9) == 13);
    assert(knapsack_without_capacity(items, 9) == 12);
    const std::vector<std::size_t> chosen = knapsack_choose(items, knapsack_table(items, 9));
    assert((chosen == std::vector<std::size_t>{2, 3}));

    const std::vector<Item> heavy = {{6, 30}, {5, 20}, {5, 20}};
    assert(knapsack_brute(heavy, 10) == 40);
    assert(greedy_by_ratio(heavy, 10) == 30);
    assert(greedy_by_value(heavy, 10) == 30);
    assert(knapsack_table(heavy, 10)[3][10] == 40);

    // El mismo objeto, con una fila: al revés se toma una vez y al derecho tres.
    const std::vector<Item> single = {{2, 3}};
    assert(knapsack_one_row(single, 6) == 3);
    assert(knapsack_one_row_ascending(single, 6) == 9);

    // Bordes: sin objetos, capacidad cero y un objeto que no cabe.
    assert(knapsack_one_row({}, 5) == 0);
    assert(knapsack_table(items, 0)[4][0] == 0);
    assert(knapsack_one_row(items, 0) == 0);
    assert(knapsack_one_row({{5, 7}}, 4) == 0);
    assert(knapsack_one_row({{5, 7}}, 5) == 7);

    // Un valor que no cabe en int.
    const std::vector<Item> large = {{1, 2000000000}, {1, 2000000000}};
    assert(knapsack_table(large, 2)[2][2] == 4000000000LL);
    assert(knapsack_one_row(large, 2) == 4000000000LL);
}

void test_knapsack_random() {
    std::mt19937 rng(11);
    for (int round = 0; round < 3000; round++) {
        const std::size_t n = rng() % 12;
        const std::size_t capacity = rng() % 25;
        std::vector<Item> items;
        for (std::size_t i = 0; i < n; i++) {
            items.push_back({1 + rng() % 9, static_cast<long long>(rng() % 20)});
        }
        const long long expected = knapsack_brute(items, capacity);
        const std::vector<std::vector<long long>> table = knapsack_table(items, capacity);
        assert(table[n][capacity] == expected);
        assert(knapsack_one_row(items, capacity) == expected);

        std::map<std::pair<std::size_t, std::size_t>, long long> memo;
        assert(knapsack_memo(items, n, capacity, memo) == expected);

        // La reconstrucción: cabe y suma el óptimo.
        std::size_t weight = 0;
        long long value = 0;
        for (std::size_t i : knapsack_choose(items, table)) {
            weight += items[i].weight;
            value += items[i].value;
        }
        assert(weight <= capacity);
        assert(value == expected);

        // De menor a mayor no es un error cualquiera: es la mochila sin límite de copias.
        assert(knapsack_one_row_ascending(items, capacity) == unbounded_knapsack(items, capacity));
        assert(knapsack_one_row_ascending(items, capacity) >= expected);
    }
}

std::string random_string(std::mt19937& rng, std::size_t max_length, const std::string& alphabet) {
    const std::size_t length = rng() % (max_length + 1);
    std::string s;
    for (std::size_t i = 0; i < length; i++) s.push_back(alphabet[rng() % alphabet.size()]);
    return s;
}

void test_lcs() {
    const std::string a = "algoritmo";
    const std::string b = "logaritmo";
    const Table table = lcs_table(a, b);
    assert(table[9][9] == 7);
    assert(lcs_brute(a, b) == 7);
    assert(lcs_walk(a, b, table, true) == "lgritmo");
    assert(lcs_walk(a, b, table, false) == "loritmo");
    assert(longest_common_substring(a, b) == "ritmo");

    std::mt19937 rng(13);
    for (int round = 0; round < 3000; round++) {
        const std::string x = random_string(rng, 11, "abc");
        const std::string y = random_string(rng, 11, "abc");
        const Table t = lcs_table(x, y);
        const int length = t[x.size()][y.size()];
        assert(static_cast<std::size_t>(length) == lcs_brute(x, y));
        for (bool prefer_up : {true, false}) {
            const std::string walked = lcs_walk(x, y, t, prefer_up);
            assert(static_cast<int>(walked.size()) == length);
            assert(is_subsequence(walked, x));
            assert(is_subsequence(walked, y));
        }
        if (!x.empty() && !y.empty()) {
            const std::string substring = longest_common_substring(x, y);
            assert(x.find(substring) != std::string::npos);
            assert(y.find(substring) != std::string::npos);
            assert(static_cast<int>(substring.size()) <= length);
        }
    }
}

void test_edit_examples() {
    const Table table = edit_table("casa", "cosas");
    assert(table[4][5] == 2);
    assert((table[2] == std::vector<int>{2, 1, 1, 2, 2, 3}));
    assert((table[4] == std::vector<int>{4, 3, 3, 2, 1, 2}));
    assert(table.size() == 5);
    assert(table[0].size() == 6);
    for (std::size_t i = 0; i <= 4; i++) assert(table[i][0] == static_cast<int>(i));
    for (std::size_t j = 0; j <= 5; j++) assert(table[0][j] == static_cast<int>(j));
    const std::vector<EditStep> steps = edit_walk("casa", "cosas", table);
    assert(edit_cost(steps) == 2);
    assert(apply_steps("casa", "cosas", steps) == "cosas");
    assert(edit_table("", "").back().back() == 0);
    assert(edit_table("abc", "").back().back() == 3);
    assert(edit_table("", "abc").back().back() == 3);
    assert(edit_table("algoritmo", "logaritmo").back().back() == 3);
    assert(edit_table("ab", "ba").back().back() == 2);  // intercambiar dos vecinas cuesta 2
}

void test_edit_random() {
    std::mt19937 rng(17);
    for (int round = 0; round < 3000; round++) {
        const std::string x = random_string(rng, 30, "abcd");
        const std::string y = random_string(rng, 30, "abcd");
        const Table t = edit_table(x, y);
        const int d = t[x.size()][y.size()];
        assert(edit_two_rows(x, y) == d);
        const std::vector<EditStep> steps = edit_walk(x, y, t);
        assert(edit_cost(steps) == d);
        assert(apply_steps(x, y, steps) == y);
        assert(edit_table(y, x).back().back() == d);  // convertir en un sentido o en el otro cuesta igual
        for (std::size_t i = 1; i <= x.size(); i++) {
            for (std::size_t j = 1; j <= y.size(); j++) {
                if (x[i - 1] == y[j - 1]) assert(t[i][j] == t[i - 1][j - 1]);  // ejercicio 8
            }
        }
    }
    // Contra el árbitro que aplica la definición de una operación, sin recurrencia.
    for (int round = 0; round < 400; round++) {
        const std::string x = random_string(rng, 4, "ab");
        const std::string y = random_string(rng, 4, "ab");
        const std::size_t limit = 7;
        assert(edit_bfs(x, y, "ab", limit, true) == edit_table(x, y).back().back());
        const int lcs = lcs_table(x, y).back().back();
        // Solo con borrar e insertar: n + m - 2 LCS.
        assert(edit_bfs(x, y, "ab", limit, false) == static_cast<int>(x.size() + y.size()) - 2 * lcs);
    }
}

}  // namespace

int main() {
    test_fibonacci();
    test_weighted_examples();
    test_weighted_random();
    test_knapsack_examples();
    test_knapsack_random();
    test_lcs();
    test_edit_examples();
    test_edit_random();
    std::cout << "Todas las pruebas de la semana 7 pasaron.\n";
}