// Máquina de Turing determinista de k cintas. Es la definición de una cinta con una función de
// transición que mira un símbolo por cinta:
//   δ(q, a1, ..., ak) = (r, b1, ..., bk, m1, ..., mk),  con cada mi en {L, R, S}.
// La entrada empieza en la cinta 1 y las demás empiezan en blanco. S deja el cabezal quieto.
// code/formats.md no define un formato de archivo para varias cintas, así que la máquina de
// ejemplo se arma aquí, en código.
#ifndef MULTITAPE_H
#define MULTITAPE_H

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

// El lado derecho de una transición. write y move tienen un carácter por cinta.
struct MultitapeAction {
    std::string state;
    std::string write;
    std::string move;
};

struct MultitapeTm {
    std::size_t tapes = 2;                                                 // k
    std::vector<std::string> states;                                       // Q
    std::vector<char> alphabet;                                            // Σ
    std::vector<char> tape;                                                // Γ
    std::map<std::pair<std::string, std::string>, MultitapeAction> delta;  // δ; la clave es (q, a1...ak)
    std::string start;                                                     // q0
    std::string accept;                                                    // q_accept
    std::string reject;                                                    // q_reject
};

struct MultitapeResult {
    bool accepted = false;
    long long steps = 0;
    std::size_t cells = 0;  // la mayor cantidad de celdas usadas en una cinta
};

// Ejecuta m con la entrada w hasta que se detenga. Un par sin transición lleva a q_reject.
inline MultitapeResult run_multitape(const MultitapeTm& m, const std::string& w) {
    std::vector<std::string> cells(m.tapes);
    std::vector<std::size_t> head(m.tapes, 0);
    cells[0] = w;
    std::string state = m.start;
    MultitapeResult result;
    while (state != m.accept && state != m.reject) {
        std::string read(m.tapes, '_');
        for (std::size_t i = 0; i < m.tapes; i++) {
            if (head[i] == cells[i].size()) {
                cells[i].push_back('_');
            }
            read[i] = cells[i][head[i]];
        }
        result.steps++;
        auto found = m.delta.find({state, read});
        if (found == m.delta.end()) {
            state = m.reject;
            continue;
        }
        const MultitapeAction& action = found->second;
        for (std::size_t i = 0; i < m.tapes; i++) {
            cells[i][head[i]] = action.write[i];
            if (action.move[i] == 'R') {
                head[i]++;
            } else if (action.move[i] == 'L' && head[i] > 0) {
                head[i]--;
            }
        }
        state = action.state;
    }
    result.accepted = (state == m.accept);
    for (const std::string& t : cells) {
        result.cells = t.size() > result.cells ? t.size() : result.cells;
    }
    return result;
}

// La máquina de dos cintas que decide { 0^k 1^k : k ≥ 0 } en tiempo lineal.
//   q0     pone la marca $ al inicio de la cinta 2
//   copy   copia cada 0 de la cinta 1 a la cinta 2
//   match  por cada 1 de la cinta 1 retrocede un 0 en la cinta 2
// Acepta si los unos se acaban justo cuando la cinta 2 vuelve a la marca.
inline MultitapeTm two_tape_zeros_ones() {
    MultitapeTm m;
    m.tapes = 2;
    m.states = {"q0", "copy", "match", "q_accept", "q_reject"};
    m.alphabet = {'0', '1'};
    m.tape = {'0', '1', '$', '_'};
    m.start = "q0";
    m.accept = "q_accept";
    m.reject = "q_reject";
    m.delta[{"q0", "__"}] = {"q_accept", "__", "SS"};
    m.delta[{"q0", "0_"}] = {"copy", "0$", "SR"};
    m.delta[{"copy", "0_"}] = {"copy", "00", "RR"};
    m.delta[{"copy", "1_"}] = {"match", "1_", "SL"};
    m.delta[{"match", "10"}] = {"match", "10", "RL"};
    m.delta[{"match", "_$"}] = {"q_accept", "_$", "SS"};
    return m;
}

#endif
