// Máquina de Turing 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, las configuraciones u q v, dar un paso y ejecutar con un límite
// de pasos.
//
// El modelo es el del curso: la cinta es infinita solo hacia la derecha, un movimiento L en la
// primera celda deja el cabezal donde está, y un par (estado, símbolo) sin transición lleva a
// q_reject.
//
// La lectura de campos sigue la de code/week-01/dfa.h, adaptada a los campos de una máquina.
#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 símbolo blanco, como se escribe en los archivos.
inline constexpr char BLANK = '_';

// El resultado de δ(q, a) = (r, b, D): pasar a r, escribir b, mover el cabezal hacia D.
struct Action {
    std::string state;  // r
    char write = BLANK; // b
    char move = 'R';    // D: 'L' o 'R'
};

struct Tm {
    std::vector<std::string> states;                       // Q, en el orden del archivo
    std::vector<char> alphabet;                            // Σ, el alfabeto de entrada
    std::vector<char> tape;                                // Γ, el alfabeto de la cinta
    std::map<std::pair<std::string, char>, Action> delta;  // δ : Q' × Γ → Q × Γ × {L, R}
    std::string start;                                     // q0
    std::string accept;                                    // q_accept
    std::string reject;                                    // q_reject
};

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

// Una línea de delta: "estado lee -> destino escribe movimiento".
struct Rule {
    std::string state;
    char read = BLANK;
    Action action;
};

// Lo que dice un archivo .tm, sin exigir todavía que sea determinista: una máquina no
// determinista se escribe igual, con varias líneas para el mismo par (ntm.h).
struct Description {
    std::vector<std::string> states;
    std::vector<char> alphabet;
    std::vector<char> tape;
    std::string start;
    std::string accept;
    std::string reject;
    std::vector<Rule> rules;
};

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

// Lanza std::runtime_error si la descripción no cumple la definición.
inline void check_description(const Description& d) {
    std::set<std::string> q(d.states.begin(), d.states.end());
    std::set<char> sigma(d.alphabet.begin(), d.alphabet.end());
    std::set<char> gamma(d.tape.begin(), d.tape.end());
    if (q.size() != d.states.size()) {
        throw std::runtime_error("hay un estado repetido en states");
    }
    if (sigma.size() != d.alphabet.size() || gamma.size() != d.tape.size()) {
        throw std::runtime_error("hay un símbolo repetido en alphabet o en tape");
    }
    if (gamma.count(BLANK) == 0) {
        throw std::runtime_error("el símbolo blanco _ tiene que estar en tape");
    }
    if (sigma.count(BLANK) > 0) {
        throw std::runtime_error("el símbolo blanco _ no puede estar en alphabet");
    }
    for (char a : d.alphabet) {
        if (gamma.count(a) == 0) {
            throw std::runtime_error(std::string("el símbolo ") + a + " está en alphabet y no en tape");
        }
    }
    for (const std::string* name : {&d.start, &d.accept, &d.reject}) {
        if (q.count(*name) == 0) {
            throw std::runtime_error("el estado " + *name + " no está en states");
        }
    }
    if (d.accept == d.reject) {
        throw std::runtime_error("accept y reject tienen que ser estados distintos");
    }
    for (const Rule& rule : d.rules) {
        const std::string where = "δ(" + rule.state + ", " + rule.read + ")";
        if (q.count(rule.state) == 0 || q.count(rule.action.state) == 0) {
            throw std::runtime_error(where + ": hay un estado que no está en states");
        }
        if (gamma.count(rule.read) == 0 || gamma.count(rule.action.write) == 0) {
            throw std::runtime_error(where + ": hay un símbolo que no está en tape");
        }
        if (rule.action.move != 'L' && rule.action.move != 'R') {
            throw std::runtime_error(where + ": el movimiento es L o R");
        }
        if (rule.state == d.accept || rule.state == d.reject) {
            throw std::runtime_error(where + ": de " + rule.state + " no sale ninguna transición, la máquina ya se detuvo");
        }
    }
}

