// El problema de correspondencia de Post (PCP): fichas, comprobación de una solución y
// búsqueda en anchura sobre el exceso entre la cadena de arriba y la de abajo.
#pragma once

#include <cstddef>
#include <istream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>

// Una ficha: una cadena arriba y otra abajo.
struct Domino {
    std::string top;
    std::string bottom;
};

// Lee una instancia: comentarios (#) y líneas vacías antes de `dominoes: k`, y después k líneas
// `arriba abajo`. Después de `dominoes:` ya no hay comentarios, porque las fichas que salen de
// una máquina de Turing usan el símbolo #.
inline std::vector<Domino> read_pcp(std::istream& in) {
    std::string line;
    int count = -1;
    while (std::getline(in, line)) {
        if (line.empty() || line[0] == '#') continue;
        std::istringstream fields(line);
        std::string name;
        fields >> name;
        if (name != "dominoes:" || !(fields >> count) || count < 1) {
            throw std::runtime_error("se esperaba `dominoes: k`, con k >= 1");
        }
        break;
    }
    if (count < 0) throw std::runtime_error("falta la línea `dominoes: k`");
    std::vector<Domino> dominoes;
    for (int i = 0; i < count; ++i) {
        Domino d;
        if (!std::getline(in, line)) throw std::runtime_error("faltan fichas");
        std::istringstream fields(line);
        if (!(fields >> d.top >> d.bottom)) {
            throw std::runtime_error("la ficha " + std::to_string(i + 1) + " no tiene dos cadenas");
        }
        dominoes.push_back(d);
    }
    return dominoes;
}

// La cadena de arriba (o la de abajo) de una secuencia de fichas. Las posiciones cuentan desde 0.
inline std::string concatenate(const std::vector<Domino>& dominoes, const std::vector<int>& sequence, bool top) {
    std::string result;
    for (int i : sequence) result += top ? dominoes.at(i).top : dominoes.at(i).bottom;
    return result;
}

// ¿Es la secuencia una solución? Debe tener al menos una ficha, y arriba y abajo se debe leer
// la misma cadena.
inline bool is_solution(const std::vector<Domino>& dominoes, const std::vector<int>& sequence) {
    if (sequence.empty()) return false;
    for (int i : sequence) {
        if (i < 0 || i >= static_cast<int>(dominoes.size())) return false;
    }
    return concatenate(dominoes, sequence, true) == concatenate(dominoes, sequence, false);
}

// El estado de la búsqueda: qué lado va adelantado y con qué cadena (el exceso).
// Se guarda en una sola cadena: 'T' o 'B' seguido del exceso.
struct Overhang {
    char side = 'T';        // 'T': arriba va adelantado; 'B': abajo
    std::string excess;     // lo que el lado adelantado tiene de más
};

// Agrega una ficha a un estado. Devuelve false si las cadenas dejan de coincidir.
inline bool extend(const Overhang& from, const Domino& d, Overhang& to) {
    // `ahead` es lo que tiene pendiente el lado adelantado después de agregar la ficha,
    // y `behind` lo que agrega el otro lado. Uno debe ser prefijo del otro.
    const std::string ahead = from.excess + (from.side == 'T' ? d.top : d.bottom);
    const std::string& behind = from.side == 'T' ? d.bottom : d.top;
    if (ahead.size() >= behind.size()) {
        if (ahead.compare(0, behind.size(), behind) != 0) return false;
        to.side = from.side;
        to.excess = ahead.substr(behind.size());
    } else {
        if (behind.compare(0, ahead.size(), ahead) != 0) return false;
        to.side = from.side == 'T' ? 'B' : 'T';
        to.excess = behind.substr(ahead.size());
    }
    return true;
}

struct PcpResult {
    bool found = false;
    std::vector<int> sequence;   // la solución, como posiciones desde 0
    bool exhausted = false;      // no quedaron estados por explorar: no hay solución de ninguna longitud
    bool gave_up = false;        // se llegó al tope de excesos guardados antes de terminar
    std::size_t visited = 0;     // excesos distintos que se alcanzaron
};

