// Distancia de edición: la tabla, el camino hacia atrás y el alineamiento.
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "sequences.h"

namespace {

void print_table(const std::string& a, const std::string& b, const Table& table) {
    std::cout << "    ";
    for (char c : b) std::cout << std::setw(2) << c;
    std::cout << '\n';
    for (std::size_t i = 0; i <= a.size(); i++) {
        std::cout << (i == 0 ? ' ' : a[i - 1]) << " ";
        for (std::size_t j = 0; j <= b.size(); j++) std::cout << std::setw(2) << table[i][j];
        std::cout << '\n';
    }
}

void show(const std::string& a, const std::string& b) {
    const Table dist = edit_table(a, b);
    std::cout << a << " -> " << b << '\n';
    print_table(a, b, dist);
    std::cout << "Distancia: " << dist[a.size()][b.size()] << '\n';
    const std::vector<EditStep> steps = edit_walk(a, b, dist);

    std::string top;
    std::string bottom;
    std::string mark;
    for (const EditStep& s : steps) {
        top.push_back(s.kind == EditStep::Kind::insert ? '-' : a[s.i]);
        bottom.push_back(s.kind == EditStep::Kind::erase ? '-' : b[s.j]);
        mark.push_back(s.kind == EditStep::Kind::keep ? ' ' : '*');
    }
    std::cout << "Alineamiento:\n  " << top << "\n  " << bottom << "\n  " << mark << '\n';
    std::cout << "Operaciones:\n";
    for (const EditStep& s : steps) {
        if (s.kind == EditStep::Kind::change) {
            std::cout << "  cambiar " << a[s.i] << " por " << b[s.j] << '\n';
        } else if (s.kind == EditStep::Kind::erase) {
            std::cout << "  borrar " << a[s.i] << '\n';
        } else if (s.kind == EditStep::Kind::insert) {
            std::cout << "  insertar " << b[s.j] << '\n';
        }
    }
    std::cout << "Con solo borrar e insertar: " << static_cast<int>(a.size() + b.size()) - 2 * lcs_table(a, b)[a.size()][b.size()]
              << "\n\n";
}

}  // namespace

int main() {
    show("casa", "cosas");
    show("algoritmo", "logaritmo");
}

// Cuántas llamadas hace Fibonacci con y sin memoización, y qué subproblemas repite.
#include <iomanip>
#include <iostream>
#include <vector>

#include "fibonacci.h"

int main() {
    std::cout << " n          F(n)   sin memoizar   memoizando\n";
    for (int n : {5, 10, 20, 30, 40}) {
        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);
        long long memo_calls = 0;
        std::vector<long long> memo(static_cast<std::size_t>(n) + 1, -1);
        fib_memo(n, memo, memo_calls);
        std::cout << std::setw(2) << n << std::setw(14) << value << std::setw(15) << plain_calls
                  << std::setw(13) << memo_calls << '\n';
    }

    long long calls = 0;
    std::vector<long long> times(11, 0);
    fib_plain(10, calls, times);
    std::cout << "\nfib(10): cuántas veces se calcula cada subproblema\n";
    for (std::size_t k = 0; k <= 10; k++) {
        std::cout << "  F(" << k << "): " << times[k] << '\n';
    }

    std::cout << "\nF(90) con tabla:         " << fib_table(90) << '\n';
    std::cout << "F(90) con dos variables: " << fib_two_vars(90) << '\n';
}

// Fibonacci de cuatro formas: la recursión directa, con memoización, con tabla y con dos variables.
// F(0) = 0, F(1) = 1. Con long long alcanza hasta F(92).
#pragma once

#include <cstddef>
#include <vector>

// Cuenta en calls cada llamada, y en times[k] cuántas veces se calculó F(k).
inline long long fib_plain(int n, long long& calls, std::vector<long long>& times) {
    calls++;
    times[static_cast<std::size_t>(n)]++;
    if (n < 2) return n;
    return fib_plain(n - 1, calls, times) + fib_plain(n - 2, calls, times);
}

