// Las pruebas de lo que afirman los apuntes de la semana 12.
#include <bit>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <random>
#include <set>
#include <vector>

#include "baseball.h"
#include "disjoint_paths.h"
#include "lower_bounds.h"
#include "matching.h"
#include "projects.h"

namespace {

using Random = std::mt19937;

int below(Random& random, int limit) { return static_cast<int>(random() % static_cast<std::uint32_t>(limit)); }

Options random_options(Random& random, int left, int right, int max_degree) {
    Options options(static_cast<std::size_t>(left));
    for (auto& list : options) {
        int degree = below(random, max_degree + 1);
        for (int k = 0; k < degree; k++) {
            int j = below(random, right);
            if (std::find(list.begin(), list.end(), j) == list.end()) list.push_back(j);
        }
    }
    return options;
}

void test_matching_examples() {
    // El ejemplo de 3 por 3, cuyo tercer camino usa aristas inversas.
    Options three = {{0, 1}, {0}, {1, 2}};
    MatchingNetwork net = matching_network(three, 3);
    net.flow.keep_paths();
    assert(net.flow.edmonds_karp(net.source, net.sink) == 3);
    assert(net.flow.paths().size() == 3);
    assert(net.flow.paths()[2].size() == 8);
    assert(is_matching(three, 3, read_matching(net, three)));

    // Los dos greedy fallan donde dicen los apuntes.
    Options first = {{0, 1}, {0}};
    assert(assigned_count(first_fit(first, {1, 1})) == 1);
    assert(assigned_count(fewest_options_first(first, {1, 1})) == 2);
    assert(assigned_count(max_matching(first, 2)) == 2);
    Options fewest = {{0, 1}, {2, 0}, {2}};
    assert(assigned_count(fewest_options_first(fewest, {1, 1, 1})) == 2);
    assert(assigned_count(max_matching(fewest, 3)) == 3);

    // Sin capacidad en s -> E, el valor deja de ser el tamaño de un matching: falla una sola dirección.
    Options wide = {{0, 1}, {}};
    MatchingNetwork no_limit = matching_network(wide, 2, 1000);
    assert(no_limit.flow.edmonds_karp(no_limit.source, no_limit.sink) == 2);
    assert(assigned_count(max_matching(wide, 2)) == 1);

    // En un ciclo de 4 también existe un flujo de valor 2 con un medio en cada arista. El programa, que
    // solo empuja enteros, devuelve un matching de verdad.
    Options cycle = {{0, 1}, {0, 1}};
    assert(assigned_count(max_matching(cycle, 2)) == 2);
}

void test_matching_random() {
    Random random(1212);
    for (int round = 0; round < 3000; round++) {
        int left = 1 + below(random, 7);
        int right = 1 + below(random, 7);
        Options options = random_options(random, left, right, 3);
        std::vector<int> quota(static_cast<std::size_t>(right), 1);
        std::vector<int> copy = quota;
        int expected = brute_assignment(options, copy);

        MatchingNetwork net = matching_network(options, right);
        long long value = net.flow.edmonds_karp(net.source, net.sink);
        std::vector<int> partner = read_matching(net, options);
        assert(value == expected);
        assert(assigned_count(partner) == expected);
        assert(is_matching(options, right, partner));
        // A lo sumo min(L, R) aumentos.
        assert(net.flow.augmentations() <= std::min(left, right));

        MatchingNetwork other = matching_network(options, right);
        assert(other.flow.ford_fulkerson(other.source, other.sink) == expected);
        assert(assigned_count(first_fit(options, quota)) <= expected);
        assert(assigned_count(fewest_options_first(options, quota)) <= expected);
    }
}

void test_quota_example() {
    const Options options = {{0}, {0}, {2, 1}, {0, 2}, {2}, {0}};
    std::vector<int> quota = {2, 1, 2};
    assert(assigned_count(first_fit(options, quota)) == 4);
    assert(assigned_count(fewest_options_first(options, quota)) == 4);
    assert(brute_assignment(options, quota) == 5);
    // La condición de Hall con cupos: E0, E1 y E5 solo pueden ir a S0, que tiene cupo 2.
}

// Un flujo entero al azar se arma sumando caminos y ciclos, sin ninguna red detrás.
void test_decomposition() {
    std::vector<Arc> with_cycle = {{0, 1}, {1, 2}, {2, 5}, {0, 3}, {3, 5}, {2, 4}, {4, 3}, {3, 2}};
    Decomposition result = decompose_flow(6, with_cycle, 0, 5);
    assert(result.paths.size() == 2);
    assert(result.cycles.size() == 1);

    // Solo un ciclo: valor 0. Un ciclo que pasa por s y por t no se confunde con un camino.
    Decomposition only_cycle = decompose_flow(3, {{0, 1}, {1, 2}, {2, 0}}, 0, 1);
    assert(only_cycle.paths.empty());
    assert(only_cycle.cycles.size() == 1);

    Random random(99);
    for (int round = 0; round < 2000; round++) {
        int nodes = 3 + below(random, 6);
        int s = 0;
        int t = nodes - 1;
        std::vector<Arc> arcs;
        int paths = below(random, 4);
        for (int p = 0; p < paths; p++) {
            int v = s;
            for (int step = below(random, 4); step > 0; step--) {
                int w = below(random, nodes);
                if (w != v) {
                    arcs.push_back({v, w});
                    v = w;
                }
            }
            if (v != t) arcs.push_back({v, t});
        }
        for (int c = below(random, 3); c > 0; c--) {
            int a = below(random, nodes);
            int b = below(random, nodes);
            int d = below(random, nodes);
            if (a != b && b != d && d != a) {
                arcs.push_back({a, b});
                arcs.push_back({b, d});
                arcs.push_back({d, a});
            }
        }
        Decomposition parts = decompose_flow(nodes, arcs, s, t);
        std::size_t used = 0;
        int value = 0;
        for (const Arc& arc : arcs) value += (arc.from == s) - (arc.to == s);
        assert(static_cast<int>(parts.paths.size()) == value);
        for (const auto& path : parts.paths) {
            assert(path.front() == s && path.back() == t);
            assert(std::set<int>(path.begin(), path.end()).size() == path.size());  // camino simple
            used += path.size() - 1;
        }
        for (const auto& cycle : parts.cycles) {
            assert(cycle.front() == cycle.back());
            used += cycle.size() - 1;
        }
        assert(used == arcs.size());  // ninguna unidad se pierde: todo está en un camino o en un ciclo
    }
}

std::vector<Arc> random_arcs(Random& random, int nodes, int tries) {
    std::vector<Arc> arcs;
    std::set<std::pair<int, int>> seen;
    for (int k = 0; k < tries; k++) {
        int a = below(random, nodes);
        int b = below(random, nodes);
        if (a != b && seen.insert({a, b}).second) arcs.push_back({a, b});
    }
    return arcs;
}

int brute_edge_cut(int nodes, const std::vector<Arc>& arcs, int s, int t) {
    int best = static_cast<int>(arcs.size());
    std::vector<bool> no_nodes(static_cast<std::size_t>(nodes), false);
    for (unsigned mask = 0; mask < (1u << arcs.size()); mask++) {
        std::vector<bool> removed(arcs.size());
        for (std::size_t k = 0; k < arcs.size(); k++) removed[k] = (mask >> k) & 1u;
        if (!connected_without(nodes, arcs, s, t, no_nodes, removed)) best = std::min(best, std::popcount(mask));
    }
    return best;
}

int brute_vertex_separator(int nodes, const std::vector<Arc>& arcs, int s, int t) {
    int best = nodes;
    std::vector<bool> no_arcs(arcs.size(), false);
    for (unsigned mask = 0; mask < (1u << nodes); mask++) {
        if ((mask >> s & 1u) || (mask >> t & 1u)) continue;
        std::vector<bool> removed(static_cast<std::size_t>(nodes));
        for (int v = 0; v < nodes; v++) removed[static_cast<std::size_t>(v)] = (mask >> v) & 1u;
        if (!connected_without(nodes, arcs, s, t, removed, no_arcs)) best = std::min(best, std::popcount(mask));
    }
    return best;
}

// Menger: los caminos son disjuntos de verdad y son tantos como el mínimo que los separa, por fuerza bruta.
void test_menger() {
    Random random(2024);
    for (int round = 0; round < 1500; round++) {
        int nodes = 2 + below(random, 5);
        int s = 0;
        int t = nodes - 1;
        std::vector<Arc> arcs = random_arcs(random, nodes, 1 + below(random, 10));

        Decomposition by_edges = edge_disjoint_paths(nodes, arcs, s, t);
        std::set<std::pair<int, int>> used;
        for (const auto& path : by_edges.paths) {
            for (std::size_t k = 0; k + 1 < path.size(); k++) assert(used.insert({path[k], path[k + 1]}).second);
        }
        int cut = brute_edge_cut(nodes, arcs, s, t);
        assert(static_cast<int>(by_edges.paths.size()) == cut);
        assert(static_cast<int>(minimum_edge_cut(nodes, arcs, s, t).size()) == cut);

        Decomposition by_nodes = vertex_disjoint_paths(nodes, arcs, s, t);
        std::set<int> inner;
        int direct = 0;
        for (const auto& path : by_nodes.paths) {
            direct += path.size() == 2;
            for (std::size_t k = 1; k + 1 < path.size(); k++) assert(inner.insert(path[k]).second);
        }
        // Sin la arista directa, Menger con nodos. Con ella, son uno más que sin ella.
        std::vector<Arc> without;
        for (const Arc& arc : arcs) {
            if (!(arc.from == s && arc.to == t)) without.push_back(arc);
        }
        bool adjacent = without.size() != arcs.size();
        assert(direct == (adjacent ? 1 : 0));
        int separator = brute_vertex_separator(nodes, without, s, t);
        assert(static_cast<int>(by_nodes.paths.size()) == separator + (adjacent ? 1 : 0));
        assert(static_cast<int>(minimum_vertex_separator(nodes, without, s, t).size()) == separator);
    }
}

// No dirigido: el mismo mínimo con dos arcos por arista, y aristas de verdad sin repetir.
void test_undirected() {
    Random random(77);
    for (int round = 0; round < 1500; round++) {
        int nodes = 2 + below(random, 6);
        int s = 0;
        int t = nodes - 1;
        std::vector<Arc> edges;
        std::set<std::pair<int, int>> seen;
        for (int k = 0, tries = 1 + below(random, 9); k < tries; k++) {
            int a = below(random, nodes);
            int b = below(random, nodes);
            if (a != b && !seen.count({a, b}) && !seen.count({b, a})) {
                seen.insert({a, b});
                edges.push_back({a, b});
            }
        }
        Decomposition result = undirected_edge_disjoint_paths(nodes, edges, s, t);
        std::set<std::pair<int, int>> used;
        for (const auto& path : result.paths) {
            for (std::size_t k = 0; k + 1 < path.size(); k++) {
                int a = std::min(path[k], path[k + 1]);
                int b = std::max(path[k], path[k + 1]);
                assert(used.insert({a, b}).second);
            }
        }
        std::vector<Arc> both;
        for (const Arc& e : edges) {
            both.push_back(e);
            both.push_back({e.to, e.from});
        }
        // Quitar una arista no dirigida quita sus dos arcos, pero para s y t basta el arco que cruza.
        assert(static_cast<int>(result.paths.size()) == static_cast<int>(minimum_edge_cut(nodes, both, s, t).size()));
    }
    // La red de los apuntes usa una arista en las dos direcciones.
    std::vector<Arc> edges = {{0, 4}, {6, 5}, {0, 2}, {2, 5}, {3, 6}, {1, 4}, {3, 1}, {0, 6}, {5, 4}};
    Decomposition example = undirected_edge_disjoint_paths(7, edges, 0, 6);
    assert(example.cancelled == 1);
    assert(example.paths.size() == 3);
}

void test_baseball() {
    Championship league{{"Lima", "Cusco", "Ica", "Piura", "Callao"},
                        {27, 26, 26, 25, 20},
                        {{0, 2, 2, 0, 0}, {2, 0, 2, 0, 0}, {2, 2, 0, 0, 0}, {0, 0, 0, 0, 3}, {0, 0, 0, 3, 0}}};
    assert(!check_team(league, 0).eliminated);
    Elimination piura = check_team(league, 3);
    assert(piura.eliminated && !piura.trivial && piura.flow == 5 && piura.games_left == 6);
    assert((piura.certificate == std::vector<int>{0, 1, 2}));
    Elimination callao = check_team(league, 4);
    assert(callao.eliminated && callao.trivial);

    Random random(31);
    int nontrivial = 0;
    for (int round = 0; round < 2500; round++) {
        int teams = 2 + below(random, 4);
        Championship random_league;
        random_league.games.assign(static_cast<std::size_t>(teams), std::vector<int>(static_cast<std::size_t>(teams), 0));
        random_league.names.assign(static_cast<std::size_t>(teams), "");
        for (int i = 0; i < teams; i++) random_league.wins.push_back(below(random, 7));
        int budget = 9;
        for (int i = 0; i < teams; i++) {
            for (int j = i + 1; j < teams; j++) {
                int g = std::min(budget, below(random, 3));
                budget -= g;
                random_league.games[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)] = g;
                random_league.games[static_cast<std::size_t>(j)][static_cast<std::size_t>(i)] = g;
            }
        }
        for (int x = 0; x < teams; x++) {
            Elimination result = check_team(random_league, x);
            assert(result.eliminated == !brute_can_finish_first(random_league, x));
            if (result.eliminated) {
                assert(!result.certificate.empty());
                assert(certificate_holds(random_league, result.best, result.certificate));
                nontrivial += !result.trivial;
            }
        }
    }
    assert(nontrivial > 0);
}

