// De 3-SAT a HAMPATH: de una fórmula en CNF sale un grafo dirigido con dos nodos s y t que
// tiene un camino hamiltoniano de s a t si y solo si la fórmula es satisfacible.
// Un rombo por variable, un nodo por cláusula y un desvío por cada literal.
#ifndef HAMPATH_H
#define HAMPATH_H

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

#include "cnf.h"

struct Digraph {
    std::vector<std::string> names;
    std::vector<std::vector<int>> out;  // listas de adyacencia
    std::vector<std::vector<int>> in;
    std::set<std::pair<int, int>> edges;

    int add_node(const std::string& name) {
        names.push_back(name);
        out.emplace_back();
        in.emplace_back();
        return static_cast<int>(names.size()) - 1;
    }
    void add_edge(int u, int v) {
        if (edges.insert({u, v}).second) {
            out[u].push_back(v);
            in[v].push_back(u);
        }
    }
    int size() const { return static_cast<int>(names.size()); }
};

// El grafo de la reducción, con los nodos que la demostración nombra.
// Con l variables y k cláusulas:
//   top[i], i = 1..l+1   la punta de arriba del rombo i; top[i+1] es también su punta de abajo
//   left[i], right[i]    los extremos de la fila del rombo i
//   row[i][0..3k]        la fila: separador, par de c1, separador, par de c2, ..., separador
//   clause[j]            el nodo de la cláusula j
struct HamInstance {
    Digraph graph;
    int source = 0;
    int target = 0;
    int num_vars = 0;
    int num_clauses = 0;
    std::vector<int> top, left, right, clause;
    std::vector<std::vector<int>> row;

    int pair_a(int i, int j) const { return row[i][3 * (j - 1) + 1]; }  // el nodo izquierdo del par de c_j
    int pair_b(int i, int j) const { return row[i][3 * (j - 1) + 2]; }  // el derecho
};

inline HamInstance build_hampath(const Cnf& f) {
    HamInstance h;
    int l = h.num_vars = f.num_vars;
    int k = h.num_clauses = static_cast<int>(f.clauses.size());
    Digraph& g = h.graph;
    h.top.assign(l + 2, -1);
    h.left.assign(l + 1, -1);
    h.right.assign(l + 1, -1);
    h.row.assign(l + 1, {});
    h.clause.assign(k + 1, -1);
    for (int i = 1; i <= l + 1; i++) {
        h.top[i] = g.add_node(i == 1 ? "s" : i == l + 1 ? "t" : "d" + std::to_string(i));
    }
    for (int i = 1; i <= l; i++) {
        std::string x = "x" + std::to_string(i);
        h.left[i] = g.add_node(x + ".izq");
        for (int p = 0; p <= 3 * k; p++) {
            int j = p / 3 + 1;
            std::string name = p % 3 == 0 ? x + ".sep" + std::to_string(p / 3)
                                          : x + ".c" + std::to_string(j) + (p % 3 == 1 ? "a" : "b");
            h.row[i].push_back(g.add_node(name));
        }
        h.right[i] = g.add_node(x + ".der");
    }
    for (int j = 1; j <= k; j++) {
        h.clause[j] = g.add_node("c" + std::to_string(j));
    }
    for (int i = 1; i <= l; i++) {
        // El rombo: de la punta de arriba a los dos extremos, y de los dos extremos a la de abajo.
        g.add_edge(h.top[i], h.left[i]);
        g.add_edge(h.top[i], h.right[i]);
        g.add_edge(h.left[i], h.top[i + 1]);
        g.add_edge(h.right[i], h.top[i + 1]);
        // La fila, en los dos sentidos.
        std::vector<int> line = {h.left[i]};
        line.insert(line.end(), h.row[i].begin(), h.row[i].end());
        line.push_back(h.right[i]);
        for (std::size_t p = 0; p + 1 < line.size(); p++) {
            g.add_edge(line[p], line[p + 1]);
            g.add_edge(line[p + 1], line[p]);
        }
    }
    // Los desvíos. x_i en c_j: se entra desde el nodo izquierdo del par y se vuelve al
    // derecho, lo que solo sirve si la fila se recorre de izquierda a derecha.
    // ¬x_i en c_j: al revés.
    for (int j = 1; j <= k; j++) {
        for (int literal : f.clauses[j - 1]) {
            int i = literal > 0 ? literal : -literal;
            if (literal > 0) {
                g.add_edge(h.pair_a(i, j), h.clause[j]);
                g.add_edge(h.clause[j], h.pair_b(i, j));
            } else {
                g.add_edge(h.pair_b(i, j), h.clause[j]);
                g.add_edge(h.clause[j], h.pair_a(i, j));
            }
        }
    }
    h.source = h.top[1];
    h.target = h.top[l + 1];
    return h;
}

