// El tableau de la demostración de Cook-Levin: una tabla de t × t celdas con una
// configuración por fila, entre dos columnas de #. Aquí están el alfabeto de las celdas,
// las ventanas legales de 2 × 3 y las comprobaciones de un tableau ya lleno.
#ifndef TABLEAU_H
#define TABLEAU_H

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

#include "ntm.h"

// ------------------------------------------------------------
// El alfabeto de las celdas: C = Γ ∪ Q ∪ {#}
// ------------------------------------------------------------

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

    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;
            }
        }
        throw std::runtime_error("no es un símbolo de celda: " + name);
    }
    int index(char symbol) const { return index(std::string(1, symbol)); }
};

inline 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;
}

// ------------------------------------------------------------
// Filas
// ------------------------------------------------------------

using Row = std::vector<int>;
using Tableau = std::vector<Row>;

// ¿Cabe la configuración en una fila de t celdas? Hacen falta las dos #, la celda del estado
// y las celdas de la cinta hasta la que lee el cabezal: el cabezal no pasa de la celda t - 3.
inline bool fits(const Config& c, std::size_t t) {
    return t >= 4 && c.tape.size() + 3 <= t;
}

// La fila # u q v #, con v completada con blancos hasta t celdas.
inline Row row_of(const Cells& cells, const Config& c, std::size_t t) {
    if (!fits(c, t)) {
        throw std::runtime_error("la configuración no cabe en una fila de " + std::to_string(t) + " celdas");
    }
    Row row;
    row.push_back(cells.border());
    for (std::size_t k = 0; k < t - 3; k++) {
        if (k == c.head) {
            row.push_back(cells.index(c.state));
        }
        row.push_back(cells.index(k < c.tape.size() ? c.tape[k] : BLANK));
    }
    row.push_back(cells.border());
    return row;
}

// ¿Es la fila una configuración: # u q v #, con exactamente un estado y v no vacía?
inline bool is_config_row(const Cells& cells, const Row& row) {
    std::size_t t = row.size();
    if (t < 4 || row[0] != cells.border() || row[t - 1] != cells.border()) {
        return false;
    }
    int states = 0;
    for (std::size_t j = 1; j + 1 < t; j++) {
        if (cells.is_state(row[j])) {
            states++;
            if (j + 2 >= t) {
                return false;  // el estado quedó pegado a la # derecha
            }
        } else if (!cells.is_tape(row[j])) {
            return false;
        }
    }
    return states == 1;
}

inline Config config_of(const Cells& cells, const Row& row) {
    if (!is_config_row(cells, row)) {
        throw std::runtime_error("la fila no es una configuración");
    }
    Config c;
    for (std::size_t j = 1; j + 1 < row.size(); j++) {
        if (cells.is_state(row[j])) {
            c.state = cells.names[row[j]];
            c.head = c.tape.size();
        } else {
            c.tape.push_back(cells.names[row[j]][0]);
        }
    }
    normalize(c);
    return c;
}

inline std::string show_row(const Cells& cells, const Row& row) {
    std::string text;
    for (std::size_t j = 0; j < row.size(); j++) {
        text += (j > 0 ? " " : "") + cells.names[row[j]];
    }
    return text;
}

// Columnas alineadas: cada celda ocupa el ancho del nombre más largo.
inline void print_tableau(std::ostream& out, const Cells& cells, const Tableau& table) {
    std::size_t width = 1;
    for (const std::string& name : cells.names) {
        width = name.size() > width ? name.size() : width;
    }
    for (const Row& row : table) {
        std::string line;
        for (std::size_t j = 0; j < row.size(); j++) {
            const std::string& name = cells.names[row[j]];
            line += name;
            if (j + 1 < row.size()) {
                line += std::string(width - name.size() + 1, ' ');
            }
        }
        out << line << "\n";
    }
}

// El tableau de una rama: una fila por configuración y, si la rama termina antes de la fila
// t, su última configuración repetida hasta llenar la tabla.
inline Tableau tableau_of(const Cells& cells, const std::vector<Config>& branch, std::size_t t) {
    if (branch.empty() || branch.size() > t) {
        throw std::runtime_error("la rama no cabe en un tableau de " + std::to_string(t) + " filas");
    }
    Tableau table;
    for (std::size_t i = 0; i < t; i++) {
        table.push_back(row_of(cells, branch[i < branch.size() ? i : branch.size() - 1], t));
    }
    return table;
}

