// Máquina de Turing de k cintas, y su simulación con una sola cinta.
//
// La máquina de k cintas se ejecuta directamente con run_multi. La simulación (struct
// Simulation) trabaja sobre una única cinta y solo la toca como lo haría un cabezal: lee la
// celda donde está, escribe en ella y se mueve una celda. Cada una de esas operaciones cuenta
// como un paso, así que al final se sabe cuántos pasos da la máquina de una cinta.
//
// El formato .tm del curso describe máquinas de una cinta. La máquina de dos cintas del
// capítulo se arma en C++, en two_tape_zeros_ones().
#ifndef MULTITAPE_H
#define MULTITAPE_H

#include <cstddef>
#include <map>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "tm.h"

// ------------------------------------------------------------
// La máquina de k cintas
// ------------------------------------------------------------

// δ(q, a1…ak) = (r, b1…bk, D1…Dk). Cada movimiento es L, R o S (quedarse).
struct MultiAction {
    std::string state;
    std::string write;  // un símbolo por cinta
    std::string move;   // un movimiento por cinta
};

struct MultiTm {
    std::size_t tapes = 1;                                            // k
    std::vector<std::string> states;                                  // Q
    std::vector<char> alphabet;                                       // Σ
    std::vector<char> tape;                                           // Γ
    std::map<std::pair<std::string, std::string>, MultiAction> delta; // δ : Q' × Γ^k → Q × Γ^k × {L, R, S}^k
    std::string start;                                                // q0
    std::string accept;                                               // q_accept
    std::string reject;                                               // q_reject
};

struct MultiConfig {
    std::string state;
    std::vector<std::string> cells;  // el contenido de cada cinta
    std::vector<std::size_t> head;   // la posición de cada cabezal
};

// La entrada va en la primera cinta. Las demás empiezan en blanco.
inline MultiConfig initial_config(const MultiTm& m, const std::string& w) {
    MultiConfig c;
    c.state = m.start;
    c.cells.assign(m.tapes, "");
    c.cells[0] = w;
    c.head.assign(m.tapes, 0);
    return c;
}

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

// Los k símbolos que están bajo los cabezales.
inline std::string scanned(const MultiConfig& c) {
    std::string symbols;
    for (std::size_t i = 0; i < c.cells.size(); i++) {
        symbols += c.head[i] < c.cells[i].size() ? c.cells[i][c.head[i]] : BLANK;
    }
    return symbols;
}

// Un paso. Sin transición para lo que leen los cabezales, la máquina pasa a q_reject sin
// escribir ni moverse.
inline void step(const MultiTm& m, MultiConfig& c) {
    auto it = m.delta.find({c.state, scanned(c)});
    if (it == m.delta.end()) {
        c.state = m.reject;
        return;
    }
    const MultiAction& action = it->second;
    for (std::size_t i = 0; i < m.tapes; i++) {
        if (c.head[i] >= c.cells[i].size()) {
            c.cells[i].resize(c.head[i] + 1, BLANK);
        }
        c.cells[i][c.head[i]] = action.write[i];
        if (action.move[i] == 'R') {
            c.head[i]++;
        } else if (action.move[i] == 'L' && c.head[i] > 0) {
            c.head[i]--;
        }
    }
    c.state = action.state;
}

struct MultiRun {
    Outcome outcome = Outcome::Limit;
    long long steps = 0;
};

inline MultiRun run_multi(const MultiTm& m, const std::string& w, long long limit) {
    MultiRun result;
    MultiConfig c = initial_config(m, w);
    while (!halted(m, c) && result.steps < limit) {
        step(m, c);
        result.steps++;
    }
    if (c.state == m.accept) {
        result.outcome = Outcome::Accept;
    } else if (c.state == m.reject) {
        result.outcome = Outcome::Reject;
    }
    return result;
}