// Lee una descripción completa, hasta el final de la entrada.
inline Description read_description(std::istream& in) {
    int number = 0;
    auto fail = [&number](const std::string& message) {
        throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
    };
    // Siguiente línea que no es comentario ni está vacía. Devuelve false al final.
    auto next_line = [&in, &number](std::vector<std::string>& words) {
        std::string line;
        while (std::getline(in, line)) {
            number++;
            if (!line.empty() && line[0] == '#') {
                continue;
            }
            words = split_words(line);
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    // Un campo: "nombre: valor valor ...". Devuelve los valores.
    auto field = [&next_line, &fail](const std::string& name) {
        std::vector<std::string> words;
        if (!next_line(words) || words[0] != name + ":") {
            fail("se esperaba el campo " + name + ":");
        }
        words.erase(words.begin());
        return words;
    };
    auto symbols = [&field, &fail](const std::string& name) {
        std::vector<char> result;
        for (const std::string& symbol : field(name)) {
            if (symbol.size() != 1 || symbol[0] == '#') {
                fail("un símbolo es un solo carácter distinto de #: " + symbol);
            }
            result.push_back(symbol[0]);
        }
        return result;
    };
    auto one_state = [&field, &fail](const std::string& name) {
        std::vector<std::string> words = field(name);
        if (words.size() != 1) {
            fail(name + ": lleva exactamente un estado");
        }
        return words[0];
    };

    Description d;
    d.states = field("states");
    d.alphabet = symbols("alphabet");
    d.tape = symbols("tape");
    d.start = one_state("start");
    d.accept = one_state("accept");
    d.reject = one_state("reject");
    if (!field("delta").empty()) {
        fail("después de delta: las transiciones van una por línea");
    }
    std::vector<std::string> words;
    while (next_line(words)) {
        if (words.size() != 6 || words[1].size() != 1 || words[2] != "->" || words[4].size() != 1 ||
            words[5].size() != 1) {
            fail("una transición se escribe: estado lee -> destino escribe movimiento");
        }
        d.rules.push_back({words[0], words[1][0], {words[3], words[4][0], words[5][0]}});
    }
    try {
        check_description(d);
    } catch (const std::runtime_error& error) {
        fail(error.what());
    }
    return d;
}

// Una máquina determinista: a lo sumo una línea por cada par de estado y símbolo.
inline Tm read_tm(std::istream& in) {
    Description d = read_description(in);
    Tm m;
    m.states = d.states;
    m.alphabet = d.alphabet;
    m.tape = d.tape;
    m.start = d.start;
    m.accept = d.accept;
    m.reject = d.reject;
    for (const Rule& rule : d.rules) {
        if (!m.delta.insert({{rule.state, rule.read}, rule.action}).second) {
            throw std::runtime_error("hay dos transiciones para δ(" + rule.state + ", " + rule.read +
                                     "): la máquina no es determinista");
        }
    }
    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);
    }
    try {
        return read_tm(file);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(path + ": " + error.what());
    }
}

// ------------------------------------------------------------
// Configuraciones
// ------------------------------------------------------------

// Una configuración: el estado, el contenido de la cinta y la posición del cabezal.
// cells guarda las celdas que la máquina ya visitó o que traía la entrada: todas las demás
// tienen el símbolo blanco. Así la cinta crece hacia la derecha solo cuando hace falta.
struct Config {
    std::string state;
    std::string cells;
    std::size_t head = 0;
};

// La configuración inicial con la entrada w: q0 w.
inline Config initial_config(const Tm& m, const std::string& w) {
    return {m.start, w, 0};
}

// El símbolo que está bajo el cabezal.
inline char scanned(const Config& c) {
    return c.head < c.cells.size() ? c.cells[c.head] : BLANK;
}

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

