// De una máquina de Turing M y una entrada w a un conjunto de fichas: la reducción de A_TM al
// problema de correspondencia de Post. Primero el PCP modificado (la solución debe empezar con
// la ficha 1) y después el paso que quita esa condición.
//
// Supone, como la demostración, que M nunca intenta moverse a la izquierda desde la primera celda.
#pragma once

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

#include "pcp.h"
#include "tm.h"

struct TmDominoes {
    std::vector<Domino> dominoes;          // la ficha 1 (posición 0) es la de inicio
    std::vector<std::string> kinds;        // el tipo de cada ficha, para mostrarlas
    std::map<std::string, char> letter;    // el carácter que representa a cada estado
};

// En las fichas cada estado es un solo carácter: una letra mayúscula que la cinta no usa.
inline std::map<std::string, char> state_letters(const Tm& m) {
    for (char reserved : std::string("#*$")) {
        if (has_symbol(m.tape, reserved)) {
            throw std::runtime_error(std::string("la cinta no puede usar el símbolo ") + reserved);
        }
    }
    std::map<std::string, char> letter;
    char candidate = 'A';
    for (const std::string& q : m.states) {
        while (candidate <= 'Z' && has_symbol(m.tape, candidate)) ++candidate;
        if (candidate > 'Z') throw std::runtime_error("demasiados estados para nombrarlos con una letra");
        letter[q] = candidate;
        ++candidate;
    }
    return letter;
}

inline TmDominoes tm_to_mpcp(const Tm& m, const std::string& w) {
    TmDominoes result;
    result.letter = state_letters(m);
    auto add = [&result](const std::string& kind, const std::string& top, const std::string& bottom) {
        result.dominoes.push_back({top, bottom});
        result.kinds.push_back(kind);
    };
    auto name = [&result](const std::string& q) { return std::string(1, result.letter.at(q)); };
    const std::string accept = name(m.accept);

    // 1. Inicio: abajo queda escrita la configuración inicial. Si w es vacía, el estado lee un blanco.
    initial_configuration(m, w);   // comprueba que w usa el alfabeto de entrada
    add("inicio", "#", "#" + name(m.start) + (w.empty() ? "_" : w) + "#");

    // 2 y 3. Una ficha por cada transición hacia la derecha, y una por cada transición hacia la
    // izquierda y cada símbolo c que pueda estar a la izquierda del cabezal.
    for (const std::string& q : m.states) {
        for (char a : m.tape) {
            const auto it = m.delta.find({q, a});
            if (it == m.delta.end() || q == m.accept || q == m.reject) continue;
            const Transition& t = it->second;
            if (t.move == 'R') add("derecha", name(q) + a, t.write + name(t.next));
        }
    }
    for (const std::string& q : m.states) {
        for (char a : m.tape) {
            const auto it = m.delta.find({q, a});
            if (it == m.delta.end() || q == m.accept || q == m.reject) continue;
            const Transition& t = it->second;
            if (t.move != 'L') continue;
            for (char c : m.tape) add("izquierda", c + name(q) + a, name(t.next) + c + t.write);
        }
    }
    // 4. Copiar un símbolo de la cinta.
    for (char a : m.tape) add("copia", std::string(1, a), std::string(1, a));
    // 5. Copiar el separador, con o sin un blanco nuevo al final de la configuración.
    add("separador", "#", "#");
    add("separador", "#", "_#");
    // 6. Después de aceptar, el estado se come los símbolos vecinos.
    for (char a : m.tape) add("comer", a + accept, accept);
    for (char a : m.tape) add("comer", accept + a, accept);
    // 7. Cierre.
    add("final", accept + "##", "#");
    return result;
}

// Quita la condición de la primera ficha. De u = u1 u2 … un salen tres cadenas:
//   *u1*u2…*un,   u1*u2*…un*,   *u1*u2*…*un*.
// La instancia nueva tiene, en este orden: la ficha de inicio con asterisco antes arriba y antes
// y después abajo; todas las fichas (también la de inicio) con asterisco antes arriba y después
// abajo; y la ficha [*$ / $] para cerrar. Solo la primera puede empezar una solución.
inline std::vector<Domino> mpcp_to_pcp(const std::vector<Domino>& dominoes) {
    auto before = [](const std::string& u) {
        std::string result;
        for (char c : u) {
            result += '*';
            result += c;
        }
        return result;
    };
    auto after = [](const std::string& u) {
        std::string result;
        for (char c : u) {
            result += c;
            result += '*';
        }
        return result;
    };
    std::vector<Domino> result;
    result.push_back({before(dominoes.at(0).top), "*" + after(dominoes.at(0).bottom)});
    for (const Domino& d : dominoes) result.push_back({before(d.top), after(d.bottom)});
    result.push_back({"*$", "$"});
    return result;
}

// De la cadena de una solución, la lista de símbolos de la historia: se quitan los asteriscos
// y el cierre, y cada letra vuelve a ser el nombre de su estado.
inline Tokens decode_match(const TmDominoes& instance, const std::string& match) {
    std::map<char, std::string> state;
    for (const auto& [q, c] : instance.letter) state[c] = q;
    Tokens result;
    for (char c : match) {
        if (c == '*' || c == '$') continue;
        const auto it = state.find(c);
        result.push_back(it == state.end() ? std::string(1, c) : it->second);
    }
    return result;
}
