// Máquina de Turing determinista de una cinta. El struct tiene los siete componentes de la
// definición M = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato .tm de
// code/formats.md. Además: leer ese formato y ejecutar la máquina contando sus pasos, que es
// lo que se mide esta semana.
#ifndef TM_H
#define TM_H

#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

// El lado derecho de una transición: δ(q, a) = (state, write, move).
struct TmAction {
    std::string state;
    char write = '_';
    char move = 'R';  // 'L' o 'R'
};

struct Tm {
    std::vector<std::string> states;                         // Q
    std::vector<char> alphabet;                              // Σ
    std::vector<char> tape;                                  // Γ, que contiene a Σ y al blanco '_'
    std::map<std::pair<std::string, char>, TmAction> delta;  // δ; un par sin entrada va a reject
    std::string start;                                       // q0
    std::string accept;                                      // q_accept
    std::string reject;                                      // q_reject
};

// ------------------------------------------------------------
// Leer el formato .tm
// ------------------------------------------------------------

// Lee una descripción en formato .tm. Lanza std::runtime_error si no describe una máquina
// determinista: un nombre desconocido, un símbolo fuera de Γ o dos líneas para el mismo par.
inline Tm read_tm(std::istream& in) {
    Tm m;
    std::string line;
    bool in_delta = false;
    std::set<std::string> known;
    std::set<char> gamma;
    while (std::getline(in, line)) {
        if (line.empty() || line[0] == '#') {
            continue;
        }
        std::istringstream words(line);
        std::string first;
        words >> first;
        if (!in_delta) {
            std::string word;
            if (first == "states:") {
                while (words >> word) {
                    m.states.push_back(word);
                    known.insert(word);
                }
            } else if (first == "alphabet:") {
                while (words >> word) {
                    m.alphabet.push_back(word[0]);
                }
            } else if (first == "tape:") {
                while (words >> word) {
                    m.tape.push_back(word[0]);
                    gamma.insert(word[0]);
                }
            } else if (first == "start:") {
                words >> m.start;
            } else if (first == "accept:") {
                words >> m.accept;
            } else if (first == "reject:") {
                words >> m.reject;
            } else if (first == "delta:") {
                in_delta = true;
            } else {
                throw std::runtime_error("campo desconocido: " + first);
            }
            continue;
        }
        // estado lee -> destino escribe movimiento
        std::string read, arrow, target, write, move;
        if (!(words >> read >> arrow >> target >> write >> move) || arrow != "->") {
            throw std::runtime_error("transición mal escrita: " + line);
        }
        if (known.count(first) == 0 || known.count(target) == 0) {
            throw std::runtime_error("estado desconocido en: " + line);
        }
        if (read.size() != 1 || write.size() != 1 || gamma.count(read[0]) == 0 || gamma.count(write[0]) == 0) {
            throw std::runtime_error("símbolo fuera del alfabeto de la cinta en: " + line);
        }
        if (move != "L" && move != "R") {
            throw std::runtime_error("el movimiento debe ser L o R en: " + line);
        }
        if (first == m.accept || first == m.reject) {
            throw std::runtime_error("una transición sale de un estado final: " + line);
        }
        if (m.delta.count({first, read[0]}) > 0) {
            throw std::runtime_error("dos transiciones para el mismo par, la máquina no es determinista: " + line);
        }
        m.delta[{first, read[0]}] = TmAction{target, write[0], move[0]};
    }
    if (known.count(m.start) == 0 || known.count(m.accept) == 0 || known.count(m.reject) == 0) {
        throw std::runtime_error("start, accept y reject deben estar en states");
    }
    if (m.accept == m.reject) {
        throw std::runtime_error("q_accept y q_reject deben ser distintos");
    }
    if (gamma.count('_') == 0) {
        throw std::runtime_error("el alfabeto de la cinta debe tener el blanco _");
    }
    for (char a : m.alphabet) {
        if (gamma.count(a) == 0 || a == '_') {
            throw std::runtime_error("el alfabeto de entrada debe estar en el de la cinta y no tener el blanco");
        }
    }
    return m;
}

inline Tm load_tm(const std::string& path) {
    std::ifstream file(path);
    if (!file) {
        throw std::runtime_error("no se pudo abrir " + path);
    }
    return read_tm(file);
}