void test_projects() {
    const std::vector<long long> profit = {5, 4, 9, -6, -8, 3, 2, -5};
    const std::vector<Requirement> needs = {{0, 3}, {1, 3}, {2, 3}, {2, 4}, {5, 4}, {6, 7}};
    ProjectChoice choice = best_projects(profit, needs);
    assert(choice.value == 7 && choice.min_cut == 16 && choice.positive_total == 23);
    assert((choice.chosen == std::vector<int>{0, 1, 2, 3, 4, 5}));
    assert(greedy_packages(profit, needs).empty());
    assert(!is_closed(8, needs, best_projects(profit, needs, 1).chosen));

    Random random(555);
    for (int round = 0; round < 3000; round++) {
        int n = 1 + below(random, 8);
        std::vector<long long> values;
        for (int i = 0; i < n; i++) values.push_back(below(random, 21) - 10);
        std::vector<Requirement> requirements;
        for (int k = below(random, 2 * n); k > 0; k--) {
            int a = below(random, n);
            int b = below(random, n);
            if (a != b) requirements.push_back({a, b});  // también puede haber ciclos de requisitos
        }
        ProjectChoice result = best_projects(values, requirements);
        assert(result.value == brute_projects(values, requirements));
        assert(is_closed(n, requirements, result.chosen));
        assert(total_profit(values, result.chosen) == result.value);
    }

    // Capacidades grandes: el "infinito" y las sumas caben en long long, no en int.
    const std::vector<long long> big = {3000000000, -2000000000, 1000000000};
    ProjectChoice large = best_projects(big, {{0, 1}, {2, 1}});
    assert(large.value == 2000000000);
}