// memo[k] = -1 significa que F(k) todavía no se calcula.
inline long long fib_memo(int n, std::vector<long long>& memo, long long& calls) {
    calls++;
    if (n < 2) return n;
    const std::size_t k = static_cast<std::size_t>(n);
    if (memo[k] < 0) {
        memo[k] = fib_memo(n - 1, memo, calls) + fib_memo(n - 2, memo, calls);
    }
    return memo[k];
}

// La misma recurrencia, de los casos pequeños a los grandes. No hay llamadas recursivas.
inline long long fib_table(int n) {
    std::vector<long long> table(static_cast<std::size_t>(n) + 2, 0);
    table[1] = 1;
    for (std::size_t k = 2; k <= static_cast<std::size_t>(n); k++) {
        table[k] = table[k - 1] + table[k - 2];
    }
    return table[static_cast<std::size_t>(n)];
}

// Cada casilla solo lee las dos anteriores, así que basta guardar esas dos.
inline long long fib_two_vars(int n) {
    long long previous = 1;  // F(-1), que se define como 1 para que la suma cuadre
    long long current = 0;   // F(0)
    for (int k = 1; k <= n; k++) {
        const long long next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}

// Mochila: los greedy que fallan, la tabla completa y la reconstrucción.
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>

#include "knapsack.h"

namespace {

void print_items(const std::vector<Item>& items, std::size_t capacity) {
    std::cout << "  capacidad " << capacity << ", objetos (peso, valor):";
    for (const Item& item : items) std::cout << " (" << item.weight << ", " << item.value << ")";
    std::cout << '\n';
}

void compare(const char* title, const std::vector<Item>& items, std::size_t capacity) {
    std::cout << title << ":\n";
    print_items(items, capacity);
    std::cout << "  óptimo por fuerza bruta: " << knapsack_brute(items, capacity) << '\n';
    std::cout << "  mayor valor/peso:        " << greedy_by_ratio(items, capacity) << '\n';
    std::cout << "  mayor valor:             " << greedy_by_value(items, capacity) << '\n';
    std::cout << "  sin capacidad en el subproblema: " << knapsack_without_capacity(items, capacity) << '\n';
    std::cout << "  tabla:                   " << knapsack_table(items, capacity).back()[capacity] << "\n\n";
}

}  // namespace

int main() {
    const std::vector<Item> items = {{2, 3}, {3, 4}, {4, 5}, {5, 8}};
    const std::size_t capacity = 9;
    compare("El ejemplo de la tabla", items, capacity);
    compare("Un objeto valioso que no deja sitio", {{6, 30}, {5, 20}, {5, 20}}, 10);

    const std::vector<std::vector<long long>> table = knapsack_table(items, capacity);
    std::cout << "        c:";
    for (std::size_t c = 0; c <= capacity; c++) std::cout << std::setw(3) << c;
    std::cout << '\n';
    for (std::size_t i = 0; i <= items.size(); i++) {
        if (i == 0) {
            std::cout << "ninguno  ";
        } else {
            std::cout << "(" << items[i - 1].weight << ", " << items[i - 1].value << ")   ";
        }
        std::cout << " ";
        for (std::size_t c = 0; c <= capacity; c++) std::cout << std::setw(3) << table[i][c];
        std::cout << '\n';
    }

    std::cout << "\nHacia atrás:\n";
    std::size_t c = capacity;
    for (std::size_t i = items.size(); i > 0; i--) {
        const long long here = table[i][c];
        const long long above = table[i - 1][c];
        if (here != above) {
            std::cout << "  T[" << i << "][" << c << "] = " << here << " != T[" << i - 1 << "][" << c << "] = " << above
                      << ": se toma (" << items[i - 1].weight << ", " << items[i - 1].value << "), c = " << c << " - "
                      << items[i - 1].weight << '\n';
            c -= items[i - 1].weight;
        } else {
            std::cout << "  T[" << i << "][" << c << "] = " << here << " = T[" << i - 1 << "][" << c << "]: no hace falta ("
                      << items[i - 1].weight << ", " << items[i - 1].value << ")\n";
        }
    }

    std::map<std::pair<std::size_t, std::size_t>, long long> memo;
    const long long memo_value = knapsack_memo(items, items.size(), capacity, memo);
    std::cout << "\nCon memoización: valor " << memo_value << ", " << memo.size() << " estados calculados";
    std::cout << " de " << items.size() * (capacity + 1) << " casillas con i >= 1\n";
}

// Una sola fila: de mayor a menor funciona; de menor a mayor resuelve otro problema.
#include <iomanip>
#include <iostream>
#include <vector>

#include "knapsack.h"

namespace {

void print_row(const std::vector<long long>& row) {
    for (long long value : row) std::cout << std::setw(3) << value;
    std::cout << '\n';
}

}  // namespace

int main() {
    const Item item = {2, 3};
    const std::size_t capacity = 6;
    std::cout << "Un solo objeto (peso 2, valor 3), capacidad 6\n";

    std::cout << "\nDe mayor a menor:\n         c:  0  1  2  3  4  5  6\n";
    std::vector<long long> row(capacity + 1, 0);
    for (std::size_t c = capacity + 1; c-- > item.weight;) {
        row[c] = std::max(row[c], item.value + row[c - item.weight]);
        std::cout << "tras c = " << c << ":";
        print_row(row);
    }

    std::cout << "\nDe menor a mayor:\n         c:  0  1  2  3  4  5  6\n";
    row.assign(capacity + 1, 0);
    for (std::size_t c = item.weight; c <= capacity; c++) {
        row[c] = std::max(row[c], item.value + row[c - item.weight]);
        std::cout << "tras c = " << c << ":";
        print_row(row);
    }

    const std::vector<Item> items = {{2, 3}, {3, 4}, {4, 5}, {5, 8}};
    const std::size_t big = 9;
    std::cout << "\nLos objetos del ejemplo, capacidad 9\n";
    std::cout << "  tabla completa:      " << knapsack_table(items, big).back()[big] << '\n';
    std::cout << "  fila, mayor a menor: " << knapsack_one_row(items, big) << '\n';
    std::cout << "  fila, menor a mayor: " << knapsack_one_row_ascending(items, big) << '\n';
    std::cout << "  sin límite de copias: " << unbounded_knapsack(items, big) << '\n';
}

// Mochila 0/1: cada objeto se toma una vez o ninguna, sin pasar de la capacidad. Pesos enteros
// positivos y valores no negativos.
#pragma once

#include <algorithm>
#include <cstddef>
#include <map>
#include <utility>
#include <vector>

struct Item {
    std::size_t weight;
    long long value;
};

// table[i][c]: el máximo valor con los primeros i objetos y capacidad c.
inline std::vector<std::vector<long long>> knapsack_table(const std::vector<Item>& items, std::size_t capacity) {
    const std::size_t n = items.size();
    std::vector<std::vector<long long>> table(n + 1, std::vector<long long>(capacity + 1, 0));
    for (std::size_t i = 1; i <= n; i++) {
        const Item& item = items[i - 1];
        for (std::size_t c = 0; c <= capacity; c++) {
            table[i][c] = table[i - 1][c];  // sin el objeto
            if (item.weight <= c) {
                table[i][c] = std::max(table[i][c], item.value + table[i - 1][c - item.weight]);
            }
        }
    }
    return table;
}

// Camina hacia atrás: si la casilla es distinta de la de arriba, el objeto i - 1 se usó.
inline std::vector<std::size_t> knapsack_choose(const std::vector<Item>& items,
                                                const std::vector<std::vector<long long>>& table) {
    std::vector<std::size_t> chosen;
    std::size_t c = table[0].size() - 1;
    for (std::size_t i = items.size(); i > 0; i--) {
        if (table[i][c] != table[i - 1][c]) {
            chosen.push_back(i - 1);
            c -= items[i - 1].weight;
        }
    }
    std::reverse(chosen.begin(), chosen.end());
    return chosen;
}

// Una sola fila, con la capacidad de mayor a menor. Invariante, al escribir la casilla c: las
// casillas mayores que c ya tienen este objeto en cuenta y las demás todavía no.
inline long long knapsack_one_row(const std::vector<Item>& items, std::size_t capacity) {
    std::vector<long long> row(capacity + 1, 0);
    for (const Item& item : items) {
        for (std::size_t c = capacity + 1; c-- > item.weight;) {
            row[c] = std::max(row[c], item.value + row[c - item.weight]);
        }
    }
    return row[capacity];
}

// El mismo código, de menor a mayor: la casilla c - weight ya pudo usar este objeto.
inline long long knapsack_one_row_ascending(const std::vector<Item>& items, std::size_t capacity) {
    std::vector<long long> row(capacity + 1, 0);
    for (const Item& item : items) {
        for (std::size_t c = item.weight; c <= capacity; c++) {
            row[c] = std::max(row[c], item.value + row[c - item.weight]);
        }
    }
    return row[capacity];
}

// Mochila sin límite de copias, por su propia recurrencia: el último objeto puesto es alguno.
inline long long unbounded_knapsack(const std::vector<Item>& items, std::size_t capacity) {
    std::vector<long long> best(capacity + 1, 0);
    for (std::size_t c = 1; c <= capacity; c++) {
        for (const Item& item : items) {
            if (item.weight <= c) best[c] = std::max(best[c], item.value + best[c - item.weight]);
        }
    }
    return best[capacity];
}

// Greedy por valor/peso, de mayor a menor, tomando lo que quepa. Se compara sin dividir.
inline long long greedy_by_ratio(std::vector<Item> items, std::size_t capacity) {
    std::stable_sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.value * static_cast<long long>(b.weight) > b.value * static_cast<long long>(a.weight);
    });
    long long total = 0;
    for (const Item& item : items) {
        if (item.weight <= capacity) {
            capacity -= item.weight;
            total += item.value;
        }
    }
    return total;
}