// ------------------------------------------------------------
// Ejecutar contando pasos
// ------------------------------------------------------------

// Una configuración u q v: la cinta es uv, la máquina está en q y el cabezal en el primer
// símbolo de v. Los blancos de la derecha no se escriben.
struct TmConfiguration {
    std::string left;   // u
    std::string state;  // q
    std::string right;  // v
};

struct TmResult {
    bool halted = false;    // falso si se cortó por el límite de pasos
    bool accepted = false;  // terminó en q_accept
    long long steps = 0;    // cuántas veces se aplicó δ
    std::vector<TmConfiguration> watched;  // las configuraciones pedidas con watch
};

// Ejecuta m con la entrada w, a lo sumo max_steps pasos. Un paso es una aplicación de δ; el
// paso que entra a q_accept o a q_reject también cuenta. Un par sin transición lleva a
// q_reject sin cambiar la cinta. La cinta es infinita solo a la derecha: un movimiento L en
// la primera celda deja el cabezal donde está.
// Si watch no es vacío, guarda la configuración cada vez que la máquina entra a ese estado
// desde otro; con watch == "*", guarda todas, incluida la inicial.
inline TmResult run_tm(const Tm& m, const std::string& w, long long max_steps, const std::string& watch = "") {
    // Los estados y los símbolos se pasan a índices, para que un paso no busque nombres.
    std::map<std::string, int> state_index;
    for (std::size_t i = 0; i < m.states.size(); i++) {
        state_index[m.states[i]] = static_cast<int>(i);
    }
    struct Step {
        int state = -1;  // -1: no hay transición
        char write = '_';
        int move = 1;
    };
    std::vector<Step> table(m.states.size() * 256);
    for (const auto& [key, action] : m.delta) {
        std::size_t row = static_cast<std::size_t>(state_index.at(key.first)) * 256;
        table[row + static_cast<unsigned char>(key.second)] =
            Step{state_index.at(action.state), action.write, action.move == 'L' ? -1 : 1};
    }
    int accept = state_index.at(m.accept);
    int reject = state_index.at(m.reject);
    int watched_state = (watch.empty() || watch == "*") ? -1 : state_index.at(watch);

    std::string cells = w;
    std::size_t head = 0;
    int state = state_index.at(m.start);
    TmResult result;
    auto snapshot = [&]() {
        std::size_t last = cells.size();
        while (last > head && cells[last - 1] == '_') {
            last--;
        }
        std::string right = cells.substr(head, last - head);
        result.watched.push_back({cells.substr(0, head), m.states[static_cast<std::size_t>(state)], right});
    };
    if (watch == "*") {
        snapshot();
    }
    while (state != accept && state != reject) {
        if (result.steps >= max_steps) {
            return result;
        }
        if (head == cells.size()) {
            cells.push_back('_');
        }
        const Step& step = table[static_cast<std::size_t>(state) * 256 + static_cast<unsigned char>(cells[head])];
        result.steps++;
        int previous = state;
        if (step.state < 0) {
            state = reject;
        } else {
            cells[head] = step.write;
            state = step.state;
            if (step.move > 0) {
                head++;
            } else if (head > 0) {
                head--;
            }
        }
        if (watch == "*" || (state == watched_state && previous != state)) {
            if (head == cells.size()) {
                cells.push_back('_');
            }
            snapshot();
        }
    }
    result.halted = true;
    result.accepted = (state == accept);
    return result;
}

// La cadena 0^k 1^k.
inline std::string zeros_ones(std::size_t k) {
    return std::string(k, '0') + std::string(k, '1');
}

// ¿Está w en { 0^k 1^k : k ≥ 0 }? Decidido mirando la cadena completa, para comparar.
inline bool in_zeros_ones(const std::string& w) {
    std::size_t k = w.size() / 2;
    return w.size() % 2 == 0 && w == zeros_ones(k);
}

// Todas las cadenas binarias de longitud exactamente n, en orden.
inline std::vector<std::string> binary_strings(std::size_t n) {
    std::vector<std::string> all;
    for (unsigned long bits = 0; bits < (1UL << n); bits++) {
        std::string w(n, '0');
        for (std::size_t i = 0; i < n; i++) {
            if ((bits >> (n - 1 - i)) & 1UL) {
                w[i] = '1';
            }
        }
        all.push_back(w);
    }
    return all;
}

#endif
