// Máquina de Turing determinista de una cinta, con el formato .tm de code/formats.md, y las
// historias de cómputo de esta semana: escribirlas y comprobarlas ventana por ventana.
#pragma once

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

// δ(q, a) = (next, write, move).
struct Transition {
    std::string next;
    char write = '_';
    char move = 'R';
};

// M = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato.
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>, Transition> delta;     // δ; un par sin entrada va a reject
    std::string start;                                            // q0
    std::string accept;                                           // q_accept
    std::string reject;                                           // q_reject
};

inline bool has_state(const Tm& m, const std::string& name) {
    return std::find(m.states.begin(), m.states.end(), name) != m.states.end();
}

inline bool has_symbol(const std::vector<char>& symbols, char c) {
    return std::find(symbols.begin(), symbols.end(), c) != symbols.end();
}

// Lee una descripción en formato .tm. Solo máquinas deterministas.
inline Tm read_tm(std::istream& in) {
    Tm m;
    std::string line;
    bool in_delta = false;
    auto words = [](const std::string& text) {
        std::istringstream fields(text);
        std::vector<std::string> result;
        std::string word;
        while (fields >> word) result.push_back(word);
        return result;
    };
    auto symbols = [](const std::vector<std::string>& list, std::size_t from) {
        std::vector<char> result;
        for (std::size_t i = from; i < list.size(); ++i) {
            if (list[i].size() != 1) throw std::runtime_error("un símbolo es un solo carácter: " + list[i]);
            result.push_back(list[i][0]);
        }
        return result;
    };
    auto one = [](const std::vector<std::string>& list) {
        if (list.size() != 2) throw std::runtime_error("el campo " + list[0] + " lleva un solo estado");
        return list[1];
    };
    while (std::getline(in, line)) {
        if (!line.empty() && line[0] == '#') continue;
        const std::vector<std::string> list = words(line);
        if (list.empty()) {
            if (in_delta) break;
            continue;
        }
        if (!in_delta) {
            if (list[0] == "states:") m.states.assign(list.begin() + 1, list.end());
            else if (list[0] == "alphabet:") m.alphabet = symbols(list, 1);
            else if (list[0] == "tape:") m.tape = symbols(list, 1);
            else if (list[0] == "start:") m.start = one(list);
            else if (list[0] == "accept:") m.accept = one(list);
            else if (list[0] == "reject:") m.reject = one(list);
            else if (list[0] == "delta:") in_delta = true;
            else throw std::runtime_error("campo desconocido: " + list[0]);
            continue;
        }
        // estado lee -> destino escribe movimiento
        if (list.size() != 6 || list[2] != "->" || list[1].size() != 1 || list[4].size() != 1 ||
            (list[5] != "L" && list[5] != "R")) {
            throw std::runtime_error("transición mal escrita: " + line);
        }
        const std::pair<std::string, char> key{list[0], list[1][0]};
        if (m.delta.count(key) != 0) {
            throw std::runtime_error("dos transiciones para (" + list[0] + ", " + list[1] + "): la máquina debe ser determinista");
        }
        m.delta[key] = Transition{list[3], list[4][0], list[5][0]};
    }
    if (!has_symbol(m.tape, '_')) throw std::runtime_error("el alfabeto de la cinta debe tener el blanco _");
    if (has_symbol(m.alphabet, '_')) throw std::runtime_error("el blanco _ no puede estar en el alfabeto de entrada");
    for (char c : m.alphabet) {
        if (!has_symbol(m.tape, c)) throw std::runtime_error(std::string("el símbolo de entrada ") + c + " no está en tape:");
    }
    for (const std::string& q : {m.start, m.accept, m.reject}) {
        if (!has_state(m, q)) throw std::runtime_error("estado desconocido en start, accept o reject: " + q);
    }
    if (m.accept == m.reject) throw std::runtime_error("accept y reject deben ser estados distintos");
    for (const auto& [key, t] : m.delta) {
        if (!has_state(m, key.first) || !has_state(m, t.next)) {
            throw std::runtime_error("estado desconocido en la transición de (" + key.first + ", " + key.second + ")");
        }
        if (!has_symbol(m.tape, key.second) || !has_symbol(m.tape, t.write)) {
            throw std::runtime_error("símbolo fuera de tape: en la transición de (" + key.first + ", " + key.second + ")");
        }
    }
    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);
}