// Cada cinta en una línea, con el símbolo bajo el cabezal entre corchetes.
inline std::string to_string(const MultiConfig& c) {
    std::string text = c.state;
    for (std::size_t i = 0; i < c.cells.size(); i++) {
        std::string cells = c.cells[i];
        std::size_t end = cells.size();
        while (end > 0 && cells[end - 1] == BLANK) {
            end--;
        }
        cells.resize(end < c.head[i] + 1 ? c.head[i] + 1 : end, BLANK);
        text += "   cinta " + std::to_string(i + 1) + ": ";
        for (std::size_t j = 0; j < cells.size(); j++) {
            text += (j == c.head[i]) ? std::string("[") + cells[j] + "]" : std::string(1, cells[j]);
        }
    }
    return text;
}

// La máquina de dos cintas del capítulo. Decide { 0^n 1^n : n >= 0 } con una pasada: copia los
// ceros a la segunda cinta y después los va descontando, uno por cada 1.
//
//   q0   marca con $ el inicio de la cinta 2 (y acepta de una vez la cadena vacía)
//   q1   copia cada 0 a la cinta 2; con el primer 1, retrocede un paso en la cinta 2
//   q2   por cada 1 de la cinta 1, retrocede sobre un 0 de la cinta 2
inline MultiTm two_tape_zeros_ones() {
    MultiTm m;
    m.tapes = 2;
    m.states = {"q0", "q1", "q2", "q_accept", "q_reject"};
    m.alphabet = {'0', '1'};
    m.tape = {'0', '1', '$', BLANK};
    m.start = "q0";
    m.accept = "q_accept";
    m.reject = "q_reject";
    m.delta[{"q0", "__"}] = {"q_accept", "__", "SS"};
    m.delta[{"q0", "0_"}] = {"q1", "0$", "SR"};
    m.delta[{"q1", "0_"}] = {"q1", "00", "RR"};
    m.delta[{"q1", "1_"}] = {"q2", "1_", "SL"};
    m.delta[{"q2", "10"}] = {"q2", "10", "RL"};
    m.delta[{"q2", "_$"}] = {"q_accept", "_$", "SS"};
    return m;
}

// ------------------------------------------------------------
// Una sola cinta, usada solo como la usa un cabezal
// ------------------------------------------------------------

// Una celda de la cinta única. El alfabeto de esa cinta tiene, por cada símbolo a de Γ, el
// símbolo a y el símbolo "a con marca", además del separador #. La marca dice que ahí está
// uno de los cabezales de la máquina de k cintas.
struct Cell {
    char symbol = BLANK;
    bool mark = false;
    bool operator==(const Cell& other) const = default;
};

inline constexpr char SEPARATOR = '#';

struct OneTape {
    std::vector<Cell> cells;
    std::size_t head = 0;
    long long steps = 0;  // pasos de la máquina de una cinta

    Cell read() const { return head < cells.size() ? cells[head] : Cell{}; }

    // Un paso de máquina de Turing: escribir en la celda actual y mover el cabezal.
    void write_move(Cell c, char direction) {
        if (head >= cells.size()) {
            cells.resize(head + 1);
        }
        cells[head] = c;
        if (direction == 'R') {
            head++;
        } else if (head > 0) {
            head--;
        }
        steps++;
    }

    // Moverse sin cambiar lo escrito.
    void move(char direction) { write_move(read(), direction); }
};

inline bool is_separator(const Cell& c) {
    return c.symbol == SEPARATOR && !c.mark;
}

// La cinta única, de la primera celda al último separador: #[0]011#[_]#
inline std::string to_string(const OneTape& t) {
    std::size_t end = t.cells.size();
    while (end > 0 && t.cells[end - 1] == Cell{}) {
        end--;
    }
    std::string text;
    for (std::size_t i = 0; i < end; i++) {
        const Cell& c = t.cells[i];
        text += c.mark ? std::string("[") + c.symbol + "]" : std::string(1, c.symbol);
    }
    return text;
}

// ------------------------------------------------------------
// La simulación
// ------------------------------------------------------------