inline long long greedy_by_value(std::vector<Item> items, std::size_t capacity) {
    std::stable_sort(items.begin(), items.end(), [](const Item& a, const Item& b) { return a.value > b.value; });
    long long total = 0;
    for (const Item& item : items) {
        if (item.weight <= capacity) {
            capacity -= item.weight;
            total += item.value;
        }
    }
    return total;
}

// Un subproblema al que le falta información: "lo mejor con los primeros i objetos", sin la
// capacidad. Guarda una sola respuesta por i y le agrega el objeto si todavía cabe.
inline long long knapsack_without_capacity(const std::vector<Item>& items, std::size_t capacity) {
    long long best_value = 0;
    std::size_t best_weight = 0;
    for (const Item& item : items) {
        if (best_weight + item.weight <= capacity) {
            best_weight += item.weight;
            best_value += item.value;
        }
    }
    return best_value;
}

// Con memoización solo se calculan los estados a los que la recursión llega.
inline long long knapsack_memo(const std::vector<Item>& items, std::size_t i, std::size_t c,
                               std::map<std::pair<std::size_t, std::size_t>, long long>& memo) {
    if (i == 0) return 0;
    const std::pair<std::size_t, std::size_t> key(i, c);
    const auto found = memo.find(key);
    if (found != memo.end()) return found->second;
    const Item& item = items[i - 1];
    long long result = knapsack_memo(items, i - 1, c, memo);
    if (item.weight <= c) {
        result = std::max(result, item.value + knapsack_memo(items, i - 1, c - item.weight, memo));
    }
    memo[key] = result;
    return result;
}

