#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <expected>
#include <format>
#include <iostream>
#include <limits>
#include <optional>
#include <ranges>
#include <span>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

namespace memory {

struct MemoryId {
    std::size_t value{};
    auto operator<=>(const MemoryId&) const = default;
};

struct SourceId {
    std::size_t value{};
    auto operator<=>(const SourceId&) const = default;
};

enum class EvidenceKind {
    constraint,
    preference,
    outcome,
    qualifier
};

[[nodiscard]] constexpr auto kind_name(EvidenceKind kind) -> std::string_view {
    switch (kind) {
    case EvidenceKind::constraint:
        return "constraint";
    case EvidenceKind::preference:
        return "preference";
    case EvidenceKind::outcome:
        return "outcome";
    case EvidenceKind::qualifier:
        return "qualifier";
    }
    std::unreachable();
}

struct Interval {
    int begin{};
    std::optional<int> end;

    [[nodiscard]] auto contains(int day) const -> bool {
        return day >= begin && (!end || day < *end);
    }
};

struct MemoryUnit {
    MemoryId id;
    SourceId source_root;
    EvidenceKind kind;
    std::string text;
    std::size_t bundle_cost{};
    double relevance{};
    double utility{};
    Interval valid_time;
    Interval transaction_time;
    bool allowed{};
    bool supported{};
    bool active{};
};

[[nodiscard]] auto make_unit(
    MemoryId id,
    SourceId source_root,
    EvidenceKind kind,
    std::string text,
    std::size_t bundle_cost,
    double relevance,
    double utility,
    Interval valid_time,
    Interval transaction_time,
    bool allowed,
    bool supported,
    bool active) -> std::expected<MemoryUnit, std::string> {

    if (text.empty() || bundle_cost == 0) {
        return std::unexpected{"Evidence text and bundle cost are required."};
    }
    if (relevance < 0.0 || relevance > 1.0 ||
        utility < 0.0 || utility > 1.0) {
        return std::unexpected{"Relevance and utility must be in [0, 1]."};
    }
    if (valid_time.end && *valid_time.end <= valid_time.begin) {
        return std::unexpected{"Valid time must be a nonempty interval."};
    }
    if (transaction_time.end &&
        *transaction_time.end <= transaction_time.begin) {
        return std::unexpected{"Transaction time must be a nonempty interval."};
    }

    return MemoryUnit{
        id,
        source_root,
        kind,
        std::move(text),
        bundle_cost,
        relevance,
        utility,
        valid_time,
        transaction_time,
        allowed,
        supported,
        active};
}

[[nodiscard]] auto eligible(
    const MemoryUnit& unit,
    int valid_day,
    int knowledge_day) -> bool {
    return unit.allowed &&
           unit.supported &&
           unit.active &&
           unit.valid_time.contains(valid_day) &&
           unit.transaction_time.contains(knowledge_day);
}

struct Packet {
    std::vector<const MemoryUnit*> selected;
    std::vector<std::string> omissions;
    std::size_t cost{};
};

[[nodiscard]] auto relevance_baseline(
    std::span<const MemoryUnit> units,
    std::size_t budget) -> Packet {

    std::vector<const MemoryUnit*> ranked;
    ranked.reserve(units.size());
    std::ranges::transform(
        units,
        std::back_inserter(ranked),
        [](const MemoryUnit& unit) { return &unit; });
    std::ranges::stable_sort(
        ranked,
        std::greater{},
        [](const MemoryUnit* unit) { return unit->relevance; });

    Packet packet;
    for (const auto* unit : ranked) {
        if (packet.cost + unit->bundle_cost <= budget) {
            packet.selected.push_back(unit);
            packet.cost += unit->bundle_cost;
        }
    }
    return packet;
}

[[nodiscard]] auto already_has_kind(
    std::span<const MemoryUnit* const> selected,
    EvidenceKind kind) -> bool {
    return std::ranges::any_of(
        selected,
        [kind](const MemoryUnit* unit) { return unit->kind == kind; });
}

[[nodiscard]] auto already_has_source(
    std::span<const MemoryUnit* const> selected,
    SourceId source) -> bool {
    return std::ranges::any_of(
        selected,
        [source](const MemoryUnit* unit) {
            return unit->source_root == source;
        });
}

[[nodiscard]] auto marginal_value(
    const MemoryUnit& candidate,
    std::span<const MemoryUnit* const> selected) -> double {

    const double coverage =
        already_has_kind(selected, candidate.kind) ? 0.0 : 0.50;
    const double kind_redundancy =
        already_has_kind(selected, candidate.kind) ? 0.60 : 0.0;
    const double source_redundancy =
        already_has_source(selected, candidate.source_root) ? 0.70 : 0.0;

    return candidate.relevance +
           candidate.utility +
           coverage -
           kind_redundancy -
           source_redundancy;
}

[[nodiscard]] auto build_packet(
    std::span<const MemoryUnit> units,
    std::size_t budget,
    int valid_day,
    int knowledge_day) -> Packet {

    std::vector<const MemoryUnit*> remaining;
    remaining.reserve(units.size());

    Packet packet;
    for (const auto& unit : units) {
        if (eligible(unit, valid_day, knowledge_day)) {
            remaining.push_back(&unit);
        } else {
            packet.omissions.push_back(
                std::format("Memory {} failed an eligibility gate.",
                            unit.id.value));
        }
    }

    while (!remaining.empty()) {
        const MemoryUnit* best = nullptr;
        double best_value = -std::numeric_limits<double>::infinity();

        // Marginal value is recomputed after every selection because novelty
        // and shared provenance depend on the packet built so far.
        for (const auto* candidate : remaining) {
            if (packet.cost + candidate->bundle_cost > budget) {
                continue;
            }
            const double value = marginal_value(*candidate, packet.selected);
            if (value > best_value) {
                best = candidate;
                best_value = value;
            }
        }

        if (best == nullptr) {
            for (const auto* candidate : remaining) {
                packet.omissions.push_back(
                    std::format("Memory {} did not fit the remaining budget.",
                                candidate->id.value));
            }
            break;
        }

        packet.selected.push_back(best);
        packet.cost += best->bundle_cost;
        std::erase(remaining, best);
    }

    // Serialization is a separate operation from selection. Constraints lead,
    // then stable kind order keeps packets reproducible across equal scores.
    std::ranges::stable_sort(
        packet.selected,
        std::less{},
        [](const MemoryUnit* unit) {
            return static_cast<int>(unit->kind);
        });
    return packet;
}

void print_packet(std::string_view label, const Packet& packet) {
    std::cout << std::format("{} | cost {}\n", label, packet.cost);
    for (const auto* unit : packet.selected) {
        std::cout << std::format(
            "  memory {} | {:10} | source {} | {}\n",
            unit->id.value,
            kind_name(unit->kind),
            unit->source_root.value,
            unit->text);
    }
    for (const auto& omission : packet.omissions) {
        std::cout << std::format("  omitted | {}\n", omission);
    }
}

[[nodiscard]] auto canonical_memory() -> std::vector<MemoryUnit> {
    std::vector<MemoryUnit> units;
    units.reserve(7);

    const auto add = [&units](auto result) {
        assert(result);
        units.push_back(std::move(*result));
    };

    add(make_unit(
        MemoryId{1}, SourceId{11}, EvidenceKind::constraint,
        "Lia avoids caffeine at night.", 4, 0.99, 1.00,
        Interval{40, std::nullopt}, Interval{95, std::nullopt},
        true, true, true));
    add(make_unit(
        MemoryId{2}, SourceId{11}, EvidenceKind::constraint,
        "Evening drinks for Lia should be caffeine free.", 4, 0.97, 0.90,
        Interval{40, std::nullopt}, Interval{95, std::nullopt},
        true, true, true));
    add(make_unit(
        MemoryId{3}, SourceId{12}, EvidenceKind::preference,
        "Lia prefers tea without sugar.", 4, 0.84, 0.88,
        Interval{0, std::nullopt}, Interval{0, std::nullopt},
        true, true, true));
    add(make_unit(
        MemoryId{4}, SourceId{13}, EvidenceKind::outcome,
        "Mint tea worked well in a prior episode.", 4, 0.80, 0.95,
        Interval{0, std::nullopt}, Interval{90, std::nullopt},
        true, true, true));
    add(make_unit(
        MemoryId{5}, SourceId{14}, EvidenceKind::qualifier,
        "Lia drinks coffee in the morning.", 4, 0.72, 0.65,
        Interval{86, std::nullopt}, Interval{86, std::nullopt},
        true, true, true));
    add(make_unit(
        MemoryId{6}, SourceId{15}, EvidenceKind::preference,
        "Lia likes espresso.", 4, 0.95, 0.82,
        Interval{70, std::nullopt}, Interval{70, std::nullopt},
        true, false, true));
    add(make_unit(
        MemoryId{7}, SourceId{16}, EvidenceKind::constraint,
        "Lia's night restriction began on day 52.", 4, 0.94, 0.70,
        Interval{52, std::nullopt}, Interval{52, 95},
        true, true, false));

    return units;
}

} // namespace memory