// El estado de la máquina S que simula a M. Lo que S recuerda fuera de la cinta es una
// cantidad acotada de datos (el estado de M, k símbolos, contadores hasta k + 1): cabe en
// sus estados.
struct Simulation {
    OneTape tape;
    std::string state;      // el estado de M
    long long rounds = 0;   // pasos de M ya simulados
    long long setup = 0;    // pasos de S que costó preparar la cinta
    long long length = 0;   // celdas en uso: de la primera al último separador
};

// Vuelve a la primera celda desde el último separador, contando separadores: el primero de la
// cinta es el número k + 1 que se encuentra yendo hacia la izquierda.
inline void return_to_start(OneTape& t, std::size_t k) {
    std::size_t seen = 1;
    while (seen < k + 1) {
        t.move('L');
        if (is_separator(t.read())) {
            seen++;
        }
    }
}

// Prepara la cinta: de w1 w2 … wn pasa a #[w1]w2…wn#[_]#[_]#…#, con k tramos.
inline Simulation start_simulation(const MultiTm& m, const std::string& w) {
    Simulation s;
    for (char a : w) {
        s.tape.cells.push_back({a, false});
    }
    s.state = m.start;
    OneTape& t = s.tape;
    const std::size_t k = m.tapes;

    // Correr la entrada una celda a la derecha: en cada paso se deja lo que se traía y se
    // levanta lo que había. La entrada no tiene blancos, así que el primer blanco es su final.
    Cell carried = {SEPARATOR, false};
    bool first = true;
    while (true) {
        Cell here = t.read();
        t.write_move(carried, 'R');
        if (here == Cell{}) {
            break;
        }
        carried = {here.symbol, first};
        first = false;
    }
    if (first) {
        t.write_move({BLANK, true}, 'R');  // entrada vacía: el cabezal de la cinta 1 está sobre un blanco
    }
    // Los otros k − 1 tramos, cada uno con un blanco marcado, y el último separador.
    for (std::size_t i = 1; i < k; i++) {
        t.write_move({SEPARATOR, false}, 'R');
        t.write_move({BLANK, true}, 'R');
    }
    t.write_move({SEPARATOR, false}, 'R');
    t.move('L');  // de vuelta sobre el último separador
    s.length = static_cast<long long>(t.head) + 1;
    return_to_start(t, k);
    s.setup = t.steps;
    return s;
}

// Simula un paso de M. El cabezal de S empieza y termina en la primera celda.
inline void simulate_step(const MultiTm& m, Simulation& s) {
    OneTape& t = s.tape;
    const std::size_t k = m.tapes;

    // Pasada 1, hacia la derecha: anotar el símbolo marcado de cada tramo.
    std::string seen(k, BLANK);
    std::size_t segment = 0;
    while (segment < k) {
        t.move('R');
        Cell here = t.read();
        if (is_separator(here)) {
            segment++;
        } else if (here.mark) {
            seen[segment] = here.symbol;
        }
    }

    // Ya se sabe qué hace M. Sin transición, pasa a q_reject y la simulación termina.
    auto it = m.delta.find({s.state, seen});
    if (it == m.delta.end()) {
        s.state = m.reject;
        s.rounds++;
        return_to_start(t, k);
        return;
    }
    const MultiAction& action = it->second;
    return_to_start(t, k);

    // Pasada 2, hacia la derecha: actualizar cada tramo.
    for (std::size_t i = 0; i < k; i++) {
        // Del separador que abre el tramo i hasta su celda marcada.
        do {
            t.move('R');
        } while (!t.read().mark);

        Cell written = {action.write[i], false};
        if (action.move[i] == 'S') {
            written.mark = true;
            t.write_move(written, 'R');
        } else if (action.move[i] == 'L') {
            t.write_move(written, 'L');
            if (is_separator(t.read())) {
                // El cabezal de M estaba en su primera celda: se queda ahí.
                t.move('R');
                t.write_move({action.write[i], true}, 'R');
            } else {
                t.write_move({t.read().symbol, true}, 'R');
            }
        } else {
            t.write_move(written, 'R');
            if (!is_separator(t.read())) {
                t.write_move({t.read().symbol, true}, 'R');
            } else {
                // El cabezal de M llega a una celda que este tramo todavía no tiene. Se pone ahí un
                // blanco marcado y todo lo que sigue se corre una celda a la derecha. Quedan por
                // dejar k − i separadores; el último cae en la primera celda libre de la cinta.
                Cell carried = {BLANK, true};
                std::size_t placed = 0;
                while (placed < k - i) {
                    Cell here = t.read();
                    t.write_move(carried, 'R');
                    if (is_separator(carried)) {
                        placed++;
                    }
                    carried = here;
                }
                s.length++;
                // Volver hasta el separador que cierra el tramo i: es el número k − i desde el final.
                std::size_t passed = 0;
                while (passed < k - i) {
                    t.move('L');
                    if (is_separator(t.read())) {
                        passed++;
                    }
                }
            }
        }
        // Avanzar hasta el separador que cierra el tramo i.
        while (!is_separator(t.read())) {
            t.move('R');
        }
    }
    return_to_start(t, k);
    s.state = action.state;
    s.rounds++;
}