// Prueba los 2^n subconjuntos. Solo sirve de árbitro con n pequeño.
inline long long knapsack_brute(const std::vector<Item>& items, std::size_t capacity) {
    const std::size_t n = items.size();
    long long best = 0;
    for (unsigned mask = 0; mask < (1U << n); mask++) {
        std::size_t weight = 0;
        long long value = 0;
        for (std::size_t i = 0; i < n; i++) {
            if ((mask >> i) & 1U) {
                weight += items[i].weight;
                value += items[i].value;
            }
        }
        if (weight <= capacity) best = std::max(best, value);
    }
    return best;
}

// Subsecuencia común más larga: la tabla, dos reconstrucciones y la diferencia con una subcadena.
#include <iomanip>
#include <iostream>
#include <string>

#include "sequences.h"

namespace {

void print_table(const std::string& a, const std::string& b, const Table& table) {
    std::cout << "    ";
    for (char c : b) std::cout << std::setw(2) << c;
    std::cout << '\n';
    for (std::size_t i = 0; i <= a.size(); i++) {
        std::cout << (i == 0 ? ' ' : a[i - 1]) << " ";
        for (std::size_t j = 0; j <= b.size(); j++) std::cout << std::setw(2) << table[i][j];
        std::cout << '\n';
    }
}

}  // namespace

