// Máquina de Turing no determinista de una cinta. El struct tiene los componentes de la
// definición N = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato .tm de
// code/formats.md. Ahora δ(q, a) es un conjunto de movimientos: en el archivo, varias líneas
// con el mismo par de estado y símbolo.
// El lector sigue el esquema de code/week-01/dfa.h.
#ifndef NTM_H
#define NTM_H

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

struct Move {
    std::string next;  // estado al que pasa
    char write;        // símbolo que escribe
    char dir;          // 'L' o 'R'
};

inline bool operator==(const Move& a, const Move& b) {
    return a.next == b.next && a.write == b.write && a.dir == b.dir;
}

struct Ntm {
    std::vector<std::string> states;                                   // Q, en el orden del archivo
    std::vector<char> alphabet;                                        // Σ
    std::vector<char> tape;                                            // Γ, que contiene a Σ y a '_'
    std::map<std::pair<std::string, char>, std::vector<Move>> delta;   // δ : Q × Γ → P(Q × Γ × {L, R})
    std::string start;                                                 // q0
    std::string accept;                                                // q_accept
    std::string reject;                                                // q_reject
};

const char BLANK = '_';

// Los movimientos posibles desde (q, a). Un par sin línea no tiene ninguno: esa rama rechaza.
inline const std::vector<Move>& moves(const Ntm& n, const std::string& state, char symbol) {
    static const std::vector<Move> none;
    auto it = n.delta.find({state, symbol});
    return it == n.delta.end() ? none : it->second;
}

inline bool is_deterministic(const Ntm& n) {
    for (const auto& [key, list] : n.delta) {
        if (list.size() > 1) {
            return false;
        }
    }
    return true;
}

// ------------------------------------------------------------
// Comprobar la definición
// ------------------------------------------------------------

inline void check_ntm(const Ntm& n) {
    std::set<std::string> q(n.states.begin(), n.states.end());
    std::set<char> sigma(n.alphabet.begin(), n.alphabet.end());
    std::set<char> gamma(n.tape.begin(), n.tape.end());
    if (q.size() != n.states.size()) {
        throw std::runtime_error("hay un estado repetido en states");
    }
    if (gamma.size() != n.tape.size()) {
        throw std::runtime_error("hay un símbolo repetido en tape");
    }
    if (gamma.count(BLANK) == 0) {
        throw std::runtime_error("el símbolo blanco _ debe estar en tape");
    }
    if (sigma.count(BLANK) > 0) {
        throw std::runtime_error("el símbolo blanco _ no puede estar en alphabet");
    }
    for (char a : n.alphabet) {
        if (gamma.count(a) == 0) {
            throw std::runtime_error(std::string("el símbolo ") + a + " de alphabet no está en tape");
        }
    }
    for (const std::string& state : {n.start, n.accept, n.reject}) {
        if (q.count(state) == 0) {
            throw std::runtime_error("el estado " + state + " no está en states");
        }
    }
    if (n.accept == n.reject) {
        throw std::runtime_error("accept y reject deben ser estados distintos");
    }
    for (const std::string& state : n.states) {
        if (state.size() == 1 && gamma.count(state[0]) > 0) {
            throw std::runtime_error("el estado " + state + " se llama igual que un símbolo de la cinta");
        }
    }
    for (const auto& [key, list] : n.delta) {
        if (q.count(key.first) == 0) {
            throw std::runtime_error("transición desde " + key.first + ", que no está en states");
        }
        if (key.first == n.accept || key.first == n.reject) {
            throw std::runtime_error("transición desde " + key.first + ": la máquina ya se detuvo");
        }
        if (gamma.count(key.second) == 0) {
            throw std::runtime_error(std::string("transición que lee ") + key.second + ", que no está en tape");
        }
        for (const Move& m : list) {
            if (q.count(m.next) == 0) {
                throw std::runtime_error("transición hacia " + m.next + ", que no está en states");
            }
            if (gamma.count(m.write) == 0) {
                throw std::runtime_error(std::string("transición que escribe ") + m.write + ", que no está en tape");
            }
        }
    }
}

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

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

// Lee una descripción completa, hasta el final de la entrada.
inline Ntm read_ntm(std::istream& in) {
    int number = 0;
    auto fail = [&number](const std::string& message) {
        throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
    };
    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;
    };
    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 = [&fail](const std::vector<std::string>& words) {
        std::vector<char> list;
        for (const std::string& symbol : words) {
            if (symbol.size() != 1 || symbol[0] == '#') {
                fail("un símbolo es un solo carácter distinto de #: " + symbol);
            }
            list.push_back(symbol[0]);
        }
        return list;
    };
    auto single = [&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];
    };

    Ntm n;
    n.states = field("states");
    n.alphabet = symbols(field("alphabet"));
    n.tape = symbols(field("tape"));
    n.start = single("start");
    n.accept = single("accept");
    n.reject = single("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)) {
        bool shape = words.size() == 6 && words[1].size() == 1 && words[2] == "->" && words[4].size() == 1
                     && (words[5] == "L" || words[5] == "R");
        if (!shape) {
            fail("una transición se escribe: estado lee -> destino escribe L|R");
        }
        Move move = {words[3], words[4][0], words[5][0]};
        std::vector<Move>& list = n.delta[{words[0], words[1][0]}];
        bool repeated = false;
        for (const Move& other : list) {
            repeated = repeated || other == move;
        }
        if (!repeated) {
            list.push_back(move);
        }
    }
    try {
        check_ntm(n);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(std::string("la descripción no es una máquina de Turing: ") + error.what());
    }
    return n;
}