// Lo que la cinta de S dice sobre M: los k tramos y la posición de la marca en cada uno.
// Lanza std::runtime_error si la cinta no tiene la forma #…#…#, con una marca por tramo.
inline MultiConfig decode(const MultiTm& m, const Simulation& s) {
    MultiConfig c;
    c.state = s.state;
    const std::vector<Cell>& cells = s.tape.cells;
    if (cells.empty() || !is_separator(cells[0])) {
        throw std::runtime_error("la cinta no empieza con un separador");
    }
    std::string current;
    std::size_t head = 0;
    int marks = 0;
    for (std::size_t i = 1; i < cells.size() && c.cells.size() < m.tapes; i++) {
        if (is_separator(cells[i])) {
            if (marks != 1) {
                throw std::runtime_error("un tramo no tiene exactamente una marca");
            }
            c.cells.push_back(current);
            c.head.push_back(head);
            current.clear();
            marks = 0;
        } else {
            if (cells[i].mark) {
                head = current.size();
                marks++;
            }
            current += cells[i].symbol;
        }
    }
    if (c.cells.size() != m.tapes) {
        throw std::runtime_error("la cinta no tiene k tramos");
    }
    return c;
}

// Dos configuraciones de M son la misma si coinciden el estado, los cabezales y el contenido
// de cada cinta sin contar los blancos del final.
inline bool same_config(MultiConfig a, MultiConfig b) {
    if (a.state != b.state || a.head != b.head || a.cells.size() != b.cells.size()) {
        return false;
    }
    for (std::size_t i = 0; i < a.cells.size(); i++) {
        for (std::string* cells : {&a.cells[i], &b.cells[i]}) {
            while (!cells->empty() && cells->back() == BLANK) {
                cells->pop_back();
            }
        }
        if (a.cells[i] != b.cells[i]) {
            return false;
        }
    }
    return true;
}

struct SimulationRun {
    Outcome outcome = Outcome::Limit;
    long long rounds = 0;  // pasos de M
    long long steps = 0;   // pasos de S, contando la preparación
};

inline SimulationRun run_simulation(const MultiTm& m, const std::string& w, long long limit) {
    Simulation s = start_simulation(m, w);
    while (s.state != m.accept && s.state != m.reject && s.rounds < limit) {
        simulate_step(m, s);
    }
    SimulationRun result;
    result.rounds = s.rounds;
    result.steps = s.tape.steps;
    if (s.state == m.accept) {
        result.outcome = Outcome::Accept;
    } else if (s.state == m.reject) {
        result.outcome = Outcome::Reject;
    }
    return result;
}

#endif
