// Fórmulas en CNF, con los literales de DIMACS: la variable k es el entero k y su negación
// es -k. Leer y escribir DIMACS, evaluar, resolver por fuerza bruta y llamar a minisat.
#ifndef CNF_H
#define CNF_H

#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <istream>
#include <ostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

using Clause = std::vector<int>;

struct Cnf {
    int num_vars = 0;
    std::vector<Clause> clauses;

    int fresh() { return ++num_vars; }  // una variable nueva
    void add(const Clause& clause) { clauses.push_back(clause); }
};

inline void write_dimacs(std::ostream& out, const Cnf& f) {
    std::string text = "p cnf " + std::to_string(f.num_vars) + " " + std::to_string(f.clauses.size()) + "\n";
    for (const Clause& clause : f.clauses) {
        for (int literal : clause) {
            text += std::to_string(literal);
            text += ' ';
        }
        text += "0\n";
        if (text.size() > (1u << 16)) {
            out << text;
            text.clear();
        }
    }
    out << text;
}

inline Cnf read_dimacs(std::istream& in) {
    Cnf f;
    std::string line;
    long expected = -1;
    Clause clause;
    while (std::getline(in, line)) {
        if (line.empty() || line[0] == 'c') {
            continue;
        }
        std::istringstream words(line);
        if (line[0] == 'p') {
            std::string p, cnf;
            if (!(words >> p >> cnf >> f.num_vars >> expected) || cnf != "cnf") {
                throw std::runtime_error("encabezado DIMACS mal escrito: " + line);
            }
            continue;
        }
        if (expected < 0) {
            throw std::runtime_error("falta la línea p cnf");
        }
        int literal = 0;
        while (words >> literal) {
            if (literal == 0) {
                f.clauses.push_back(clause);
                clause.clear();
            } else if (literal > f.num_vars || -literal > f.num_vars) {
                throw std::runtime_error("literal fuera de rango: " + std::to_string(literal));
            } else {
                clause.push_back(literal);
            }
        }
    }
    if (!clause.empty()) {
        throw std::runtime_error("la última cláusula no termina en 0");
    }
    if (expected != static_cast<long>(f.clauses.size())) {
        throw std::runtime_error("el encabezado anuncia " + std::to_string(expected) + " cláusulas y hay "
                                 + std::to_string(f.clauses.size()));
    }
    return f;
}

// Una asignación: value[k] es el valor de la variable k. value[0] no se usa.
using Assignment = std::vector<bool>;

inline bool satisfies(const Cnf& f, const Assignment& value) {
    for (const Clause& clause : f.clauses) {
        bool some = false;
        for (int literal : clause) {
            some = some || (literal > 0 ? value[literal] : !value[-literal]);
        }
        if (!some) {
            return false;
        }
    }
    return true;
}

// Prueba las 2^n asignaciones. Solo para fórmulas con pocas variables.
inline bool brute_force_sat(const Cnf& f, Assignment* model = nullptr) {
    if (f.num_vars > 24) {
        throw std::runtime_error("demasiadas variables para la fuerza bruta");
    }
    Assignment value(f.num_vars + 1, false);
    for (unsigned long mask = 0; mask < (1ul << f.num_vars); mask++) {
        for (int k = 1; k <= f.num_vars; k++) {
            value[k] = (mask >> (k - 1)) & 1;
        }
        if (satisfies(f, value)) {
            if (model != nullptr) {
                *model = value;
            }
            return true;
        }
    }
    return false;
}

// Lo que minisat deja en su archivo de resultado: "SAT" y la asignación, o "UNSAT".
// Devuelve true si es satisfacible, y en ese caso llena model.
inline bool read_minisat_result(std::istream& in, int num_vars, Assignment* model) {
    std::string verdict;
    if (!(in >> verdict) || (verdict != "SAT" && verdict != "UNSAT")) {
        throw std::runtime_error("no es un resultado de minisat");
    }
    if (verdict == "UNSAT") {
        return false;
    }
    Assignment value(num_vars + 1, false);
    int literal = 0;
    while (in >> literal && literal != 0) {
        int k = literal > 0 ? literal : -literal;
        if (k <= num_vars) {
            value[k] = literal > 0;
        }
    }
    if (model != nullptr) {
        *model = value;
    }
    return true;
}

// Escribe la fórmula en `base`.cnf, corre minisat y lee `base`.res.
inline bool minisat_sat(const Cnf& f, const std::string& base, Assignment* model = nullptr) {
    std::string cnf_path = base + ".cnf";
    std::string result_path = base + ".res";
    {
        std::ofstream out(cnf_path);
        if (!out) {
            throw std::runtime_error("no se pudo escribir " + cnf_path);
        }
        write_dimacs(out, f);
    }
    std::remove(result_path.c_str());
    std::string command = "minisat -verb=0 " + cnf_path + " " + result_path + " > /dev/null 2>&1";
    int status = std::system(command.c_str());
    (void)status;  // minisat termina con 10 o 20: el veredicto se lee del archivo
    std::ifstream in(result_path);
    if (!in) {
        throw std::runtime_error("minisat no dejó resultado; ¿está instalado?");
    }
    return read_minisat_result(in, f.num_vars, model);
}

inline std::string show_literal(int literal) {
    return (literal < 0 ? "¬x" : "x") + std::to_string(literal < 0 ? -literal : literal);
}

inline std::string show_clause(const Clause& clause) {
    std::string text = "(";
    for (std::size_t k = 0; k < clause.size(); k++) {
        text += (k > 0 ? " ∨ " : "") + show_literal(clause[k]);
    }
    return text + ")";
}

#endif