int main() {
    const std::string a = "algoritmo";
    const std::string b = "logaritmo";
    const Table lcs = lcs_table(a, b);
    print_table(a, b, lcs);
    std::cout << "\nLargo: " << lcs[a.size()][b.size()] << '\n';
    std::cout << "Hacia atrás, prefiriendo subir:    " << lcs_walk(a, b, lcs, true) << '\n';
    std::cout << "Hacia atrás, prefiriendo la izquierda: " << lcs_walk(a, b, lcs, false) << '\n';
    std::cout << "Subcadena común más larga:         " << longest_common_substring(a, b) << '\n';
}

// Mide la mochila de una fila con n fijo y W creciente: cada bit más de W duplica el trabajo.
// Se compila con -O2. Se toma el menor de 3 intentos.
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

#include "knapsack.h"

int main() {
    const std::size_t n = 200;
    std::cout << "n = " << n << ", pesos al azar entre 1 y W/2, menor de 3 intentos\n";
    std::cout << " bits de W           W    casillas n·W          ms\n";
    double previous = 0;
    for (unsigned bits = 16; bits <= 25; bits++) {
        const std::size_t capacity = std::size_t{1} << (bits - 1);
        std::mt19937 rng(42);
        std::vector<Item> items;
        for (std::size_t i = 0; i < n; i++) {
            items.push_back({1 + rng() % (capacity / 2), static_cast<long long>(1 + rng() % 1000000)});
        }
        double best_ms = 1e18;
        long long answer = 0;
        for (int attempt = 0; attempt < 3; attempt++) {
            const auto begin = std::chrono::steady_clock::now();
            answer = knapsack_one_row(items, capacity);
            const auto end = std::chrono::steady_clock::now();
            best_ms = std::min(best_ms, std::chrono::duration<double, std::milli>(end - begin).count());
        }
        std::cout << std::setw(9) << bits << std::setw(12) << capacity << std::setw(16)
                  << static_cast<unsigned long long>(n) * capacity << std::setw(12) << std::fixed << std::setprecision(1)
                  << best_ms;
        if (previous > 0) std::cout << "   x" << std::setprecision(2) << best_ms / previous;
        std::cout << "   (óptimo " << answer << ")\n";
        previous = best_ms;
    }
}

// Subsecuencia común más larga y distancia de edición sobre dos cadenas. Los prefijos son
// semiabiertos: la casilla (i, j) habla de a[0..i) y b[0..j), así que la tabla mide (n+1) x (m+1).
#pragma once

#include <algorithm>
#include <cstddef>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>

using Table = std::vector<std::vector<int>>;

