// La reducción de Cook-Levin, ejecutada: dada una máquina no determinista N, una entrada w
// y el lado t del tableau, escribe una fórmula en CNF que es satisfacible si y solo si N
// acepta w con una ejecución que cabe en el tableau de t × t.
#ifndef COOK_LEVIN_H
#define COOK_LEVIN_H

#include <cstddef>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

#include "cnf.h"
#include "ntm.h"
#include "tableau.h"

// La variable x_{i,j,s}: "la celda (i, j) contiene el símbolo s". Filas y columnas desde 1,
// símbolos desde 0 en el orden de Cells. Las variables de las celdas son 1, 2, ..., t·t·|C|.
inline int cell_var(std::size_t t, int symbols, std::size_t i, std::size_t j, int s) {
    return static_cast<int>(((i - 1) * t + (j - 1)) * static_cast<std::size_t>(symbols)) + s + 1;
}

// Cuántas variables y cláusulas aporta cada parte de la fórmula.
struct Counts {
    long cell_vars = 0;      // t² · |C|
    long window_vars = 0;    // una por posición de ventana y por ventana legal
    long cell_clauses = 0;   // grupo 1
    long start_clauses = 0;  // grupo 2
    long move_clauses = 0;   // grupo 3
    long accept_clauses = 0; // grupo 4
    long legal = 0;          // cantidad de ventanas legales de N
    long symbols = 0;        // |C|
};

struct TableauFormula {
    Cnf cnf;
    Counts counts;
};

// Grupo 1: cada celda tiene exactamente un símbolo.
inline void add_cell_clauses(Cnf& f, std::size_t t, int symbols) {
    for (std::size_t i = 1; i <= t; i++) {
        for (std::size_t j = 1; j <= t; j++) {
            Clause some;
            for (int s = 0; s < symbols; s++) {
                some.push_back(cell_var(t, symbols, i, j, s));
            }
            f.add(some);  // al menos uno
            for (int s = 0; s < symbols; s++) {
                for (int r = s + 1; r < symbols; r++) {
                    f.add({-cell_var(t, symbols, i, j, s), -cell_var(t, symbols, i, j, r)});  // a lo sumo uno
                }
            }
        }
    }
}

// Grupo 2: la primera fila es # q0 w ␣ ... ␣ #.
inline void add_start_clauses(Cnf& f, const Ntm& n, const Cells& cells, const std::string& w, std::size_t t) {
    Row first = row_of(cells, start_config(n, w), t);
    for (std::size_t j = 1; j <= t; j++) {
        f.add({cell_var(t, cells.size(), 1, j, first[j - 1])});
    }
}

// Grupo 3: cada ventana de 2 × 3 es una de las legales. La disyunción de conjunciones de
// la demostración se pasa a CNF con una variable nueva z por cada ventana legal:
// z implica cada una de sus seis celdas, y alguna z es verdadera.
inline void add_move_clauses(Cnf& f, const std::set<Window>& legal, const Cells& cells, std::size_t t) {
    int symbols = cells.size();
    for (std::size_t i = 1; i < t; i++) {
        for (std::size_t j = 1; j + 2 <= t; j++) {
            Clause some;
            for (const Window& window : legal) {
                int z = f.fresh();
                for (std::size_t k = 0; k < 6; k++) {
                    f.add({-z, cell_var(t, symbols, i + k / 3, j + k % 3, window[k])});
                }
                some.push_back(z);
            }
            f.add(some);
        }
    }
}

// Grupo 4: alguna celda contiene q_accept.
inline void add_accept_clause(Cnf& f, const Ntm& n, const Cells& cells, std::size_t t) {
    Clause some;
    int accept = cells.index(n.accept);
    for (std::size_t i = 1; i <= t; i++) {
        for (std::size_t j = 1; j <= t; j++) {
            some.push_back(cell_var(t, cells.size(), i, j, accept));
        }
    }
    f.add(some);
}

inline TableauFormula tableau_formula(const Ntm& n, const std::string& w, std::size_t t) {
    if (t < 4 || w.size() + 3 > t) {
        throw std::runtime_error("el tableau necesita t >= 4 y t >= |w| + 3");
    }
    Cells cells = cells_of(n);
    std::set<Window> legal = legal_windows(n);
    TableauFormula result;
    Cnf& f = result.cnf;
    Counts& counts = result.counts;
    counts.symbols = cells.size();
    counts.legal = static_cast<long>(legal.size());
    f.num_vars = static_cast<int>(t * t) * cells.size();
    counts.cell_vars = f.num_vars;

    add_cell_clauses(f, t, cells.size());
    counts.cell_clauses = static_cast<long>(f.clauses.size());
    add_start_clauses(f, n, cells, w, t);
    counts.start_clauses = static_cast<long>(f.clauses.size()) - counts.cell_clauses;
    add_move_clauses(f, legal, cells, t);
    counts.move_clauses = static_cast<long>(f.clauses.size()) - counts.cell_clauses - counts.start_clauses;
    counts.window_vars = f.num_vars - counts.cell_vars;
    add_accept_clause(f, n, cells, t);
    counts.accept_clauses = 1;
    return result;
}

// Lo que dice la cuenta de los apuntes, sin construir la fórmula. t es el lado, c = |C| y
// l la cantidad de ventanas legales.
inline Counts predicted_counts(long t, long c, long l) {
    Counts counts;
    counts.symbols = c;
    counts.legal = l;
    counts.cell_vars = t * t * c;
    counts.window_vars = (t - 1) * (t - 2) * l;
    counts.cell_clauses = t * t * (1 + c * (c - 1) / 2);
    counts.start_clauses = t;
    counts.move_clauses = (t - 1) * (t - 2) * (6 * l + 1);
    counts.accept_clauses = 1;
    return counts;
}

// De una asignación al tableau: en cada celda, el único símbolo cuya variable es verdadera.
inline Tableau decode_tableau(const Cells& cells, std::size_t t, const Assignment& value) {
    Tableau table(t, Row(t, -1));
    for (std::size_t i = 1; i <= t; i++) {
        for (std::size_t j = 1; j <= t; j++) {
            for (int s = 0; s < cells.size(); s++) {
                if (value.at(cell_var(t, cells.size(), i, j, s))) {
                    if (table[i - 1][j - 1] != -1) {
                        throw std::runtime_error("la celda (" + std::to_string(i) + ", " + std::to_string(j)
                                                 + ") tiene dos símbolos");
                    }
                    table[i - 1][j - 1] = s;
                }
            }
            if (table[i - 1][j - 1] == -1) {
                throw std::runtime_error("la celda (" + std::to_string(i) + ", " + std::to_string(j)
                                         + ") no tiene símbolo");
            }
        }
    }
    return table;
}

#endif
