// Tipos de cambio: un producto mayor que 1 es una suma negativa de -ln(tasa). Estas funciones solo
// responden si, desde la moneda 0, se detecta un ciclo. Con ellas se mide qué hace el redondeo.
#pragma once

#include <cmath>
#include <cstddef>
#include <limits>
#include <vector>

struct Rate {
    int from;
    int to;
    double rate;  // una unidad de from compra rate unidades de to
};

// La suma de -ln(tasa) a lo largo de una cadena de tasas.
inline double log_sum(const std::vector<double>& rates) {
    double total = 0;
    for (double r : rates) total += -std::log(r);
    return total;
}

// Bellman-Ford desde la moneda 0, con pesos -ln(tasa) + epsilon. Dice si la vuelta n relajó algo.
inline bool round_n_relaxes(int n, const std::vector<Rate>& rates, double epsilon) {
    const double unreached = std::numeric_limits<double>::infinity();
    std::vector<double> d(static_cast<std::size_t>(n), unreached);
    d[0] = 0;
    bool relaxed = false;
    for (int round = 1; round <= n; round++) {
        relaxed = false;
        for (const Rate& e : rates) {
            const auto u = static_cast<std::size_t>(e.from);
            const auto v = static_cast<std::size_t>(e.to);
            if (d[u] == unreached) continue;
            const double through = d[u] + (-std::log(e.rate) + epsilon);
            if (through < d[v]) {
                d[v] = through;
                relaxed = true;
            }
        }
        if (!relaxed) return false;
    }
    return relaxed;
}

// Cinco monedas con valores 1, 1,25, 1,6, 2,5 y 0,4, y la tasa exacta entre cada par. Todos los
// productos alrededor de un ciclo valen exactamente 1, así que no hay arbitraje.
inline std::vector<Rate> consistent_table() {
    return {{0, 1, 1.25},  {0, 2, 1.6},  {0, 3, 2.5},    {0, 4, 0.4},  {1, 0, 0.8},  {1, 2, 1.28}, {1, 3, 2},
            {1, 4, 0.32},  {2, 0, 0.625}, {2, 1, 0.78125}, {2, 3, 1.5625}, {2, 4, 0.25}, {3, 0, 0.4},  {3, 1, 0.5},
            {3, 2, 0.64},  {3, 4, 0.16}, {4, 0, 2.5},    {4, 1, 3.125}, {4, 2, 4},    {4, 3, 6.25}};
}

// Un ciclo de largo L, todas las tasas 1 menos una: su producto es exactamente 1,000001.
inline std::vector<Rate> long_cycle(int length) {
    std::vector<Rate> rates;
    for (int i = 0; i < length; i++) rates.push_back({i, (i + 1) % length, i == 0 ? 1.000001 : 1.0});
    return rates;
}