// Cadena de matrices: la pregunta de repaso, el greedy que falla, la tabla por largo y el orden ingenuo.
#include <iomanip>
#include <iostream>
#include <vector>

#include "interval_dp.h"

namespace {

void print_dimensions(const std::vector<long long>& d) {
    for (std::size_t i = 0; i + 1 < d.size(); i++) {
        std::cout << (i ? ", " : "") << d[i] << "x" << d[i + 1];
    }
}

void print_table(const CostTable& cost) {
    const int n = static_cast<int>(cost.size());
    std::cout << "  i\\j";
    for (int j = 0; j < n; j++) std::cout << std::setw(8) << j;
    std::cout << '\n';
    for (int i = 0; i < n; i++) {
        std::cout << std::setw(5) << i;
        for (int j = 0; j < n; j++) {
            if (j < i) {
                std::cout << std::setw(8) << ".";
            } else {
                std::cout << std::setw(8) << cost[i][j];
            }
        }
        std::cout << '\n';
    }
}

void show_chain(const std::vector<long long>& d) {
    std::cout << "Matrices: ";
    print_dimensions(d);
    const ChainTables t = matrix_chain(d);
    const int last = static_cast<int>(d.size()) - 2;
    std::cout << '\n';
    print_table(t.cost);
    std::cout << "Mínimo: " << t.cost[0][last] << ", con " << parenthesize(t.split, 0, last) << '\n';
}

}  // namespace

int main() {
    const std::vector<long long> review = {10, 30, 5, 60};
    show_chain(review);
    std::cout << "  (A0 A1) A2: " << 10 * 30 * 5 + 10 * 5 * 60 << '\n';
    std::cout << "  A0 (A1 A2): " << 30 * 5 * 60 + 10 * 30 * 60 << "\n\n";

    const std::vector<long long> greedy_case = {4, 1, 3, 5};
    std::cout << "Primero la multiplicación más barata\n  matrices: ";
    print_dimensions(greedy_case);
    std::cout << "\n  greedy: " << chain_cheapest_first(greedy_case) << ", óptimo por fuerza bruta: "
              << chain_brute(greedy_case) << "\n\n";

    const std::vector<long long> d = {10, 20, 5, 30, 2};
    show_chain(d);
    std::cout << "Por fuerza bruta: " << chain_brute(d) << "\n\n";

    std::cout << "Orden ingenuo: i de menor a mayor, j de menor a mayor, con la tabla en ceros\n";
    for (const std::vector<long long>& instance : {review, d}) {
        const NaiveOrderRun run = matrix_chain_naive_order(instance);
        std::cout << "  ";
        print_dimensions(instance);
        std::cout << '\n';
        for (const std::string& line : run.first_reads) std::cout << "    " << line << '\n';
        std::cout << "    lecturas vacías: " << run.empty_reads << ", respuesta: " << run.answer << ", correcta: "
                  << matrix_chain(instance).cost[0][instance.size() - 2] << '\n';
    }

    std::cout << "\nOtro orden válido, i de mayor a menor y j de menor a mayor: " << matrix_chain_i_descending(d) << '\n';

    long long combinations = 0;
    const std::vector<long long> ten(11, 2);
    matrix_chain(ten, &combinations);
    std::cout << "Con n = 10 matrices, combinaciones (i, k, j) probadas: " << combinations << '\n';
}