// De SAT a 3-SAT: cada cláusula se reemplaza por cláusulas de exactamente tres literales,
// de tres variables distintas, con variables nuevas. La fórmula que sale no es equivalente
// a la de entrada: es satisfacible si y solo si la de entrada lo es.
#ifndef THREE_SAT_H
#define THREE_SAT_H

#include <algorithm>
#include <cstddef>
#include <vector>

#include "cnf.h"

// Quita los literales repetidos. Devuelve false si la cláusula tiene x y ¬x: siempre se
// cumple y se puede borrar.
inline bool clean_clause(Clause& clause) {
    std::sort(clause.begin(), clause.end());
    clause.erase(std::unique(clause.begin(), clause.end()), clause.end());
    for (int literal : clause) {
        if (literal > 0 && std::binary_search(clause.begin(), clause.end(), -literal)) {
            return false;
        }
    }
    return true;
}

// Agrega a `out` lo que reemplaza a una cláusula ya limpia.
inline void split_clause(const Clause& c, Cnf& out) {
    std::size_t k = c.size();
    if (k == 0) {
        // Nunca se cumple: las 8 cláusulas sobre tres variables nuevas tampoco.
        int a = out.fresh();
        int b = out.fresh();
        int d = out.fresh();
        for (int sa : {1, -1}) {
            for (int sb : {1, -1}) {
                for (int sd : {1, -1}) {
                    out.add({sa * a, sb * b, sd * d});
                }
            }
        }
    } else if (k == 1) {
        int a = out.fresh();
        int b = out.fresh();
        out.add({c[0], a, b});
        out.add({c[0], a, -b});
        out.add({c[0], -a, b});
        out.add({c[0], -a, -b});
    } else if (k == 2) {
        int a = out.fresh();
        out.add({c[0], c[1], a});
        out.add({c[0], c[1], -a});
    } else if (k == 3) {
        out.add(c);
    } else {
        // La cadena: y_j dice "el literal verdadero está más adelante".
        int y = out.fresh();
        out.add({c[0], c[1], y});
        for (std::size_t j = 2; j + 2 < k; j++) {
            int next = out.fresh();
            out.add({-y, c[j], next});
            y = next;
        }
        out.add({-y, c[k - 2], c[k - 1]});
    }
}

inline Cnf to_three_sat(const Cnf& f) {
    Cnf out;
    out.num_vars = f.num_vars;
    for (Clause clause : f.clauses) {
        if (clean_clause(clause)) {
            split_clause(clause, out);
        }
    }
    return out;
}

// ¿Tiene cada cláusula exactamente tres literales, de tres variables distintas?
inline bool is_three_sat(const Cnf& f) {
    for (const Clause& c : f.clauses) {
        if (c.size() != 3) {
            return false;
        }
        int a = c[0] < 0 ? -c[0] : c[0];
        int b = c[1] < 0 ? -c[1] : c[1];
        int d = c[2] < 0 ? -c[2] : c[2];
        if (a == b || a == d || b == d) {
            return false;
        }
    }
    return true;
}

#endif