// Escribe la máquina en formato .tm.
inline void write_tm(std::ostream& out, const Tm& m) {
    out << "states:";
    for (const std::string& q : m.states) out << ' ' << q;
    out << "\nalphabet:";
    for (char c : m.alphabet) out << ' ' << c;
    out << "\ntape:";
    for (char c : m.tape) out << ' ' << c;
    out << "\nstart: " << m.start << "\naccept: " << m.accept << "\nreject: " << m.reject << "\ndelta:\n";
    // En el orden de states y de tape, para que la salida no dependa del orden del mapa.
    for (const std::string& q : m.states) {
        for (char a : m.tape) {
            const auto it = m.delta.find({q, a});
            if (it == m.delta.end()) continue;
            out << q << ' ' << a << " -> " << it->second.next << ' ' << it->second.write << ' ' << it->second.move << "\n";
        }
    }
}

// Una configuración u q v: el cabezal está sobre el primer símbolo de v. Si v es vacía, está
// sobre un blanco. No se guardan los blancos del final de la cinta.
struct Configuration {
    std::string left;    // u
    std::string state;   // q
    std::string right;   // v
};

inline Configuration initial_configuration(const Tm& m, const std::string& w) {
    for (char c : w) {
        if (!has_symbol(m.alphabet, c)) throw std::runtime_error(std::string("la entrada usa un símbolo fuera del alfabeto: ") + c);
    }
    return Configuration{"", m.start, w};
}

inline bool halted(const Tm& m, const Configuration& c) {
    return c.state == m.accept || c.state == m.reject;
}

// Un paso. Devuelve false si la máquina ya se había detenido.
inline bool step(const Tm& m, Configuration& c) {
    if (halted(m, c)) return false;
    const char a = c.right.empty() ? '_' : c.right[0];
    const auto it = m.delta.find({c.state, a});
    if (it == m.delta.end()) {
        c.state = m.reject;
        return true;
    }
    const Transition& t = it->second;
    const std::string rest = c.right.empty() ? "" : c.right.substr(1);
    c.state = t.next;
    if (t.move == 'R') {
        c.left += t.write;
        c.right = rest;
    } else if (c.left.empty()) {
        // En la primera celda, L deja el cabezal donde está.
        c.right = t.write + rest;
    } else {
        const char previous = c.left.back();
        c.left.pop_back();
        c.right = std::string(1, previous) + t.write + rest;
    }
    while (!c.right.empty() && c.right.back() == '_') c.right.pop_back();
    return true;
}

// Resultado de correr la máquina con un tope de pasos.
struct Run {
    bool halted = false;
    bool accepted = false;
    long steps = 0;
    std::vector<Configuration> configurations;   // C1, C2, …, hasta donde se llegó
};

inline Run run_tm(const Tm& m, const std::string& w, long max_steps) {
    Run run;
    Configuration c = initial_configuration(m, w);
    run.configurations.push_back(c);
    while (!halted(m, c) && run.steps < max_steps) {
        step(m, c);
        ++run.steps;
        run.configurations.push_back(c);
    }
    run.halted = halted(m, c);
    run.accepted = c.state == m.accept;
    return run;
}

// Una configuración como lista de símbolos: los de u, el estado, los de v. El estado siempre
// lleva a su derecha el símbolo que lee: si v es vacía se escribe el blanco.
using Tokens = std::vector<std::string>;

inline Tokens tokens_of(const Configuration& c) {
    Tokens result;
    for (char a : c.left) result.push_back(std::string(1, a));
    result.push_back(c.state);
    for (char a : c.right) result.push_back(std::string(1, a));
    if (c.right.empty()) result.push_back("_");
    return result;
}

// La historia C1 # C2 # … # Ck como una sola lista de símbolos. Con `alternate`, las
// configuraciones pares (C2, C4, …) van al revés.
inline Tokens history_tokens(const std::vector<Configuration>& configurations, bool alternate = false) {
    Tokens result;
    for (std::size_t i = 0; i < configurations.size(); ++i) {
        if (i > 0) result.push_back("#");
        Tokens c = tokens_of(configurations[i]);
        if (alternate && i % 2 == 1) std::reverse(c.begin(), c.end());
        result.insert(result.end(), c.begin(), c.end());
    }
    return result;
}

inline std::string join(const Tokens& tokens) {
    std::string result;
    for (std::size_t i = 0; i < tokens.size(); ++i) {
        if (i > 0) result += ' ';
        result += tokens[i];
    }
    return result;
}

inline Tokens split(const std::string& text) {
    std::istringstream fields(text);
    Tokens result;
    std::string word;
    while (fields >> word) result.push_back(word);
    return result;
}