// lcs[i][j]: el largo de la subsecuencia común más larga de a[0..i) y b[0..j).
inline Table lcs_table(const std::string& a, const std::string& b) {
    Table lcs(a.size() + 1, std::vector<int>(b.size() + 1, 0));
    for (std::size_t i = 1; i <= a.size(); i++) {
        for (std::size_t j = 1; j <= b.size(); j++) {
            if (a[i - 1] == b[j - 1]) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            } else {
                lcs[i][j] = std::max(lcs[i - 1][j], lcs[i][j - 1]);
            }
        }
    }
    return lcs;
}

// Reconstruye una subsecuencia. Ante un empate entre arriba e izquierda, prefer_up decide.
inline std::string lcs_walk(const std::string& a, const std::string& b, const Table& lcs, bool prefer_up) {
    std::string result;
    std::size_t i = a.size();
    std::size_t j = b.size();
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            result.push_back(a[i - 1]);
            i--;
            j--;
        } else if (lcs[i - 1][j] > lcs[i][j - 1] || (lcs[i - 1][j] == lcs[i][j - 1] && prefer_up)) {
            i--;
        } else {
            j--;
        }
    }
    std::reverse(result.begin(), result.end());
    return result;
}

inline bool is_subsequence(const std::string& small, const std::string& big) {
    std::size_t k = 0;
    for (char c : big) {
        if (k < small.size() && small[k] == c) k++;
    }
    return k == small.size();
}

// Prueba las 2^n subsecuencias de a. Solo sirve de árbitro con cadenas cortas.
inline std::size_t lcs_brute(const std::string& a, const std::string& b) {
    std::size_t best = 0;
    for (unsigned mask = 0; mask < (1U << a.size()); mask++) {
        std::string candidate;
        for (std::size_t i = 0; i < a.size(); i++) {
            if ((mask >> i) & 1U) candidate.push_back(a[i]);
        }
        if (is_subsequence(candidate, b)) best = std::max(best, candidate.size());
    }
    return best;
}

// Subcadena común más larga: tiene que ser contigua. run[i][j] es el largo del tramo común que
// termina justo en a[i - 1] y b[j - 1], y la respuesta es el máximo de toda la tabla.
inline std::string longest_common_substring(const std::string& a, const std::string& b) {
    Table run(a.size() + 1, std::vector<int>(b.size() + 1, 0));
    int best = 0;
    std::size_t best_end = 0;
    for (std::size_t i = 1; i <= a.size(); i++) {
        for (std::size_t j = 1; j <= b.size(); j++) {
            if (a[i - 1] == b[j - 1]) {
                run[i][j] = run[i - 1][j - 1] + 1;
                if (run[i][j] > best) {
                    best = run[i][j];
                    best_end = i;
                }
            }
        }
    }
    return a.substr(best_end - static_cast<std::size_t>(best), static_cast<std::size_t>(best));
}

// dist[i][j]: el mínimo de operaciones para convertir a[0..i) en b[0..j).
inline Table edit_table(const std::string& a, const std::string& b) {
    Table dist(a.size() + 1, std::vector<int>(b.size() + 1, 0));
    for (std::size_t i = 0; i <= a.size(); i++) dist[i][0] = static_cast<int>(i);
    for (std::size_t j = 0; j <= b.size(); j++) dist[0][j] = static_cast<int>(j);
    for (std::size_t i = 1; i <= a.size(); i++) {
        for (std::size_t j = 1; j <= b.size(); j++) {
            const int change = a[i - 1] == b[j - 1] ? 0 : 1;
            dist[i][j] = std::min({dist[i - 1][j] + 1,            // borrar a[i - 1]
                                   dist[i][j - 1] + 1,            // insertar b[j - 1]
                                   dist[i - 1][j - 1] + change});  // conservar o cambiar
        }
    }
    return dist;
}

