// Verificador de cook_levin. El juez lo llama con: verificador NN.in NN.out salida
// La fórmula no es única, así que no se compara el texto. Se comprueba que:
//   1. la salida es DIMACS y declara al menos las t·t·|C| variables de las celdas;
//   2. minisat responde lo que dice NN.out: satisfacible o insatisfacible;
//   3. con cada tableau de NN.out fijado celda por celda, la fórmula se puede cumplir si el
//      tableau es una ejecución que acepta (si) y no se puede cumplir si no lo es (no);
//   4. no admite un tableau con dos símbolos en una celda, ni con una celda vacía.
// Termina con 0 si todo se cumple; si no, dice en una línea qué falló.
#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

// ------------------------------------------------------------
// La entrada: una máquina en formato .tm, la cadena w y el lado t del tableau
// ------------------------------------------------------------

struct Move {
    std::string next;  // estado al que pasa
    char write;        // símbolo que escribe
    char dir;          // 'L' o 'R'
};

// N = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato .tm.
struct Ntm {
    std::vector<std::string> states;
    std::vector<char> alphabet;
    std::vector<char> tape;
    std::map<std::pair<std::string, char>, std::vector<Move>> delta;  // varios movimientos por par
    std::string start;
    std::string accept;
    std::string reject;
};

struct Input {
    Ntm n;
    std::string w;
    int t = 0;
};

std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

Input read_input(std::istream& in) {
    Input input;
    Ntm& n = input.n;
    std::string line;
    bool in_delta = false;
    while (std::getline(in, line)) {
        if (!line.empty() && line[0] == '#') {
            continue;  // comentario
        }
        std::vector<std::string> words = split_words(line);
        if (words.empty()) {
            continue;
        }
        if (words[0] == "strings:") {
            break;
        }
        if (in_delta) {
            // estado lee -> destino escribe movimiento
            n.delta[{words[0], words[1][0]}].push_back({words[3], words[4][0], words[5][0]});
        } else if (words[0] == "states:") {
            n.states.assign(words.begin() + 1, words.end());
        } else if (words[0] == "alphabet:") {
            for (std::size_t k = 1; k < words.size(); k++) {
                n.alphabet.push_back(words[k][0]);
            }
        } else if (words[0] == "tape:") {
            for (std::size_t k = 1; k < words.size(); k++) {
                n.tape.push_back(words[k][0]);
            }
        } else if (words[0] == "start:") {
            n.start = words[1];
        } else if (words[0] == "accept:") {
            n.accept = words[1];
        } else if (words[0] == "reject:") {
            n.reject = words[1];
        } else if (words[0] == "delta:") {
            in_delta = true;
        }
    }
    std::getline(in, input.w);  // la cadena: una línea vacía es ε
    while (!input.w.empty() && (input.w.back() == '\r' || input.w.back() == ' ')) {
        input.w.pop_back();
    }
    std::string name;
    in >> name >> input.t;  // tableau: t
    return input;
}

// ------------------------------------------------------------
// Las celdas y la numeración de las variables
// ------------------------------------------------------------

// Los símbolos que puede tener una celda, numerados desde 0: primero los de la cinta, en el
// orden de tape:, después los estados, en el orden de states:, y al final #.
struct Cells {
    std::vector<std::string> names;
    int tape_count = 0;
    int state_count = 0;

    int size() const { return static_cast<int>(names.size()); }
    int border() const { return size() - 1; }
    bool is_tape(int s) const { return s < tape_count; }
    bool is_state(int s) const { return s >= tape_count && s < tape_count + state_count; }
    int index(const std::string& name) const {
        for (int s = 0; s < size(); s++) {
            if (names[s] == name) {
                return s;
            }
        }
        return -1;
    }
    int index(char symbol) const { return index(std::string(1, symbol)); }
};

Cells cells_of(const Ntm& n) {
    Cells cells;
    for (char a : n.tape) {
        cells.names.push_back(std::string(1, a));
    }
    for (const std::string& q : n.states) {
        cells.names.push_back(q);
    }
    cells.names.push_back("#");
    cells.tape_count = static_cast<int>(n.tape.size());
    cells.state_count = static_cast<int>(n.states.size());
    return cells;
}

// La variable x_{i,j,s}: "la celda de la fila i y la columna j contiene el símbolo s".
// Filas y columnas de 1 a t; s de 0 a |C| - 1. Son las variables 1, 2, ..., t·t·|C|.
int cell_var(int t, int symbols, int i, int j, int s) {
    return ((i - 1) * t + (j - 1)) * symbols + s + 1;
}