// La configuración escrita como en clase, u q v: u es lo que está a la izquierda del cabezal,
// q el estado, y v empieza en la celda del cabezal y llega hasta el último símbolo no blanco.
// Si a partir del cabezal todo es blanco, v es un solo blanco.
inline std::string to_string(const Config& c) {
    std::size_t end = c.cells.size();
    while (end > 0 && c.cells[end - 1] == BLANK) {
        end--;
    }
    if (end < c.head + 1) {
        end = c.head + 1;
    }
    std::string all = c.cells;
    all.resize(end, BLANK);
    std::string u = all.substr(0, c.head);
    std::string v = all.substr(c.head);
    return (u.empty() ? "" : u + " ") + c.state + " " + v;
}

// ------------------------------------------------------------
// Ejecutar
// ------------------------------------------------------------

// δ(q, a). Si el archivo no trae esa línea, la máquina pasa a q_reject: se toma como si la
// línea fuera "q a -> q_reject a R".
inline Action action_for(const Tm& m, const std::string& q, char a) {
    auto it = m.delta.find({q, a});
    if (it == m.delta.end()) {
        return {m.reject, a, 'R'};
    }
    return it->second;
}

// Aplica una acción a una configuración: escribe, cambia de estado y mueve el cabezal.
inline void apply(Config& c, const Action& action) {
    if (c.head >= c.cells.size()) {
        c.cells.resize(c.head + 1, BLANK);
    }
    c.cells[c.head] = action.write;
    c.state = action.state;
    if (action.move == 'R') {
        c.head++;
    } else if (c.head > 0) {
        c.head--;  // en la primera celda, L no mueve el cabezal
    }
}

// Un paso: de una configuración a la siguiente. No se llama con una configuración final.
inline void step(const Tm& m, Config& c) {
    apply(c, action_for(m, c.state, scanned(c)));
}

enum class Outcome { Accept, Reject, Limit };

struct Run {
    Outcome outcome = Outcome::Limit;
    long long steps = 0;  // pasos que dio
    Config last;          // la configuración en la que quedó
};

// Ejecuta M con la entrada w, a lo sumo limit pasos. Si después de limit pasos no llegó a
// q_accept ni a q_reject, el resultado es Limit: no se sabe si se detendría más adelante.
inline Run run(const Tm& m, const std::string& w, long long limit) {
    Run result;
    result.last = initial_config(m, w);
    while (!halted(m, result.last) && result.steps < limit) {
        step(m, result.last);
        result.steps++;
    }
    if (result.last.state == m.accept) {
        result.outcome = Outcome::Accept;
    } else if (result.last.state == m.reject) {
        result.outcome = Outcome::Reject;
    }
    return result;
}

// La secuencia de configuraciones C0, C1, …, hasta detenerse o hasta dar limit pasos.
inline std::vector<Config> trace(const Tm& m, const std::string& w, long long limit) {
    std::vector<Config> sequence = {initial_config(m, w)};
    while (!halted(m, sequence.back()) && static_cast<long long>(sequence.size()) <= limit) {
        Config next = sequence.back();
        step(m, next);
        sequence.push_back(next);
    }
    return sequence;
}

// ------------------------------------------------------------
// Cadenas en orden
// ------------------------------------------------------------

// Todas las cadenas sobre el alfabeto con longitud a lo sumo max_len, primero las más cortas
// y, entre las de igual longitud, en el orden del alfabeto. Es la función de la semana 1.
inline std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
    std::vector<std::string> result = {""};
    std::size_t first = 0;  // dónde empiezan las cadenas de la longitud anterior
    for (std::size_t len = 1; len <= max_len; len++) {
        std::size_t last = result.size();
        for (std::size_t i = first; i < last; i++) {
            for (char a : alphabet) {
                result.push_back(result[i] + a);
            }
        }
        first = last;
    }
    return result;
}

#endif