int main() {
    using namespace memory;

    constexpr std::size_t budget = 12;
    const auto units = canonical_memory();
    const auto baseline = relevance_baseline(units, budget);
    const auto packet = build_packet(units, budget, 100, 100);

    print_packet("Relevance only baseline", baseline);
    print_packet("Evidence packet", packet);

    assert(baseline.cost == budget);
    assert(packet.cost == budget);
    assert(baseline.selected.size() == 3);
    assert(packet.selected.size() == 3);

    assert(baseline.selected[0]->id == MemoryId{1});
    assert(baseline.selected[1]->id == MemoryId{2});
    assert(baseline.selected[2]->id == MemoryId{6});

    assert(packet.selected[0]->kind == EvidenceKind::constraint);
    assert(packet.selected[1]->kind == EvidenceKind::preference);
    assert(packet.selected[2]->kind == EvidenceKind::outcome);
    assert(std::ranges::none_of(
        packet.selected,
        [](const MemoryUnit* unit) { return !unit->supported; }));

    const auto malformed = make_unit(
        MemoryId{8}, SourceId{17}, EvidenceKind::outcome,
        "", 0, 1.2, 0.5,
        Interval{100, 90}, Interval{100, std::nullopt},
        true, true, true);
    assert(!malformed);
    std::cout << std::format(
        "Malformed candidate | REJECT | {}\n", malformed.error());
}