// Una columna del alineamiento. Las posiciones son de las cadenas originales.
struct EditStep {
    enum class Kind { keep, change, erase, insert };
    Kind kind;
    std::size_t i;  // posición en a (no se usa si kind es insert)
    std::size_t j;  // posición en b (no se usa si kind es erase)
};

// Camina hacia atrás desde la esquina. En cada casilla toma una opción que explique su valor.
// Ante un empate prefiere la diagonal, luego borrar y luego insertar.
inline std::vector<EditStep> edit_walk(const std::string& a, const std::string& b, const Table& dist) {
    std::vector<EditStep> steps;
    std::size_t i = a.size();
    std::size_t j = b.size();
    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && a[i - 1] == b[j - 1] && dist[i][j] == dist[i - 1][j - 1]) {
            steps.push_back({EditStep::Kind::keep, i - 1, j - 1});
            i--;
            j--;
        } else if (i > 0 && j > 0 && dist[i][j] == dist[i - 1][j - 1] + 1) {
            steps.push_back({EditStep::Kind::change, i - 1, j - 1});
            i--;
            j--;
        } else if (i > 0 && dist[i][j] == dist[i - 1][j] + 1) {
            steps.push_back({EditStep::Kind::erase, i - 1, 0});
            i--;
        } else {
            steps.push_back({EditStep::Kind::insert, 0, j - 1});
            j--;
        }
    }
    std::reverse(steps.begin(), steps.end());
    return steps;
}

// Aplica los pasos a a y devuelve lo que resulta, sin mirar b salvo por los caracteres nuevos.
inline std::string apply_steps(const std::string& a, const std::string& b, const std::vector<EditStep>& steps) {
    std::string out;
    for (const EditStep& s : steps) {
        if (s.kind == EditStep::Kind::keep) out.push_back(a[s.i]);
        if (s.kind == EditStep::Kind::change || s.kind == EditStep::Kind::insert) out.push_back(b[s.j]);
    }
    return out;
}

inline int edit_cost(const std::vector<EditStep>& steps) {
    int cost = 0;
    for (const EditStep& s : steps) {
        if (s.kind != EditStep::Kind::keep) cost++;
    }
    return cost;
}

// Con dos filas basta para el número, pero ya no se puede caminar hacia atrás.
inline int edit_two_rows(const std::string& a, const std::string& b) {
    std::vector<int> previous(b.size() + 1);
    std::vector<int> current(b.size() + 1);
    for (std::size_t j = 0; j <= b.size(); j++) previous[j] = static_cast<int>(j);
    for (std::size_t i = 1; i <= a.size(); i++) {
        current[0] = static_cast<int>(i);
        for (std::size_t j = 1; j <= b.size(); j++) {
            const int change = a[i - 1] == b[j - 1] ? 0 : 1;
            current[j] = std::min({previous[j] + 1, current[j - 1] + 1, previous[j - 1] + change});
        }
        std::swap(previous, current);
    }
    return previous[b.size()];
}

// Árbitro: BFS sobre las cadenas, con la definición misma de una operación (sin alineamientos y
// sin recurrencia). Cadenas de a lo sumo max_length caracteres sobre el alfabeto dado. Con
// allow_change en falso, solo borrar e insertar.
inline int edit_bfs(const std::string& a, const std::string& b, const std::string& alphabet, std::size_t max_length,
                    bool allow_change) {
    std::set<std::string> seen = {a};
    std::queue<std::pair<std::string, int>> pending;
    pending.push({a, 0});
    while (!pending.empty()) {
        const std::string s = pending.front().first;
        const int d = pending.front().second;
        pending.pop();
        if (s == b) return d;
        std::vector<std::string> next;
        for (std::size_t p = 0; p < s.size(); p++) {
            next.push_back(s.substr(0, p) + s.substr(p + 1));
            if (allow_change) {
                for (char c : alphabet) next.push_back(s.substr(0, p) + c + s.substr(p + 1));
            }
        }
        if (s.size() < max_length) {
            for (std::size_t p = 0; p <= s.size(); p++) {
                for (char c : alphabet) next.push_back(s.substr(0, p) + c + s.substr(p));
            }
        }
        for (const std::string& t : next) {
            if (seen.insert(t).second) pending.push({t, d + 1});
        }
    }
    return -1;
}