void test_lower_bounds() {
    auto network = [](long long low, long long high) {
        return std::vector<BoundedEdge>{{0, 1, low, high}, {0, 2, low, high}, {1, 3, 0, 3}, {1, 4, 0, 1},
                                        {2, 4, 0, 2},      {3, 5, 0, 3},      {4, 5, 0, 2}};
    };
    BoundedFlow plain = max_flow_with_lower_bounds(6, network(0, 4), 0, 5);
    assert(plain.value == 5 && plain.on_edge[1] == 1);  // el máximo sin restricción deja a B con 1
    BoundedFlow at_most = max_flow_with_lower_bounds(6, network(0, 2), 0, 5);
    assert(at_most.value == 4);
    BoundedFlow at_least = max_flow_with_lower_bounds(6, network(2, 4), 0, 5);
    assert(at_least.feasible && at_least.value == 5 && at_least.on_edge[0] == 3 && at_least.on_edge[1] == 2);

    Random random(808);
    for (int round = 0; round < 1500; round++) {
        int nodes = 2 + below(random, 3);
        int s = 0;
        int t = nodes - 1;
        std::vector<BoundedEdge> edges;
        for (int k = 1 + below(random, 5); k > 0; k--) {
            int a = below(random, nodes);
            int b = below(random, nodes);
            if (a == b || b == s || a == t) continue;  // la fuerza bruta cuenta el valor como lo que sale de s
            long long low = below(random, 2);
            edges.push_back({a, b, low, low + below(random, 3)});
        }
        long long expected = brute_bounded(nodes, edges, s, t);
        BoundedFlow result = max_flow_with_lower_bounds(nodes, edges, s, t);
        assert(result.feasible == (expected >= 0));
        if (result.feasible) {
            assert(result.value == expected);
            for (std::size_t k = 0; k < edges.size(); k++) {
                assert(edges[k].low <= result.on_edge[k] && result.on_edge[k] <= edges[k].high);
            }
        }
    }
}

}  // namespace

int main() {
    test_matching_examples();
    test_matching_random();
    test_quota_example();
    test_decomposition();
    test_menger();
    test_undirected();
    test_baseball();
    test_projects();
    test_lower_bounds();
    std::cout << "Todas las pruebas de la semana 12 pasaron.\n";
}