// ------------------------------------------------------------
// Lo que se espera: casos/NN.out
// ------------------------------------------------------------

// Un tableau de prueba. Si `valid`, es una ejecución de la máquina que acepta w y la fórmula
// lo tiene que admitir; si no, `reason` dice qué le falla y la fórmula lo tiene que rechazar.
struct Probe {
    bool valid = false;
    std::string reason;
    std::vector<std::vector<int>> table;
};

struct Expected {
    bool satisfiable = false;
    std::vector<Probe> probes;
};

Expected read_expected(std::istream& in, const Cells& cells, int t) {
    Expected expected;
    std::string line;
    std::getline(in, line);
    expected.satisfiable = split_words(line).at(0) == "satisfacible";
    while (std::getline(in, line)) {
        std::vector<std::string> words = split_words(line);
        if (words.empty()) {
            continue;
        }
        Probe probe;
        probe.valid = words[0] == "si";
        probe.reason = line.size() > 3 ? line.substr(3) : "";
        for (int i = 0; i < t; i++) {
            std::getline(in, line);
            std::vector<int> row;
            for (const std::string& name : split_words(line)) {
                row.push_back(cells.index(name));
            }
            probe.table.push_back(row);
        }
        expected.probes.push_back(probe);
    }
    return expected;
}

// ------------------------------------------------------------
// La fórmula entregada
// ------------------------------------------------------------

struct Submitted {
    long num_vars = 0;
    long num_clauses = 0;
    std::vector<int> literals;  // las cláusulas, cada una terminada en 0
};

const long MAX_VARS = 2000000;
const long MAX_CLAUSES = 4000000;

// Lee DIMACS. Devuelve un mensaje de error, o vacío si todo está bien.
std::string read_submitted(std::istream& in, Submitted& f) {
    std::string line;
    bool header = false;
    long clauses = 0;
    bool open = false;
    while (std::getline(in, line)) {
        std::size_t first = line.find_first_not_of(" \t\r");
        if (first == std::string::npos || line[first] == 'c') {
            continue;
        }
        std::istringstream words(line);
        if (!header) {
            std::string p, cnf, rest;
            if (!(words >> p >> cnf >> f.num_vars >> f.num_clauses) || p != "p" || cnf != "cnf" || (words >> rest)) {
                return "la primera línea debe ser: p cnf VARIABLES CLAUSULAS";
            }
            if (f.num_vars < 0 || f.num_vars > MAX_VARS || f.num_clauses < 0 || f.num_clauses > MAX_CLAUSES) {
                return "la fórmula es demasiado grande: " + std::to_string(f.num_vars) + " variables y "
                       + std::to_string(f.num_clauses) + " cláusulas (el máximo es " + std::to_string(MAX_VARS)
                       + " y " + std::to_string(MAX_CLAUSES) + ")";
            }
            header = true;
            continue;
        }
        std::string word;
        while (words >> word) {
            std::size_t digits = word[0] == '-' ? 1 : 0;
            if (word.size() == digits || word.size() > 9 || word.find_first_not_of("0123456789", digits) != std::string::npos) {
                return "no es un literal: " + word.substr(0, 20);
            }
            long literal = std::stol(word);
            if (literal > f.num_vars || -literal > f.num_vars) {
                return "el literal " + word + " usa una variable mayor que las " + std::to_string(f.num_vars)
                       + " del encabezado";
            }
            f.literals.push_back(static_cast<int>(literal));
            open = literal != 0;
            if (literal == 0 && ++clauses > f.num_clauses) {
                return "hay más cláusulas que las " + std::to_string(f.num_clauses) + " del encabezado";
            }
        }
    }
    if (!header) {
        return "falta la línea p cnf";
    }
    if (open) {
        return "la última cláusula no termina en 0";
    }
    if (clauses != f.num_clauses) {
        return "el encabezado anuncia " + std::to_string(f.num_clauses) + " cláusulas y hay " + std::to_string(clauses);
    }
    return "";
}

// ¿Es satisfacible la fórmula entregada junto con estos literales fijados? Lo decide minisat.
bool satisfiable_with(const Submitted& f, const std::vector<int>& units, const std::string& base) {
    std::string cnf_path = base + ".cnf";
    std::string result_path = base + ".res";
    {
        std::ofstream out(cnf_path);
        std::string text = "p cnf " + std::to_string(f.num_vars) + " "
                           + std::to_string(f.num_clauses + static_cast<long>(units.size())) + "\n";
        for (int literal : f.literals) {
            if (literal == 0) {
                text += "0\n";
            } else {
                text += std::to_string(literal);
                text += ' ';
            }
            if (text.size() > (1u << 16)) {
                out << text;
                text.clear();
            }
        }
        for (int literal : units) {
            text += std::to_string(literal) + " 0\n";
        }
        out << text;
    }
    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 con 20: el veredicto se lee del archivo
    std::string verdict;
    {
        std::ifstream in(result_path);
        in >> verdict;
    }
    std::remove(cnf_path.c_str());
    std::remove(result_path.c_str());
    if (verdict != "SAT" && verdict != "UNSAT") {
        std::cout << "el verificador no pudo correr minisat\n";
        std::exit(2);
    }
    return verdict == "SAT";
}