// ------------------------------------------------------------
// Ventanas legales
// ------------------------------------------------------------

// Una ventana de 2 × 3: a1 a2 a3 arriba, b1 b2 b3 abajo.
using Window = std::array<int, 6>;

// Las ventanas legales de N, por las cuatro formas de los apuntes, según dónde está el
// estado en la fila de arriba. x, y, z son símbolos de la cinta o #, según la forma.
inline std::set<Window> legal_windows(const Ntm& n) {
    Cells cells = cells_of(n);
    int border = cells.border();
    std::vector<int> gamma;         // Γ
    std::vector<int> gamma_border;  // Γ ∪ {#}
    for (int s = 0; s < cells.tape_count; s++) {
        gamma.push_back(s);
        gamma_border.push_back(s);
    }
    gamma_border.push_back(border);
    int accept = cells.index(n.accept);
    std::set<Window> legal;

    // Las transiciones, con índices de celda: (q, a) -> (r, b, D).
    struct Rule {
        int q, a, r, b;
        char dir;
    };
    std::vector<Rule> rules;
    for (const auto& [key, list] : n.delta) {
        for (const Move& m : list) {
            rules.push_back({cells.index(key.first), cells.index(key.second), cells.index(m.next),
                             cells.index(m.write), m.dir});
        }
    }

    // Forma 1: el estado en el centro. Arriba x q a. La ventana ve todo lo que cambia.
    for (const Rule& rule : rules) {
        for (int x : gamma_border) {
            if (rule.dir == 'R') {
                legal.insert({x, rule.q, rule.a, x, rule.b, rule.r});
            } else if (x != border) {
                legal.insert({x, rule.q, rule.a, rule.r, x, rule.b});
            } else {
                legal.insert({x, rule.q, rule.a, x, rule.r, rule.b});  // L en la primera celda
            }
        }
    }
    // Forma 2: el estado a la izquierda. Arriba q a y. No se ve qué hay a la izquierda de q.
    for (const Rule& rule : rules) {
        for (int y : gamma_border) {
            if (rule.dir == 'R') {
                if (y != border) {  // el estado no puede quedar pegado a la # derecha
                    legal.insert({rule.q, rule.a, y, rule.b, rule.r, y});
                }
            } else {
                for (int x : gamma) {
                    legal.insert({rule.q, rule.a, y, x, rule.b, y});
                }
                legal.insert({rule.q, rule.a, y, rule.r, rule.b, y});  // L en la primera celda
            }
        }
    }
    // Forma 3: el estado a la derecha. Arriba z x q. No se ve el símbolo que lee q.
    for (const Rule& rule : rules) {
        for (int z : gamma_border) {
            for (int x : gamma) {
                if (rule.dir == 'R') {
                    legal.insert({z, x, rule.q, z, x, rule.b});
                } else {
                    legal.insert({z, x, rule.q, z, rule.r, x});
                }
            }
        }
    }
    // Forma 4: sin estado arriba. Arriba y1 y2 y3, con y2 en Γ. El centro se copia; una
    // esquina cambia solo si el estado está justo al lado de la ventana.
    for (int y1 : gamma_border) {
        for (int y2 : gamma) {
            for (int y3 : gamma_border) {
                if (y1 == border && y3 == border) {
                    continue;
                }
                legal.insert({y1, y2, y3, y1, y2, y3});
                for (const Rule& rule : rules) {
                    if (rule.a == y1) {  // el estado está a la izquierda de la ventana y lee y1
                        legal.insert({y1, y2, y3, rule.dir == 'R' ? rule.r : rule.b, y2, y3});
                    }
                    if (rule.dir == 'L' && y3 != border) {  // el estado llega desde la derecha
                        legal.insert({y1, y2, y3, y1, y2, rule.r});
                    }
                }
            }
        }
    }
    // Una configuración de aceptación se repite: las ventanas con q_accept arriba se copian.
    for (int x : gamma_border) {
        for (int a : gamma) {
            legal.insert({x, accept, a, x, accept, a});
            legal.insert({accept, a, x, accept, a, x});
            legal.insert({x, a, accept, x, a, accept});
        }
    }
    return legal;
}