// ¿Es `path` un camino hamiltoniano de s a t?
inline bool is_hamiltonian_path(const HamInstance& h, const std::vector<int>& path) {
    const Digraph& g = h.graph;
    if (static_cast<int>(path.size()) != g.size() || path.front() != h.source || path.back() != h.target) {
        return false;
    }
    std::set<int> seen(path.begin(), path.end());
    if (static_cast<int>(seen.size()) != g.size()) {
        return false;
    }
    for (std::size_t p = 0; p + 1 < path.size(); p++) {
        if (g.edges.count({path[p], path[p + 1]}) == 0) {
            return false;
        }
    }
    return true;
}

// La dirección que se demuestra completa: de una asignación que satisface la fórmula, el
// camino. El rombo i se recorre de izquierda a derecha si x_i es verdadera y de derecha a
// izquierda si es falsa; cada cláusula se visita con un desvío desde su primer literal verdadero.
inline std::vector<int> path_from_assignment(const HamInstance& h, const Cnf& f, const Assignment& value) {
    std::vector<int> chosen(h.num_clauses + 1, 0);  // la variable desde cuyo rombo se visita c_j
    for (int j = 1; j <= h.num_clauses; j++) {
        for (int literal : f.clauses[j - 1]) {
            int i = literal > 0 ? literal : -literal;
            if (chosen[j] == 0 && value[i] == (literal > 0)) {
                chosen[j] = i;
            }
        }
        if (chosen[j] == 0) {
            throw std::runtime_error("la asignación no cumple la cláusula " + std::to_string(j));
        }
    }
    std::vector<int> path;
    for (int i = 1; i <= h.num_vars; i++) {
        path.push_back(h.top[i]);
        if (value[i]) {
            path.push_back(h.left[i]);
            for (int p = 0; p <= 3 * h.num_clauses; p++) {
                path.push_back(h.row[i][p]);
                if (p % 3 == 1 && chosen[p / 3 + 1] == i) {
                    path.push_back(h.clause[p / 3 + 1]);  // a -> c_j -> b
                }
            }
            path.push_back(h.right[i]);
        } else {
            path.push_back(h.right[i]);
            for (int p = 3 * h.num_clauses; p >= 0; p--) {
                path.push_back(h.row[i][p]);
                if (p % 3 == 2 && chosen[p / 3 + 1] == i) {
                    path.push_back(h.clause[p / 3 + 1]);  // b -> c_j -> a
                }
            }
            path.push_back(h.left[i]);
        }
    }
    path.push_back(h.target);
    return path;
}

// La otra dirección, leída de un camino: x_i es verdadera si el camino pasa de la punta de
// arriba del rombo i a su extremo izquierdo.
inline Assignment assignment_from_path(const HamInstance& h, const std::vector<int>& path) {
    Assignment value(h.num_vars + 1, false);
    for (std::size_t p = 0; p + 1 < path.size(); p++) {
        for (int i = 1; i <= h.num_vars; i++) {
            if (path[p] == h.top[i] && path[p + 1] == h.left[i]) {
                value[i] = true;
            }
        }
    }
    return value;
}

// Búsqueda de un camino hamiltoniano de s a t con backtracking. Con `prune`, corta una rama
// cuando algún nodo sin visitar ya no puede quedar dentro de ningún camino; sin ella es la
// fuerza bruta pura, que solo sirve para grafos muy chicos.
struct HamSearch {
    const HamInstance& h;
    bool prune;
    std::vector<bool> visited;
    std::vector<int> path;
    long calls = 0;

    HamSearch(const HamInstance& instance, bool with_prune)
        : h(instance), prune(with_prune), visited(instance.graph.size(), false) {}

    bool hopeless(int current) const {
        const Digraph& g = h.graph;
        for (int v = 0; v < g.size(); v++) {
            if (visited[v]) {
                continue;
            }
            int entries = 0, exits = 0, last_in = -1, last_out = -1;
            for (int u : g.in[v]) {
                if (!visited[u] || u == current) {
                    entries++;
                    last_in = u;
                }
            }
            for (int u : g.out[v]) {
                if (!visited[u]) {
                    exits++;
                    last_out = u;
                }
            }
            if (entries == 0) {
                return true;  // nadie puede llegar a v
            }
            if (v != h.target && exits == 0) {
                return true;  // de v no se puede salir, y no es el final
            }
            if (v != h.target && entries == 1 && exits == 1 && last_in == last_out) {
                return true;  // se entraría y se saldría por el mismo vecino
            }
        }
        return false;
    }

    bool extend(int current) {
        calls++;
        if (static_cast<int>(path.size()) == h.graph.size()) {
            return current == h.target;
        }
        if (current == h.target || (prune && hopeless(current))) {
            return false;
        }
        for (int next : h.graph.out[current]) {
            if (!visited[next]) {
                visited[next] = true;
                path.push_back(next);
                if (extend(next)) {
                    return true;
                }
                path.pop_back();
                visited[next] = false;
            }
        }
        return false;
    }

    bool run() {
        visited[h.source] = true;
        path = {h.source};
        return extend(h.source);
    }
};

#endif