// Los literales que fijan un tableau completo: en cada celda, su símbolo sí y los demás no.
std::vector<int> units_of(const std::vector<std::vector<int>>& table, int symbols) {
    int t = static_cast<int>(table.size());
    std::vector<int> units;
    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= t; j++) {
            for (int s = 0; s < symbols; s++) {
                int x = cell_var(t, symbols, i, j, s);
                units.push_back(table[i - 1][j - 1] == s ? x : -x);
            }
        }
    }
    return units;
}

int wrong(const std::string& message) {
    std::cout << message << "\n";
    return 1;
}

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cout << "uso: verificador NN.in NN.out salida\n";
        return 2;
    }
    std::ifstream input_file(argv[1]);
    std::ifstream expected_file(argv[2]);
    std::ifstream output_file(argv[3]);
    if (!input_file || !expected_file || !output_file) {
        std::cout << "el verificador no pudo abrir sus archivos\n";
        return 2;
    }
    Input input = read_input(input_file);
    Cells cells = cells_of(input.n);
    int t = input.t;
    int c = cells.size();
    Expected expected = read_expected(expected_file, cells, t);

    // 1. La salida es DIMACS y usa la numeración del enunciado para las celdas.
    Submitted f;
    std::string error = read_submitted(output_file, f);
    if (!error.empty()) {
        bool too_large = error.rfind("la fórmula es demasiado grande", 0) == 0;
        return wrong(too_large ? error : "la salida no es una fórmula en DIMACS: " + error);
    }
    long cell_vars = static_cast<long>(t) * t * c;
    if (f.num_vars < cell_vars) {
        return wrong("el encabezado declara " + std::to_string(f.num_vars) + " variables: las de las celdas son t·t·|C| = "
                     + std::to_string(cell_vars));
    }

    // 2. La respuesta: satisfacible exactamente cuando la máquina acepta dentro del tableau.
    std::string base = std::string(argv[3]) + ".verificador";
    bool satisfiable = satisfiable_with(f, {}, base);
    if (satisfiable && !expected.satisfiable) {
        return wrong("la fórmula es satisfacible, y la máquina no acepta dentro del tableau: decodifiquen la "
                     "asignación de minisat para ver qué tableau admite");
    }
    if (!satisfiable && expected.satisfiable) {
        return wrong("la fórmula es insatisfacible, y la máquina sí acepta dentro del tableau");
    }

    // 3. Que sea satisfacible por la razón correcta: admite los tableaux que son ejecuciones
    //    que aceptan, y rechaza los que no lo son.
    int number = 0;
    for (const Probe& probe : expected.probes) {
        number++;
        bool admits = satisfiable_with(f, units_of(probe.table, c), base);
        if (probe.valid && !admits) {
            return wrong("la fórmula no admite el tableau " + std::to_string(number) + " de " + argv[2]
                         + ", que es una ejecución que acepta");
        }
        if (!probe.valid && admits) {
            return wrong("la fórmula admite el tableau " + std::to_string(number) + " de " + argv[2] + ": "
                         + probe.reason);
        }
    }
    // 4. El grupo 1, con el primer tableau válido: una celda con dos símbolos y una sin ninguno.
    for (const Probe& probe : expected.probes) {
        if (!probe.valid) {
            continue;
        }
        int corner = cell_var(t, c, t, t, 0);  // la primera variable de la celda (t, t), que contiene #
        std::vector<int> units = units_of(probe.table, c);
        for (int& literal : units) {
            literal = literal == -corner ? corner : literal;
        }
        if (satisfiable_with(f, units, base)) {
            return wrong("la fórmula admite un tableau con dos símbolos en la celda (t, t)");
        }
        units = units_of(probe.table, c);
        for (int& literal : units) {
            literal = literal == corner + c - 1 ? -literal : literal;
        }
        if (satisfiable_with(f, units, base)) {
            return wrong("la fórmula admite un tableau sin símbolo en la celda (t, t)");
        }
        break;
    }
    return 0;
}
