// Máquina de Turing determinista de una cinta, M = (Q, Σ, Γ, δ, q0, q_accept, q_reject), en el
// formato .tm de code/formats.md, y un simulador que la recibe como dato.
//
// El simulador es la máquina universal de la clase escrita en C++: no sabe nada de ninguna
// máquina en particular, y lo único que hace es aplicar δ un paso por vez. Avanza de a un paso
// para poder cortarlo con un límite y para poder alternar dos simulaciones.
#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>

const char BLANK = '_';

// δ(q, a) = (r, b, L o R).
struct Action {
    std::string next;
    char write = BLANK;
    char move = '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>, Action> delta;  // δ; lo que falta lleva a reject
    std::string start;                                     // q0
    std::string accept;                                    // q_accept
    std::string reject;                                    // q_reject
};

inline Tm read_tm(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;
            }
            std::istringstream text(line);
            words.clear();
            std::string word;
            while (text >> word) {
                words.push_back(word);
            }
            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> result;
        for (const std::string& word : words) {
            if (word.size() != 1 || word[0] == '#') {
                fail("un símbolo es un solo carácter distinto de #: " + word);
            }
            result.push_back(word[0]);
        }
        return result;
    };
    auto one = [&fail](const std::vector<std::string>& words, const std::string& name) {
        if (words.size() != 1) {
            fail(name + ": lleva exactamente un estado");
        }
        return words[0];
    };

    Tm m;
    m.states = field("states");
    m.alphabet = symbols(field("alphabet"));
    m.tape = symbols(field("tape"));
    m.start = one(field("start"), "start");
    m.accept = one(field("accept"), "accept");
    m.reject = one(field("reject"), "reject");
    if (!field("delta").empty()) {
        fail("después de delta: las transiciones van una por línea");
    }
    std::set<std::string> q(m.states.begin(), m.states.end());
    std::set<char> gamma(m.tape.begin(), m.tape.end());
    if (gamma.count(BLANK) == 0) {
        fail("tape: debe contener el blanco _");
    }
    for (char a : m.alphabet) {
        if (gamma.count(a) == 0 || a == BLANK) {
            fail("alphabet: debe estar contenido en tape y no tener el blanco");
        }
    }
    if (q.count(m.start) == 0 || q.count(m.accept) == 0 || q.count(m.reject) == 0 || m.accept == m.reject) {
        fail("start, accept y reject deben ser estados, y accept distinto de reject");
    }
    std::vector<std::string> words;
    while (next_line(words)) {
        // estado lee -> destino escribe movimiento
        if (words.size() != 6 || words[2] != "->" || words[1].size() != 1 || words[4].size() != 1 ||
            (words[5] != "L" && words[5] != "R")) {
            fail("una transición se escribe: estado lee -> destino escribe L|R");
        }
        if (q.count(words[0]) == 0 || q.count(words[3]) == 0) {
            fail("estado desconocido en la transición");
        }
        if (gamma.count(words[1][0]) == 0 || gamma.count(words[4][0]) == 0) {
            fail("símbolo que no está en tape");
        }
        if (words[0] == m.accept || words[0] == m.reject) {
            fail("accept y reject no tienen transiciones de salida");
        }
        std::pair<std::string, char> key = {words[0], words[1][0]};
        if (m.delta.count(key) > 0) {
            fail("transición repetida: este simulador es para máquinas deterministas");
        }
        m.delta[key] = {words[3], words[4][0], words[5][0]};
    }
    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());
    }
}

// La descripción ⟨M⟩: la máquina escrita como una cadena, en el mismo formato .tm.
inline std::string encode(const Tm& m) {
    std::ostringstream out;
    out << "states:";
    for (const std::string& state : m.states) {
        out << ' ' << state;
    }
    out << "\nalphabet:";
    for (char a : m.alphabet) {
        out << ' ' << a;
    }
    out << "\ntape:";
    for (char a : m.tape) {
        out << ' ' << a;
    }
    out << "\nstart: " << m.start << "\naccept: " << m.accept << "\nreject: " << m.reject << "\ndelta:\n";
    for (const auto& [key, action] : m.delta) {
        out << key.first << ' ' << key.second << " -> " << action.next << ' ' << action.write << ' '
            << action.move << '\n';
    }
    return out.str();
}

// ------------------------------------------------------------
// Simular
// ------------------------------------------------------------

// Una configuración: estado, contenido de la cinta y posición del cabezal.
struct Config {
    std::string state;
    std::string tape;      // las celdas usadas; a su derecha todo es blanco
    std::size_t head = 0;
};

enum class Status { Running, Accepted, Rejected };

inline Config initial_config(const Tm& m, const std::string& w) {
    return {m.start, w.empty() ? std::string(1, BLANK) : w, 0};
}

inline Status status(const Tm& m, const Config& c) {
    if (c.state == m.accept) {
        return Status::Accepted;
    }
    return c.state == m.reject ? Status::Rejected : Status::Running;
}

// Un paso: aplica δ a la configuración. No hace nada si la máquina ya se detuvo.
inline void step(const Tm& m, Config& c) {
    if (status(m, c) != Status::Running) {
        return;
    }
    auto it = m.delta.find({c.state, c.tape[c.head]});
    if (it == m.delta.end()) {
        c.state = m.reject;  // un par sin transición lleva a reject
        return;
    }
    c.tape[c.head] = it->second.write;
    c.state = it->second.next;
    if (it->second.move == 'R') {
        c.head++;
        if (c.head == c.tape.size()) {
            c.tape.push_back(BLANK);
        }
    } else if (c.head > 0) {
        c.head--;  // en la primera celda, L deja el cabezal donde está
    }
}

// La configuración escrita como u q v.
inline std::string show_config(const Config& c) {
    std::string tape = c.tape;
    while (tape.size() > c.head + 1 && tape.back() == BLANK) {
        tape.pop_back();
    }
    return tape.substr(0, c.head) + " " + c.state + " " + tape.substr(c.head);
}

struct Outcome {
    Status status = Status::Running;  // Running: no se detuvo dentro del límite
    long steps = 0;
};

// Simula M con w durante a lo sumo `limit` pasos. Si la máquina se detiene antes, dice cómo.
// Si no, devuelve Running: con eso NO se sabe si M se detendría con más pasos.
inline Outcome simulate(const Tm& m, const std::string& w, long limit) {
    Config c = initial_config(m, w);
    Outcome result;
    while (status(m, c) == Status::Running && result.steps < limit) {
        step(m, c);
        result.steps++;
    }
    result.status = status(m, c);
    return result;
}

// Corre dos máquinas con la misma entrada, alternando un paso de cada una, hasta que alguna
// acepte. Devuelve 1 o 2 según cuál aceptó, o 0 si ninguna lo hizo en `limit` rondas.
// Es la máquina de la demostración "L y su complemento reconocibles implica L decidible".
struct Alternation {
    int winner = 0;
    long rounds = 0;
};

inline Alternation alternate(const Tm& m1, const Tm& m2, const std::string& w, long limit) {
    Config c1 = initial_config(m1, w);
    Config c2 = initial_config(m2, w);
    Alternation result;
    while (true) {
        if (status(m1, c1) == Status::Accepted) {
            result.winner = 1;
            return result;
        }
        if (status(m2, c2) == Status::Accepted) {
            result.winner = 2;
            return result;
        }
        if (result.rounds == limit) {
            return result;
        }
        step(m1, c1);
        step(m2, c2);
        result.rounds++;
    }
}

#endif