// Las mismas ventanas, sacadas de la definición: todas las que aparecen entre dos filas
// seguidas # C # y # C' #, donde C' sale de C en un paso, o C acepta y C' = C. Recorre todas
// las filas de hasta `interior` celdas entre las #. Sirve para comprobar legal_windows.
inline std::set<Window> windows_from_steps(const Ntm& n, std::size_t interior) {
    Cells cells = cells_of(n);
    std::set<Window> found;
    for (std::size_t t = 4; t <= interior + 2; t++) {
        std::size_t tape_cells = t - 3;
        std::vector<std::size_t> digits(tape_cells, 0);
        bool more = true;
        while (more) {
            std::string tape;
            for (std::size_t d : digits) {
                tape.push_back(n.tape[d]);
            }
            for (const std::string& q : n.states) {
                for (std::size_t head = 0; head < tape_cells; head++) {
                    Config c = {q, tape, head};
                    normalize(c);
                    std::vector<Config> nexts = successors(n, c);
                    if (q == n.accept) {
                        nexts.push_back(c);
                    }
                    for (const Config& d : nexts) {
                        if (!fits(d, t)) {
                            continue;
                        }
                        Row top = row_of(cells, c, t);
                        Row bottom = row_of(cells, d, t);
                        for (std::size_t j = 0; j + 2 < t; j++) {
                            found.insert({top[j], top[j + 1], top[j + 2], bottom[j], bottom[j + 1], bottom[j + 2]});
                        }
                    }
                }
            }
            std::size_t k = 0;
            while (k < tape_cells && ++digits[k] == n.tape.size()) {
                digits[k++] = 0;
            }
            more = k < tape_cells;
        }
    }
    return found;
}

// ------------------------------------------------------------
// Comprobar un tableau lleno, grupo por grupo
// ------------------------------------------------------------

inline bool first_row_is_start(const Ntm& n, const Cells& cells, const Tableau& table, const std::string& w) {
    return table[0] == row_of(cells, start_config(n, w), table.size());
}

// Cantidad de ventanas ilegales entre filas seguidas.
inline std::size_t illegal_windows(const std::set<Window>& legal, const Tableau& table) {
    std::size_t bad = 0;
    for (std::size_t i = 0; i + 1 < table.size(); i++) {
        for (std::size_t j = 0; j + 2 < table[i].size(); j++) {
            Window w = {table[i][j], table[i][j + 1], table[i][j + 2],
                        table[i + 1][j], table[i + 1][j + 1], table[i + 1][j + 2]};
            bad += legal.count(w) == 0;
        }
    }
    return bad;
}

inline bool has_accept(const Ntm& n, const Cells& cells, const Tableau& table) {
    int accept = cells.index(n.accept);
    for (const Row& row : table) {
        for (int s : row) {
            if (s == accept) {
                return true;
            }
        }
    }
    return false;
}

// Comprobación directa, sin ventanas: cada fila es una configuración, la primera es la
// inicial con w, cada una sale de la anterior por un paso de N (o es la misma, si ya aceptó)
// y alguna acepta. Devuelve la cantidad de pasos hasta aceptar, o -1 si el tableau no es eso.
inline int accepting_steps(const Ntm& n, const Cells& cells, const Tableau& table, const std::string& w) {
    std::size_t t = table.size();
    for (const Row& row : table) {
        if (row.size() != t || !is_config_row(cells, row)) {
            return -1;
        }
    }
    if (!first_row_is_start(n, cells, table, w)) {
        return -1;
    }
    int steps = -1;
    for (std::size_t i = 0; i < t; i++) {
        Config c = config_of(cells, table[i]);
        if (c.state == n.accept && steps < 0) {
            steps = static_cast<int>(i);
        }
        if (i + 1 == t) {
            break;
        }
        Config d = config_of(cells, table[i + 1]);
        bool follows = c.state == n.accept && c == d;
        for (const Config& next : successors(n, c)) {
            follows = follows || next == d;
        }
        if (!follows) {
            return -1;
        }
    }
    return steps;
}

#endif