// Comprueba que `next` sigue a `current` en un paso de M, mirando solo ventanas de tres
// símbolos. Devuelve "" si todo está bien, o una frase que dice qué ventana falla.
//
// Las dos filas se completan con blancos hasta el mismo largo y se les pone # a la izquierda.
//   - Una ventana de arriba sin estado: el símbolo del centro se copia abajo sin cambios.
//   - La ventana con el estado en el centro: los tres símbolos de abajo los fija δ.
// Entre las dos reglas queda determinada cada posición de la fila de abajo.
inline std::string check_step(const Tm& m, const Tokens& current, const Tokens& next) {
    const std::size_t width = std::max(current.size(), next.size()) + 2;
    Tokens top{"#"};
    Tokens bottom{"#"};
    top.insert(top.end(), current.begin(), current.end());
    bottom.insert(bottom.end(), next.begin(), next.end());
    top.resize(width + 1, "_");
    bottom.resize(width + 1, "_");
    auto is_state = [&m](const std::string& token) { return has_state(m, token); };
    auto show = [](const Tokens& row, std::size_t j) { return row[j - 1] + " " + row[j] + " " + row[j + 1]; };

    for (std::size_t j = 1; j < width; ++j) {
        if (is_state(top[j])) {
            const std::string& q = top[j];
            const char a = top[j + 1][0];
            const auto it = m.delta.find({q, a});
            if (q == m.accept || q == m.reject || it == m.delta.end()) {
                return "δ(" + q + ", " + top[j + 1] + ") no lleva a una configuración siguiente";
            }
            const Transition& t = it->second;
            const std::string b(1, t.write);
            Tokens expected;
            if (t.move == 'R') expected = {top[j - 1], b, t.next};
            else if (top[j - 1] == "#") expected = {"#", t.next, b};
            else expected = {t.next, top[j - 1], b};
            if (bottom[j - 1] != expected[0] || bottom[j] != expected[1] || bottom[j + 1] != expected[2]) {
                return "ventana del cabezal en la posición " + std::to_string(j) + ": arriba [" + show(top, j) +
                       "], abajo [" + show(bottom, j) + "], y δ pide [" + join(expected) + "]";
            }
        } else if (!is_state(top[j - 1]) && !is_state(top[j + 1]) && bottom[j] != top[j]) {
            return "ventana lejos del cabezal en la posición " + std::to_string(j) + ": arriba [" + show(top, j) +
                   "], abajo [" + show(bottom, j) + "], y el centro debía copiarse";
        }
    }
    return "";
}

// Comprueba que la lista de símbolos es una historia de cómputo de aceptación de M con w.
// Devuelve "" si lo es, o la razón por la que no.
inline std::string check_history(const Tm& m, const std::string& w, const Tokens& history) {
    std::vector<Tokens> configurations(1);
    for (const std::string& token : history) {
        if (token == "#") configurations.emplace_back();
        else configurations.back().push_back(token);
    }
    // 1. Cada tramo es una configuración: símbolos de la cinta y exactamente un estado.
    for (std::size_t i = 0; i < configurations.size(); ++i) {
        int state_count = 0;
        for (const std::string& token : configurations[i]) {
            if (has_state(m, token)) ++state_count;
            else if (token.size() != 1 || !has_symbol(m.tape, token[0])) {
                return "C" + std::to_string(i + 1) + ": " + token + " no es un estado ni un símbolo de la cinta";
            }
        }
        if (state_count != 1) {
            return "C" + std::to_string(i + 1) + " tiene " + std::to_string(state_count) + " estados, y debe tener uno";
        }
    }
    // 2. C1 es la configuración inicial: q0 w, con los blancos que se quiera al final.
    Tokens first = configurations[0];
    while (first.size() > 1 && first.back() == "_") first.pop_back();
    Tokens expected{m.start};
    for (char a : w) expected.push_back(std::string(1, a));
    if (first != expected) return "C1 no es la configuración inicial " + join(expected);
    // 3. Cada configuración sigue a la anterior.
    for (std::size_t i = 0; i + 1 < configurations.size(); ++i) {
        const std::string problem = check_step(m, configurations[i], configurations[i + 1]);
        if (!problem.empty()) return "de C" + std::to_string(i + 1) + " a C" + std::to_string(i + 2) + ": " + problem;
    }
    // 4. La última es de aceptación.
    const Tokens& last = configurations.back();
    if (std::find(last.begin(), last.end(), m.accept) == last.end()) {
        return "la última configuración no está en " + m.accept;
    }
    return "";
}