inline Ntm read_ntm_file(const std::string& path) {
    std::ifstream in(path);
    if (!in) {
        throw std::runtime_error("no se pudo abrir " + path);
    }
    try {
        return read_ntm(in);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(path + ": " + error.what());
    }
}

// ------------------------------------------------------------
// Configuraciones y pasos
// ------------------------------------------------------------

// Una configuración u q v: el estado, la cinta y la posición del cabezal (desde 0).
// La cinta se guarda sin los blancos del final, salvo los que hagan falta para llegar al cabezal.
struct Config {
    std::string state;
    std::string tape;
    std::size_t head = 0;
};

inline bool operator<(const Config& a, const Config& b) {
    return std::tie(a.state, a.head, a.tape) < std::tie(b.state, b.head, b.tape);
}

inline bool operator==(const Config& a, const Config& b) {
    return a.state == b.state && a.head == b.head && a.tape == b.tape;
}

inline void normalize(Config& c) {
    while (c.tape.size() > c.head + 1 && c.tape.back() == BLANK) {
        c.tape.pop_back();
    }
    while (c.tape.size() < c.head + 1) {
        c.tape.push_back(BLANK);
    }
}

inline Config start_config(const Ntm& n, const std::string& w) {
    Config c = {n.start, w, 0};
    normalize(c);
    return c;
}

// El resultado de aplicar un movimiento. En la primera celda, L deja el cabezal donde está.
inline Config apply_move(const Config& c, const Move& m) {
    Config next = c;
    next.state = m.next;
    next.tape[c.head] = m.write;
    if (m.dir == 'R') {
        next.head = c.head + 1;
    } else if (c.head > 0) {
        next.head = c.head - 1;
    }
    normalize(next);
    return next;
}

// Todas las configuraciones que siguen a c en un paso. Vacío si c ya se detuvo o si δ no
// tiene línea para lo que lee: esa rama rechaza.
inline std::vector<Config> successors(const Ntm& n, const Config& c) {
    std::vector<Config> result;
    if (c.state == n.accept || c.state == n.reject) {
        return result;
    }
    for (const Move& m : moves(n, c.state, c.tape[c.head])) {
        result.push_back(apply_move(c, m));
    }
    return result;
}

// La configuración como se escribe en clase: u q v.
inline std::string show_config(const Config& c) {
    std::string text = c.tape.substr(0, c.head);
    if (!text.empty()) {
        text += ' ';
    }
    return text + c.state + ' ' + c.tape.substr(c.head);
}

// ------------------------------------------------------------
// Recorrer el árbol de ejecuciones
// ------------------------------------------------------------

// Busca por niveles una rama que acepte w con a lo sumo max_steps pasos y sin que el cabezal
// pase de la celda max_head (desde 0). Devuelve la rama completa, desde la configuración
// inicial; vacía si no hay ninguna. Entre las que hay, devuelve una de las más cortas.
inline std::vector<Config> accepting_branch(const Ntm& n, const std::string& w, std::size_t max_steps,
                                            std::size_t max_head) {
    Config first = start_config(n, w);
    std::map<Config, Config> parent;  // de cada configuración vista, la anterior en su rama
    std::vector<Config> level = {first};
    std::set<Config> seen = {first};
    auto branch_to = [&parent, &first](Config c) {
        std::vector<Config> branch = {c};
        while (!(c == first)) {
            c = parent.at(c);
            branch.insert(branch.begin(), c);
        }
        return branch;
    };
    for (std::size_t step = 0; step <= max_steps; step++) {
        for (const Config& c : level) {
            if (c.state == n.accept) {
                return branch_to(c);
            }
        }
        std::vector<Config> next_level;
        for (const Config& c : level) {
            for (const Config& d : successors(n, c)) {
                if (d.head <= max_head && seen.insert(d).second) {
                    parent.insert({d, c});
                    next_level.push_back(d);
                }
            }
        }
        level = next_level;
    }
    return {};
}

// ¿Acepta N la cadena w con a lo sumo max_steps pasos, en alguna rama? Sin podar por
// configuraciones repetidas: recorre el árbol completo, rama por rama.
inline bool accepts_within(const Ntm& n, const Config& c, std::size_t max_steps, std::size_t max_head) {
    if (c.state == n.accept) {
        return true;
    }
    if (max_steps == 0) {
        return false;
    }
    for (const Config& d : successors(n, c)) {
        if (d.head <= max_head && accepts_within(n, d, max_steps - 1, max_head)) {
            return true;
        }
    }
    return false;
}

#endif