// Intervalos con pesos: los greedy que fallan y el recorrido de la tabla.
#include <iomanip>
#include <iostream>
#include <vector>

#include "weighted_intervals.h"

namespace {

void print_classes(const std::vector<WeightedInterval>& classes) {
    for (const WeightedInterval& c : classes) {
        std::cout << " [" << c.start << ',' << c.finish << ")v" << c.value;
    }
    std::cout << '\n';
}

void compare(const char* title, const std::vector<WeightedInterval>& classes) {
    std::cout << title << ":\n  clases:";
    print_classes(classes);
    std::cout << "  óptimo por fuerza bruta: " << weighted_brute(classes) << '\n';
    std::cout << "  termina antes (semana 4): " << greedy_earliest_finish(classes) << '\n';
    std::cout << "  mayor valor primero:      " << greedy_highest_value(classes) << '\n';
    std::cout << "  tabla:                    " << weighted_best(classes) << "\n\n";
}

}  // namespace

int main() {
    compare("Una clase valiosa en medio", {{0, 2, 1}, {1, 6, 10}, {5, 7, 1}});
    compare("Una clase larga que estorba", {{0, 10, 5}, {0, 3, 4}, {3, 6, 4}, {6, 10, 4}});

    std::vector<WeightedInterval> classes = {{0, 3, 2}, {1, 5, 4}, {3, 7, 4}, {4, 9, 6}, {7, 10, 2}, {8, 11, 3}};
    compare("El ejemplo del recorrido", classes);

    sort_by_finish(classes);
    const std::vector<std::size_t> p = compatible_prefix(classes);
    const std::vector<long long> best = weighted_table(classes, p);
    std::cout << "j  clase   valor  p(j)  sin ella  con ella  T[j]\n";
    std::cout << "0  -           -     -         -         -" << std::setw(6) << best[0] << '\n';
    for (std::size_t j = 1; j <= classes.size(); j++) {
        const WeightedInterval& c = classes[j - 1];
        std::cout << j << "  [" << c.start << ',' << std::setw(2) << c.finish << ")" << std::setw(7) << c.value << std::setw(6) << p[j - 1] << std::setw(10) << best[j - 1]
                  << std::setw(10) << c.value + best[p[j - 1]] << std::setw(6) << best[j] << '\n';
    }

    std::cout << "\nHacia atrás:\n";
    std::size_t j = classes.size();
    while (j > 0) {
        if (best[j] == best[j - 1]) {
            std::cout << "  T[" << j << "] = T[" << j - 1 << "] = " << best[j] << ": no hace falta la clase " << j
                      << ", j = " << j - 1 << '\n';
            j--;
        } else {
            const WeightedInterval& c = classes[j - 1];
            std::cout << "  T[" << j << "] = " << best[j] << " > T[" << j - 1 << "] = " << best[j - 1] << ": se toma ["
                      << c.start << ',' << c.finish << "), j = p(" << j << ") = " << p[j - 1] << '\n';
            j = p[j - 1];
        }
    }
    std::cout << "Elegidas:";
    for (std::size_t i : weighted_choose(classes, p, best)) {
        std::cout << " [" << classes[i].start << ',' << classes[i].finish << ")";
    }
    std::cout << ", valor " << best.back() << '\n';

    std::cout << "\nSi el borde contara como cruce (lower_bound en vez de upper_bound):\n";
    const std::vector<std::size_t> closed = compatible_prefix_closed(classes);
    std::cout << "  p:";
    for (std::size_t value : closed) std::cout << ' ' << value;
    std::cout << "\n  valor: " << weighted_table(classes, closed).back() << " en vez de " << best.back() << '\n';
}