// Búsqueda en anchura sobre el exceso, hasta `bound` fichas. Si `first` no es -1, la solución
// debe empezar con esa ficha (el PCP modificado). Como recorre por niveles, la solución que
// encuentra es una de las más cortas. `max_states` es un tope de memoria: la cantidad de excesos
// distintos puede crecer exponencialmente con la profundidad.
inline PcpResult solve_pcp(const std::vector<Domino>& dominoes, int bound, int first = -1,
                           std::size_t max_states = 2000000) {
    struct Node {
        int parent;
        int domino;
        Overhang state;
    };
    PcpResult result;
    std::vector<Node> nodes;
    std::unordered_map<std::string, int> seen;
    const int count = static_cast<int>(dominoes.size());

    auto path = [&nodes](int node, int last) {
        std::vector<int> reversed{last};
        for (int at = node; at != -1; at = nodes[at].parent) reversed.push_back(nodes[at].domino);
        return std::vector<int>(reversed.rbegin(), reversed.rend());
    };

    // Nivel 0: ninguna ficha puesta, exceso vacío. No se guarda como nodo: se representa con -1.
    std::vector<int> level{-1};
    for (int depth = 1; depth <= bound; ++depth) {
        std::vector<int> next;
        for (int at : level) {
            const Overhang from = at == -1 ? Overhang{} : nodes[at].state;
            for (int i = 0; i < count; ++i) {
                if (at == -1 && first != -1 && i != first) continue;
                Overhang to;
                if (!extend(from, dominoes[i], to)) continue;
                if (to.excess.empty()) {
                    result.found = true;
                    result.sequence = path(at, i);
                    result.visited = nodes.size();
                    return result;
                }
                const std::string key = to.side + to.excess;
                if (seen.count(key) != 0) continue;
                seen[key] = static_cast<int>(nodes.size());
                next.push_back(static_cast<int>(nodes.size()));
                nodes.push_back({at, i, to});
                if (nodes.size() >= max_states) {
                    result.gave_up = true;
                    result.visited = nodes.size();
                    return result;
                }
            }
        }
        level = next;
        if (level.empty()) {
            result.exhausted = true;
            break;
        }
    }
    result.visited = nodes.size();
    return result;
}

// Búsqueda desde los dos extremos. Una solución leída de derecha a izquierda es una solución
// del conjunto con todas las cadenas invertidas. Se buscan los excesos alcanzables con a lo
// sumo `half` fichas desde el principio y, en el conjunto invertido, desde el final. Un prefijo
// que deja arriba adelantado con el exceso e se completa con un sufijo que, leído al revés,
// deja abajo adelantado con e al revés (y lo mismo cambiando arriba por abajo).
// Encuentra una solución más corta si hay alguna de a lo sumo 2·half fichas.
inline PcpResult solve_pcp_two_ends(const std::vector<Domino>& dominoes, int half) {
    struct Reached {
        int depth;
        std::string parent;   // clave del estado anterior; "" es el estado sin fichas
        int domino;
    };
    using Table = std::unordered_map<std::string, Reached>;
    const std::string solved = "!";   // clave especial: exceso vacío después de al menos una ficha

    auto reach = [&solved, half](const std::vector<Domino>& set) {
        Table table;
        std::vector<std::string> level{""};
        for (int depth = 1; depth <= half && !level.empty(); ++depth) {
            std::vector<std::string> next;
            for (const std::string& from : level) {
                const Overhang state = from.empty() ? Overhang{} : Overhang{from[0], from.substr(1)};
                for (int i = 0; i < static_cast<int>(set.size()); ++i) {
                    Overhang to;
                    if (!extend(state, set[i], to)) continue;
                    const std::string key = to.excess.empty() ? solved : to.side + to.excess;
                    if (table.count(key) != 0) continue;
                    table[key] = Reached{depth, from, i};
                    if (key != solved) next.push_back(key);
                }
            }
            level = next;
        }
        return table;
    };
    // Las fichas desde una clave hasta el estado sin fichas, de la más cercana a la más lejana.
    auto walk = [](const Table& table, std::string key) {
        std::vector<int> result;
        while (!key.empty()) {
            const Reached& r = table.at(key);
            result.push_back(r.domino);
            key = r.parent;
        }
        return result;
    };

    std::vector<Domino> reversed;
    for (const Domino& d : dominoes) {
        reversed.push_back({std::string(d.top.rbegin(), d.top.rend()), std::string(d.bottom.rbegin(), d.bottom.rend())});
    }
    const Table forward = reach(dominoes);
    const Table backward = reach(reversed);

    PcpResult result;
    result.visited = forward.size() + backward.size();
    int best = 0;
    std::string best_forward;
    std::string best_backward;
    for (const auto& [key, r] : forward) {
        int total = 0;
        std::string other;
        if (key == solved) {
            total = r.depth;
        } else {
            other = (key[0] == 'T' ? 'B' : 'T') + std::string(key.rbegin(), key.rend() - 1);
            const auto it = backward.find(other);
            if (it == backward.end()) continue;
            total = r.depth + it->second.depth;
        }
        if (best == 0 || total < best || (total == best && key < best_forward)) {
            best = total;
            best_forward = key;
            best_backward = other;
        }
    }
    if (best == 0) return result;
    result.found = true;
    const std::vector<int> prefix = walk(forward, best_forward);
    result.sequence.assign(prefix.rbegin(), prefix.rend());
    if (!best_backward.empty()) {
        const std::vector<int> suffix = walk(backward, best_backward);
        result.sequence.insert(result.sequence.end(), suffix.begin(), suffix.end());
    }
    return result;
}
