// De la asignación de minisat al tableau. Recibe el caso y el resultado de minisat:
//   build/solution < casos/01.in > f.cnf
//   minisat -verb=0 f.cnf f.res
//   build/decode casos/01.in f.res
// Imprime el tableau y lo comprueba sin usar la fórmula: la primera fila es la configuración
// inicial, cada fila sale de la anterior por un paso de la máquina y alguna acepta.
#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;
}

// ¿Sale la fila `below` de la fila `above` por un paso de la máquina? Las dos filas ya son
// configuraciones: # u q v #. Se compara con cada movimiento posible desde `above`.
bool follows(const Ntm& n, const Cells& cells, const std::vector<int>& above, const std::vector<int>& below) {
    int t = static_cast<int>(above.size());
    int p = 0;  // la columna del estado, desde 0
    while (!cells.is_state(above[p])) {
        p++;
    }
    const std::string& state = cells.names[above[p]];
    if (state == n.accept) {
        return above == below;  // una configuración que acepta se repite
    }
    auto it = n.delta.find({state, cells.names[above[p + 1]][0]});
    if (it == n.delta.end()) {
        return false;
    }
    for (const Move& move : it->second) {
        std::vector<int> next = above;
        int r = cells.index(move.next);
        int b = cells.index(move.write);
        if (move.dir == 'R') {
            next[p] = b;
            next[p + 1] = r;
            if (p + 2 >= t - 1) {
                continue;  // el estado quedaría pegado a la # derecha
            }
        } else if (p == 1) {
            next[p + 1] = b;  // L en la primera celda
            next[p] = r;
        } else {
            next[p + 1] = b;
            next[p] = above[p - 1];
            next[p - 1] = r;
        }
        if (next == below) {
            return true;
        }
    }
    return false;
}

bool is_config_row(const Cells& cells, const std::vector<int>& row) {
    int t = static_cast<int>(row.size());
    if (row[0] != cells.border() || row[t - 1] != cells.border()) {
        return false;
    }
    int states = 0;
    for (int j = 1; j < t - 1; j++) {
        if (cells.is_state(row[j])) {
            states++;
            if (j == t - 2) {
                return false;
            }
        } else if (!cells.is_tape(row[j])) {
            return false;
        }
    }
    return states == 1;
}

int main(int argc, char** argv) {
    if (argc != 3) {
        std::cerr << "uso: decode caso.in resultado-de-minisat\n";
        return 2;
    }
    std::ifstream input_file(argv[1]);
    std::ifstream result_file(argv[2]);
    if (!input_file || !result_file) {
        std::cerr << "no se pudo abrir " << (input_file ? argv[2] : argv[1]) << "\n";
        return 2;
    }
    Input input = read_input(input_file);
    Cells cells = cells_of(input.n);
    int t = input.t;
    int c = cells.size();

    std::string verdict;
    result_file >> verdict;
    if (verdict == "UNSAT") {
        std::cout << "UNSAT: la fórmula no tiene ninguna asignación\n";
        return 0;
    }
    if (verdict != "SAT") {
        std::cerr << "no es un resultado de minisat\n";
        return 2;
    }
    std::vector<bool> value(static_cast<std::size_t>(t * t * c) + 1, false);
    int literal = 0;
    while (result_file >> literal && literal != 0) {
        if (literal > 0 && literal <= t * t * c) {
            value[static_cast<std::size_t>(literal)] = true;
        }
    }

    // En cada celda, los símbolos cuya variable es verdadera. Debe ser uno solo.
    std::size_t width = 1;
    for (const std::string& name : cells.names) {
        width = name.size() > width ? name.size() : width;
    }
    std::vector<std::vector<int>> table(static_cast<std::size_t>(t), std::vector<int>(static_cast<std::size_t>(t), -1));
    bool one_each = true;
    for (int i = 1; i <= t; i++) {
        std::string line;
        for (int j = 1; j <= t; j++) {
            std::string cell;
            for (int s = 0; s < c; s++) {
                if (value[static_cast<std::size_t>(cell_var(t, c, i, j, s))]) {
                    cell += (cell.empty() ? "" : "+") + cells.names[static_cast<std::size_t>(s)];
                    one_each = one_each && table[i - 1][j - 1] == -1;
                    table[i - 1][j - 1] = s;
                }
            }
            if (cell.empty()) {
                cell = "?";
                one_each = false;
            }
            line += cell;
            if (j < t) {
                line += std::string(cell.size() < width + 1 ? width + 1 - cell.size() : 1, ' ');
            }
        }
        std::cout << line << "\n";
    }
    if (!one_each) {
        std::cout << "hay celdas sin símbolo (?) o con varios (a+b): revisen el grupo 1\n";
        return 1;
    }

    // La comprobación, sin usar la fórmula.
    for (int i = 0; i < t; i++) {
        if (!is_config_row(cells, table[i])) {
            std::cout << "la fila " << i + 1 << " no es una configuración # u q v #\n";
            return 1;
        }
    }
    std::vector<int> first = {cells.border(), cells.index(input.n.start)};
    for (int j = 0; j < t - 3; j++) {
        first.push_back(cells.index(j < static_cast<int>(input.w.size()) ? input.w[static_cast<std::size_t>(j)] : '_'));
    }
    first.push_back(cells.border());
    if (table[0] != first) {
        std::cout << "la fila 1 no es la configuración inicial con w\n";
        return 1;
    }
    int accept_row = -1;
    for (int i = 0; i < t; i++) {
        for (int s : table[i]) {
            if (s == cells.index(input.n.accept) && accept_row < 0) {
                accept_row = i;
            }
        }
        if (i + 1 < t && !follows(input.n, cells, table[i], table[i + 1])) {
            std::cout << "la fila " << i + 2 << " no sale de la fila " << i + 1 << " por un paso de la máquina\n";
            return 1;
        }
    }
    if (accept_row < 0) {
        std::cout << "es una ejecución de la máquina, pero ninguna fila acepta\n";
        return 1;
    }
    std::cout << "es una ejecución de la máquina: acepta en " << accept_row << " pasos\n";
    return 0;
}
