// Menú con precios en soles: ¿cuántas combinaciones de platos caben en el presupuesto?
#include <stdio.h>

#define COUNT_OF_PRICES 12

// Sin poda: recorre todo el árbol y solo revisa el total en las hojas.
static long count_all(const int *prices, int n, int index, int total, int budget, long *nodes) {
    (*nodes)++;
    if (index == n) {
        return total <= budget;
    }
    return count_all(prices, n, index + 1, total + prices[index], budget, nodes)
         + count_all(prices, n, index + 1, total, budget, nodes);
}

// Con poda: si ya se pasó, ningún plato más lo arregla, porque los precios son positivos.
static long count_pruned(const int *prices, int n, int index, int total, int budget, long *nodes) {
    (*nodes)++;
    if (total > budget) {
        return 0;
    }
    if (index == n) {
        return 1;
    }
    return count_pruned(prices, n, index + 1, total + prices[index], budget, nodes)
         + count_pruned(prices, n, index + 1, total, budget, nodes);
}

int main(void) {
    int prices[COUNT_OF_PRICES] = {12, 7, 18, 5, 9, 15, 4, 11, 6, 14, 8, 10};
    int budget = 30;
    long nodes_all = 0;
    long nodes_pruned = 0;

    long all = count_all(prices, COUNT_OF_PRICES, 0, 0, budget, &nodes_all);
    long pruned = count_pruned(prices, COUNT_OF_PRICES, 0, 0, budget, &nodes_pruned);
    printf("sin poda: %ld combinaciones, %ld nodos\n", all, nodes_all);
    printf("con poda: %ld combinaciones, %ld nodos\n", pruned, nodes_pruned);
    return 0;
}

// Cuenta de verdad las hojas y los nodos de los dos árboles, sin escribir cada resultado.
#include <stdio.h>

#define MAX_ITEMS 16

typedef struct {
    long leaves;
    long nodes;
} Count;

static void subsets(int n, int index, Count *count) {
    count->nodes++;
    if (index == n) {
        count->leaves++;
        return;
    }
    subsets(n, index + 1, count);
    subsets(n, index + 1, count);
}

static void permutations(int n, int *used, int depth, Count *count) {
    count->nodes++;
    if (depth == n) {
        count->leaves++;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = 1;
            permutations(n, used, depth + 1, count);
            used[i] = 0;
        }
    }
}

int main(void) {
    printf(" n | subconjuntos    nodos | permutaciones      nodos\n");
    for (int n = 1; n <= 10; n++) {
        Count sub = {0, 0};
        Count perm = {0, 0};
        int used[MAX_ITEMS] = {0};

        subsets(n, 0, &sub);
        permutations(n, used, 0, &perm);
        printf("%2d | %12ld %8ld | %13ld %10ld\n", n, sub.leaves, sub.nodes, perm.leaves, perm.nodes);
    }
    return 0;
}

// Permutaciones de "abc": en cada posición se elige un elemento que no se haya usado.
#include <stdio.h>
#include <string.h>

#define MAX_ITEMS 16

static void permutations(const char *items, int n, char *current, int *used, int depth,
                         long *nodes) {
    (*nodes)++;
    if (depth == n) {
        current[n] = '\0';
        printf("%s\n", current);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = 1;                                                // elegir
            current[depth] = items[i];
            permutations(items, n, current, used, depth + 1, nodes);    // explorar
            used[i] = 0;                                                // deshacer
        }
    }
}

int main(void) {
    const char *items = "abc";
    char current[MAX_ITEMS + 1];
    int used[MAX_ITEMS] = {0};
    long nodes = 0;

    permutations(items, (int) strlen(items), current, used, 0, &nodes);
    printf("nodos: %ld\n", nodes);
    return 0;
}

// N reinas, hasta la primera solución: el retorno avisa que ya no hay que seguir buscando.
#include <stdio.h>

#define MAX_N 16

typedef struct {
    int n;
    int column_of_row[MAX_N];
    int column_used[MAX_N];
    int down_used[2 * MAX_N - 1];
    int up_used[2 * MAX_N - 1];
    long nodes;
} Queens;

static int can_place(const Queens *q, int row, int col) {
    return !q->column_used[col]
        && !q->down_used[row - col + q->n - 1]
        && !q->up_used[row + col];
}

static void mark(Queens *q, int row, int col, int value) {
    q->column_used[col] = value;
    q->down_used[row - col + q->n - 1] = value;
    q->up_used[row + col] = value;
}

// Devuelve 1 si encontró una solución, y la deja en column_of_row.
static int search(Queens *q, int row) {
    q->nodes++;
    if (row == q->n) {
        return 1;
    }
    for (int col = 0; col < q->n; col++) {
        if (can_place(q, row, col)) {
            mark(q, row, col, 1);
            q->column_of_row[row] = col;
            if (search(q, row + 1)) {
                return 1;
            }
            mark(q, row, col, 0);
        }
    }
    return 0;
}

static void print_board(const Queens *q) {
    for (int row = 0; row < q->n; row++) {
        for (int col = 0; col < q->n; col++) {
            if (q->column_of_row[row] == col) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
}

int main(int argc, char *argv[]) {
    int n;
    if (argc != 2 || sscanf(argv[1], "%d", &n) != 1 || n < 1 || n > MAX_N) {
        fprintf(stderr, "uso: %s n, con n entre 1 y %d\n", argv[0], MAX_N);
        return 1;
    }
    Queens q = {.n = n};
    if (search(&q, 0)) {
        print_board(&q);
    } else {
        printf("no hay solución\n");
    }
    printf("n = %d, primera solución: %ld nodos\n", n, q.nodes);
    return 0;
}

// N reinas sin poda: pone una reina en cada fila, en cualquier columna, y solo revisa al final.
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 9

// Revisa cada par de reinas: 1 si ninguna ataca a otra.
static int all_safe(const int *column_of_row, int n) {
    for (int a = 0; a < n; a++) {
        for (int b = a + 1; b < n; b++) {
            int same_column = column_of_row[a] == column_of_row[b];
            int same_diagonal = abs(column_of_row[a] - column_of_row[b]) == b - a;
            if (same_column || same_diagonal) {
                return 0;
            }
        }
    }
    return 1;
}

static long search(int *column_of_row, int n, int row, long *nodes) {
    (*nodes)++;
    if (row == n) {
        return all_safe(column_of_row, n);
    }
    long solutions = 0;
    for (int col = 0; col < n; col++) {
        column_of_row[row] = col;
        solutions += search(column_of_row, n, row + 1, nodes);
    }
    return solutions;
}

int main(int argc, char *argv[]) {
    int n;
    if (argc != 2 || sscanf(argv[1], "%d", &n) != 1 || n < 1 || n > MAX_N) {
        fprintf(stderr, "uso: %s n, con n entre 1 y %d\n", argv[0], MAX_N);
        return 1;
    }
    int column_of_row[MAX_N];
    long nodes = 0;
    long solutions = search(column_of_row, n, 0, &nodes);
    printf("n = %d, sin poda: %ld soluciones, %ld nodos\n", n, solutions, nodes);
    return 0;
}

// Escribe el árbol de búsqueda de 4 reinas: cada línea es una reina puesta, con su sangría.
#include <stdio.h>

#define N 4

typedef struct {
    int column_used[N];
    int down_used[2 * N - 1];
    int up_used[2 * N - 1];
    long nodes;
} Queens;

static int can_place(const Queens *q, int row, int col) {
    return !q->column_used[col] && !q->down_used[row - col + N - 1] && !q->up_used[row + col];
}

static void mark(Queens *q, int row, int col, int value) {
    q->column_used[col] = value;
    q->down_used[row - col + N - 1] = value;
    q->up_used[row + col] = value;
}

static void print_indent(int row) {
    for (int i = 0; i < row; i++) {
        printf("  ");
    }
}

static void search(Queens *q, int row) {
    q->nodes++;
    if (row == N) {
        print_indent(row);
        printf("solución\n");
        return;
    }
    int tried = 0;
    for (int col = 0; col < N; col++) {
        if (can_place(q, row, col)) {
            tried = 1;
            print_indent(row);
            printf("fila %d, columna %d\n", row, col);
            mark(q, row, col, 1);
            search(q, row + 1);
            mark(q, row, col, 0);
        }
    }
    if (!tried) {
        print_indent(row);
        printf("sin lugar en la fila %d: se vuelve\n", row);
    }
}

int main(void) {
    Queens q = {.nodes = 0};
    search(&q, 0);
    printf("nodos: %ld\n", q.nodes);
    return 0;
}

// N reinas con poda: una columna o diagonal ocupada corta la rama antes de seguir.
#include <stdio.h>

#define MAX_N 16

typedef struct {
    int n;
    int column_used[MAX_N];
    int down_used[2 * MAX_N - 1];   // diagonal que baja: row - col + n - 1 es constante
    int up_used[2 * MAX_N - 1];     // diagonal que sube: row + col es constante
    long solutions;
    long nodes;
} Queens;

static int can_place(const Queens *q, int row, int col) {
    return !q->column_used[col]
        && !q->down_used[row - col + q->n - 1]
        && !q->up_used[row + col];
}

// Pone una reina con value = 1 y la quita con value = 0.
static void mark(Queens *q, int row, int col, int value) {
    q->column_used[col] = value;
    q->down_used[row - col + q->n - 1] = value;
    q->up_used[row + col] = value;
}

static void search(Queens *q, int row) {
    q->nodes++;
    if (row == q->n) {
        q->solutions++;
        return;
    }
    for (int col = 0; col < q->n; col++) {
        if (can_place(q, row, col)) {
            mark(q, row, col, 1);       // elegir
            search(q, row + 1);         // explorar
            mark(q, row, col, 0);       // deshacer
        }
    }
}

int main(int argc, char *argv[]) {
    int n;
    if (argc != 2 || sscanf(argv[1], "%d", &n) != 1 || n < 1 || n > MAX_N) {
        fprintf(stderr, "uso: %s n, con n entre 1 y %d\n", argv[0], MAX_N);
        return 1;
    }
    Queens q = {.n = n};
    search(&q, 0);
    printf("n = %d, con poda: %ld soluciones, %ld nodos\n", n, q.solutions, q.nodes);
    return 0;
}

// Subconjuntos de "abc": en cada elemento se decide si se toma o no.
#include <stdio.h>
#include <string.h>

#define MAX_ITEMS 16

static void print_subset(const char *items, const int *chosen, int n) {
    printf("{");
    for (int i = 0; i < n; i++) {
        if (chosen[i]) {
            printf(" %c", items[i]);
        }
    }
    printf(" }\n");
}

static void subsets(const char *items, int *chosen, int n, int index, long *nodes) {
    (*nodes)++;
    if (index == n) {
        print_subset(items, chosen, n);
        return;
    }
    chosen[index] = 1;                               // elegir: se toma
    subsets(items, chosen, n, index + 1, nodes);     // explorar
    chosen[index] = 0;                               // deshacer: no se toma
    subsets(items, chosen, n, index + 1, nodes);     // explorar
}

int main(void) {
    const char *items = "abc";
    int chosen[MAX_ITEMS] = {0};
    long nodes = 0;

    subsets(items, chosen, (int) strlen(items), 0, &nodes);
    printf("nodos: %ld\n", nodes);
    return 0;
}

// ERROR A PROPÓSITO: la poda supone precios positivos, y aquí hay un vale de descuento.
#include <stdio.h>

#define COUNT_OF_PRICES 3

static long count_all(const int *prices, int n, int index, int total, int budget) {
    if (index == n) {
        return total <= budget;
    }
    return count_all(prices, n, index + 1, total + prices[index], budget)
         + count_all(prices, n, index + 1, total, budget);
}

static long count_pruned(const int *prices, int n, int index, int total, int budget) {
    if (total > budget) {
        return 0;   // falso aquí: el vale todavía podría bajar el total
    }
    if (index == n) {
        return 1;
    }
    return count_pruned(prices, n, index + 1, total + prices[index], budget)
         + count_pruned(prices, n, index + 1, total, budget);
}

int main(void) {
    int prices[COUNT_OF_PRICES] = {8, 5, -5};
    int budget = 6;

    printf("sin poda: %ld combinaciones\n", count_all(prices, COUNT_OF_PRICES, 0, 0, budget));
    printf("con poda: %ld combinaciones\n", count_pruned(prices, COUNT_OF_PRICES, 0, 0, budget));
    return 0;
}

// ERROR A PROPÓSITO: search avisa que encontró una solución, y quien la llama no hace caso.
#include <stdio.h>

#define MAX_N 16

typedef struct {
    int n;
    int column_of_row[MAX_N];
    int column_used[MAX_N];
    int down_used[2 * MAX_N - 1];
    int up_used[2 * MAX_N - 1];
    long nodes;
} Queens;

static int can_place(const Queens *q, int row, int col) {
    return !q->column_used[col]
        && !q->down_used[row - col + q->n - 1]
        && !q->up_used[row + col];
}

static void mark(Queens *q, int row, int col, int value) {
    q->column_used[col] = value;
    q->down_used[row - col + q->n - 1] = value;
    q->up_used[row + col] = value;
}

// Devuelve 1 si encontró una solución, y la deja en column_of_row.
static int search(Queens *q, int row) {
    q->nodes++;
    if (row == q->n) {
        return 1;
    }
    for (int col = 0; col < q->n; col++) {
        if (can_place(q, row, col)) {
            mark(q, row, col, 1);
            q->column_of_row[row] = col;
            search(q, row + 1);     // falta revisar lo que devuelve
            mark(q, row, col, 0);
        }
    }
    return 0;
}

static void print_board(const Queens *q) {
    for (int row = 0; row < q->n; row++) {
        for (int col = 0; col < q->n; col++) {
            if (q->column_of_row[row] == col) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
}

int main(int argc, char *argv[]) {
    int n;
    if (argc != 2 || sscanf(argv[1], "%d", &n) != 1 || n < 1 || n > MAX_N) {
        fprintf(stderr, "uso: %s n, con n entre 1 y %d\n", argv[0], MAX_N);
        return 1;
    }
    Queens q = {.n = n};
    if (search(&q, 0)) {
        print_board(&q);
    } else {
        printf("no hay solución\n");
    }
    printf("n = %d, primera solución: %ld nodos\n", n, q.nodes);
    return 0;
}

// ERROR A PROPÓSITO: el elemento usado nunca vuelve a quedar libre.
#include <stdio.h>
#include <string.h>

#define MAX_ITEMS 16

static void permutations(const char *items, int n, char *current, int *used, int depth) {
    if (depth == n) {
        current[n] = '\0';
        printf("%s\n", current);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = 1;
            current[depth] = items[i];
            permutations(items, n, current, used, depth + 1);
            // falta used[i] = 0;
        }
    }
}

int main(void) {
    const char *items = "abc";
    char current[MAX_ITEMS + 1];
    int used[MAX_ITEMS] = {0};

    permutations(items, (int) strlen(items), current, used, 0);
    return 0;
}

// ERROR A PROPÓSITO: se quita la reina de la columna, pero sus diagonales quedan marcadas.
#include <stdio.h>

#define MAX_N 16

typedef struct {
    int n;
    int column_used[MAX_N];
    int down_used[2 * MAX_N - 1];   // diagonal que baja: row - col + n - 1 es constante
    int up_used[2 * MAX_N - 1];     // diagonal que sube: row + col es constante
    long solutions;
    long nodes;
} Queens;

static int can_place(const Queens *q, int row, int col) {
    return !q->column_used[col]
        && !q->down_used[row - col + q->n - 1]
        && !q->up_used[row + col];
}

// Pone una reina con value = 1 y la quita con value = 0.
static void mark(Queens *q, int row, int col, int value) {
    q->column_used[col] = value;
    q->down_used[row - col + q->n - 1] = value;
    q->up_used[row + col] = value;
}

static void search(Queens *q, int row) {
    q->nodes++;
    if (row == q->n) {
        q->solutions++;
        return;
    }
    for (int col = 0; col < q->n; col++) {
        if (can_place(q, row, col)) {
            mark(q, row, col, 1);       // elegir
            search(q, row + 1);         // explorar
            q->column_used[col] = 0;    // deshace solo una parte
        }
    }
}

int main(int argc, char *argv[]) {
    int n;
    if (argc != 2 || sscanf(argv[1], "%d", &n) != 1 || n < 1 || n > MAX_N) {
        fprintf(stderr, "uso: %s n, con n entre 1 y %d\n", argv[0], MAX_N);
        return 1;
    }
    Queens q = {.n = n};
    search(&q, 0);
    printf("n = %d, con poda: %ld soluciones, %ld nodos\n", n, q.solutions, q.nodes);
    return 0;
}

// ERROR A PROPÓSITO: después de explorar con el elemento, no se deshace la elección.
#include <stdio.h>
#include <string.h>

#define MAX_ITEMS 16

static void print_subset(const char *items, const int *chosen, int n) {
    printf("{");
    for (int i = 0; i < n; i++) {
        if (chosen[i]) {
            printf(" %c", items[i]);
        }
    }
    printf(" }\n");
}

static void subsets(const char *items, int *chosen, int n, int index) {
    if (index == n) {
        print_subset(items, chosen, n);
        return;
    }
    chosen[index] = 1;
    subsets(items, chosen, n, index + 1);
    subsets(items, chosen, n, index + 1);   // falta chosen[index] = 0 antes de esta línea
}

int main(void) {
    const char *items = "abc";
    int chosen[MAX_ITEMS] = {0};

    subsets(items, chosen, (int) strlen(items), 0);
    return 0;
}

"""Comprueba los programas de la clase y lo que los apuntes dicen de ellos."""
import math
import pathlib
import subprocess
import tempfile
import unittest

HERE = pathlib.Path(__file__).parent
BUILD = HERE / "build"
BASE = ["-Wall", "-Wextra", "-std=c17"]
FLAGS = [*BASE, "-g", "-fsanitize=address,undefined"]
PROGRAMS = ["subsets", "permutations", "count_trees", "queens_no_prune", "queens", "queens_first",
            "queens_trace", "combos"]
WITH_ERRORS = ["subsets_no_undo", "permutations_no_undo", "queens_partial_undo", "first_ignored", "bad_prune"]
QUEENS_SOLUTIONS = {4: 2, 5: 10, 6: 4, 7: 40, 8: 92}
QUEENS_PRUNED_NODES = {4: 17, 5: 54, 6: 153, 7: 552, 8: 2057}


def run(program, *arguments):
    done = subprocess.run(
        [str(program), *arguments], cwd=HERE, text=True, encoding="utf-8", errors="replace",
        stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=60,
    )
    return done.stdout, done.returncode


def run_error(name, *arguments):
    with tempfile.TemporaryDirectory() as folder:
        binary = pathlib.Path(folder) / name
        subprocess.run(["gcc", *FLAGS, "-Werror", f"errors/{name}.c", "-o", str(binary)], cwd=HERE, check=True,
                       stdout=subprocess.PIPE, stderr=subprocess.STDOUT)
        return run(binary, *arguments)


class Programs(unittest.TestCase):
    def test_every_program_compiles_without_warnings(self):
        for name in PROGRAMS:
            with self.subTest(program=name):
                subprocess.run(["gcc", *FLAGS, "-Werror", f"{name}.c", "-o", "/dev/null"], cwd=HERE, check=True,
                               stdout=subprocess.PIPE, stderr=subprocess.STDOUT)

    def test_subsets_tree(self):
        out, code = run(BUILD / "subsets")
        self.assertEqual(code, 0, out)
        lines = out.splitlines()
        self.assertEqual(len(lines) - 1, 8)
        self.assertEqual(len(set(lines)), 9)
        self.assertEqual(lines[-1], "nodos: 15")

    def test_permutations_tree(self):
        out, code = run(BUILD / "permutations")
        self.assertEqual(code, 0, out)
        self.assertEqual(out.splitlines(), ["abc", "acb", "bac", "bca", "cab", "cba", "nodos: 16"])

    def test_the_formulas_agree_with_the_counts(self):
        out, _ = run(BUILD / "count_trees")
        for line in out.splitlines()[1:]:
            parts = line.replace("|", " ").split()
            n, sub_leaves, sub_nodes, perm_leaves, perm_nodes = map(int, parts)
            self.assertEqual(sub_leaves, 2 ** n)
            self.assertEqual(sub_nodes, 2 ** (n + 1) - 1)
            self.assertEqual(perm_leaves, math.factorial(n))
            # Nodos del nivel k: n! / (n - k)!
            self.assertEqual(perm_nodes, sum(math.factorial(n) // math.factorial(n - k) for k in range(n + 1)))

    def test_review_question_about_five_elements(self):
        out, _ = run(BUILD / "count_trees")
        self.assertIn(" 5 |           32       63 |           120        326", out)

    def test_pruning_keeps_the_same_solutions(self):
        for n, solutions in QUEENS_SOLUTIONS.items():
            with self.subTest(n=n):
                plain, _ = run(BUILD / "queens_no_prune", str(n))
                pruned, _ = run(BUILD / "queens", str(n))
                self.assertIn(f"{solutions} soluciones", plain)
                self.assertIn(f"{solutions} soluciones", pruned)
                self.assertIn(f"{(n ** (n + 1) - 1) // (n - 1)} nodos", plain)
                self.assertIn(f"{QUEENS_PRUNED_NODES[n]} nodos", pruned)

    def test_numbers_quoted_in_the_notes(self):
        self.assertEqual(math.comb(64, 8), 4426165368)
        self.assertEqual(8 ** 8, 16777216)
        self.assertEqual(len(str(9 ** 57)), 55)
        self.assertEqual(len(str(math.factorial(20))), 19)
        self.assertGreater((12 ** 13 - 1) // 11, 9 * 10 ** 12)
        empty = (HERE / "lab" / "data" / "dificil.txt").read_text().count("0")
        self.assertEqual(empty, 57)

    def test_first_solution_stops_early_and_is_a_real_solution(self):
        out, code = run(BUILD / "queens_first", "8")
        self.assertEqual(code, 0, out)
        rows = [line.split() for line in out.splitlines()[:8]]
        columns = [row.index("Q") for row in rows]
        self.assertEqual(sorted(columns), list(range(8)))
        for a in range(8):
            for b in range(a + 1, 8):
                self.assertNotEqual(abs(columns[a] - columns[b]), b - a)
        self.assertIn("114 nodos", out)

    def test_programs_reject_bad_arguments(self):
        for name in ["queens", "queens_no_prune", "queens_first"]:
            for arguments in [(), ("x",), ("0",), ("99",)]:
                with self.subTest(program=name, arguments=arguments):
                    out, code = run(BUILD / name, *arguments)
                    self.assertEqual(code, 1)
                    self.assertIn("uso:", out)

    def test_pruning_saves_nodes_and_keeps_the_answer(self):
        out, _ = run(BUILD / "combos")
        self.assertEqual(out.splitlines(), ["sin poda: 249 combinaciones, 8191 nodos",
                                            "con poda: 249 combinaciones, 1265 nodos"])


class ProgramsWithErrors(unittest.TestCase):
    def test_they_compile_without_warnings(self):
        # Por eso son bugs difíciles: ni gcc ni los sanitizers avisan. Solo la salida los delata.
        for name in WITH_ERRORS:
            with self.subTest(program=name):
                subprocess.run(["gcc", *FLAGS, "-Werror", f"errors/{name}.c", "-o", "/dev/null"], cwd=HERE,
                               check=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT)

    def test_subsets_without_undo_repeat(self):
        out, code = run_error("subsets_no_undo")
        self.assertEqual(code, 0, out)
        self.assertEqual(out.splitlines(), ["{ a b c }"] * 8)

    def test_permutations_without_undo_find_one(self):
        out, code = run_error("permutations_no_undo")
        self.assertEqual(code, 0, out)
        self.assertEqual(out.splitlines(), ["abc"])

    def test_partial_undo_loses_the_solutions(self):
        out, code = run_error("queens_partial_undo", "8")
        self.assertEqual(code, 0, out)
        self.assertIn("n = 8, con poda: 0 soluciones, 11 nodos", out)

    def test_ignoring_the_return_loses_the_solution(self):
        out, code = run_error("first_ignored", "8")
        self.assertEqual(code, 0, out)
        self.assertEqual(out.splitlines(), ["no hay solución", "n = 8, primera solución: 2057 nodos"])

    def test_bad_prune_loses_a_combination(self):
        out, code = run_error("bad_prune")
        self.assertEqual(code, 0, out)
        self.assertEqual(out.splitlines(), ["sin poda: 5 combinaciones", "con poda: 4 combinaciones"])


if __name__ == "__main__":
    unittest.main()

"""Pruebas del laboratorio. LAB_DIR dice dónde está el código: lab o solution.

Cada prueba compila un main propio con board.c de lab y con subset_sum.c y solver.c de esa
carpeta. Corren con ASan y UBSan. Las cuentas de nodos exactas salen de las reglas de
lab/solver.h: si una no coincide y el tablero sí queda bien, revisen esas reglas.
"""
import os
import pathlib
import subprocess
import tempfile
import unittest

HERE = pathlib.Path(__file__).parent
LAB_DIR = os.environ.get("LAB_DIR", "solution")
SOURCE = HERE / LAB_DIR
FLAGS = ["-Wall", "-Wextra", "-std=c17", "-g", "-fsanitize=address,undefined"]
BOARD_C = HERE / "lab" / "board.c"
DATA = HERE / "lab" / "data"
# Tablero: nodos en orden de lectura y nodos con menos opciones, medidos con la solución.
BOARDS = {"facil.txt": (72, 38), "medio.txt": (4314, 169), "dificil.txt": (1745319, 1815),
          "sorpresa.txt": (815, 1116)}
# medio.txt con un 9 de más en la primera celda: es legal, pero ya no tiene solución.
UNSOLVABLE = "930000080000030005004072006190000000302001400700203961000100000000700239000029614"
UNSOLVABLE_NODES = (2070, 119)
METHODS = {"solve_in_order": 0, "solve_fewest_options": 1}


def as_rows(digits):
    return "".join(digits[i:i + 9] + "\n" for i in range(0, 81, 9))


def build_and_run(main_source, sources, files=None):
    """Devuelve (salida, código de salida) de un main propio, en una carpeta temporal."""
    with tempfile.TemporaryDirectory() as name:
        folder = pathlib.Path(name)
        for file_name, content in (files or {}).items():
            (folder / file_name).write_text(content, encoding="utf-8")
        driver = folder / "driver.c"
        driver.write_text(main_source, encoding="utf-8")
        binary = folder / "driver"
        built = subprocess.run(
            ["gcc", *FLAGS, f"-I{HERE / 'lab'}", str(driver), *map(str, sources), "-o", str(binary)],
            text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
        )
        if built.returncode != 0:
            raise AssertionError(f"No compila:\n{built.stdout}")
        try:
            done = subprocess.run(
                [str(binary)], cwd=folder, text=True, encoding="utf-8", errors="replace",
                stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=60,
            )
        except subprocess.TimeoutExpired:
            raise AssertionError("El programa tardó más de 60 segundos: ¿una búsqueda sin fin?")
        return done.stdout, done.returncode


def main_with(body):
    return ('#include <stdio.h>\n#include "board.h"\n#include "solver.h"\n#include "subset_sum.h"\n'
            "int main(void) {\n" + body + "\nreturn 0;\n}\n")


def run_board(body, files=None):
    return build_and_run(main_with(body), [BOARD_C], files)


def run_solver(body, files=None):
    return build_and_run(main_with(body), [BOARD_C, SOURCE / "solver.c"], files)


def run_subset(body):
    return build_and_run(main_with(body), [SOURCE / "subset_sum.c"])


def print_cells(name="board"):
    return ("for (int r = 0; r < BOARD_SIZE; r++) { for (int c = 0; c < BOARD_SIZE; c++) { "
            f'printf("%d", {name}.cells[r][c]); }} }} printf("\\n");\n')


class LabCase(unittest.TestCase):
    longMessage = False

    def check(self, result, wanted, what):
        out, code = result
        if code != 0:
            self.fail(f"{what}: el programa terminó con error.\n{out}")
        if out.strip() != wanted:
            self.fail(f"{what}\n  se esperaba: {wanted}\n  se obtuvo:   {out.strip()}")


class Reader(LabCase):
    """El lector ya viene hecho: estas pruebas pasan desde el inicio."""

    def load(self, content):
        body = 'Board board; printf("%d\\n", board_load("in.txt", &board));'
        return run_board(body, {"in.txt": content})

    def test_reads_a_good_file(self):
        body = 'Board board; if (!board_load("in.txt", &board)) { return 1; }\n' + print_cells()
        self.check(run_board(body, {"in.txt": as_rows(UNSOLVABLE)}), UNSOLVABLE, "Lectura de un archivo correcto.")

    def test_last_line_may_lack_the_newline(self):
        self.check(self.load(as_rows(UNSOLVABLE)[:-1]), "1", "Última línea sin salto de línea.")

    def test_rejects_bad_formats(self):
        rows = as_rows(UNSOLVABLE)
        lines = rows.splitlines()
        bad = {
            "una fila menos": "\n".join(lines[:8]) + "\n",
            "una fila más": rows + lines[0] + "\n",
            "una línea corta": rows.replace(lines[4], lines[4][:8]),
            "una línea larga": rows.replace(lines[4], lines[4] + "1"),
            "una letra": rows.replace(lines[4], "x" + lines[4][1:]),
            "archivo vacío": "",
        }
        for what, content in bad.items():
            with self.subTest(what):
                self.check(self.load(content), "0", f"Debe rechazar: {what}.")

    def test_missing_file(self):
        body = 'Board board; printf("%d\\n", board_load("no_existe.txt", &board));'
        self.check(run_board(body), "0", "Un archivo que no existe.")

    def test_legal_detects_repeats(self):
        empty = "0" * 81
        cases = {"fila": (0, 8), "columna": (0, 72), "caja": (0, 20)}
        for what, (a, b) in cases.items():
            digits = list(empty)
            digits[a] = digits[b] = "5"
            body = ('Board board; if (!board_load("in.txt", &board)) { return 1; }\n'
                    'printf("%d\\n", board_is_legal(&board));')
            with self.subTest(what):
                self.check(run_board(body, {"in.txt": as_rows("".join(digits))}), "0", f"Repetido en la {what}.")
        body = ('Board board; if (!board_load("in.txt", &board)) { return 1; }\n'
                'printf("%d\\n", board_is_legal(&board));')
        self.check(run_board(body, {"in.txt": as_rows(UNSOLVABLE)}), "1", "Un tablero sin repetidos.")


@unittest.skipUnless((SOURCE / "subset_sum.c").exists(), f"no está {LAB_DIR}/subset_sum.c")
class SubsetSum(LabCase):
    def answers(self, values, targets):
        items = ", ".join(map(str, values))
        body = f"int values[] = {{{items}}}; long nodes = 0;\n"
        for target in targets:
            body += f'printf("%d ", subset_sum(values, {len(values)}, {target}, &nodes));\n'
        return run_subset(body)

    def test_finds_sums(self):
        self.check(self.answers([3, 9, 5, 14], [8, 12, 17, 31, 3]), "1 1 1 1 1", "Sumas que sí existen.")

    def test_rejects_sums(self):
        self.check(self.answers([3, 9, 5, 14], [1, 2, 13, 30, 32, -1]), "0 0 0 0 0 0", "Sumas que no existen.")

    def test_empty_subset_sums_zero(self):
        body = 'int values[] = {7}; long nodes = 0;\nprintf("%d %d\\n", subset_sum(values, 0, 0, &nodes),'\
               ' subset_sum(values, 0, 7, &nodes));'
        self.check(run_subset(body), "1 0", "Con 0 elementos solo se puede sumar 0.")
        self.check(self.answers([4, 6], [0]), "1", "El subconjunto vacío suma 0.")

    def test_negative_values_are_not_pruned_away(self):
        # 8 ya se pasa de 3, pero 8 + (-5) = 3. Una poda por "ya me pasé" pierde esta solución.
        self.check(self.answers([8, 5, -5], [3, 0, 13, 8, 6]), "1 1 1 1 0", "Con valores negativos.")

    def test_no_solution_visits_the_whole_tree(self):
        items = ", ".join(str(2 * i + 2) for i in range(10))
        body = (f'int values[] = {{{items}}}; long nodes = 0;\n'
                'int found = subset_sum(values, 10, 3, &nodes);\n'
                'printf("%d %ld\\n", found, nodes);')
        self.check(run_subset(body), "0 2047", "Los pares no suman 3, así que se visitan 2^11 - 1 nodos.")

    def test_stops_at_the_first_solution(self):
        items = ", ".join(str(i + 1) for i in range(16))
        body = (f'int values[] = {{{items}}}; long nodes = 0;\n'
                'int found = subset_sum(values, 16, 1, &nodes);\n'
                'printf("%d %d\\n", found, nodes > 0 && nodes < 131071);')
        self.check(run_subset(body), "1 1", "Debe contar nodos, y detenerse al encontrar una solución.")


@unittest.skipUnless((SOURCE / "solver.c").exists(), f"no está {LAB_DIR}/solver.c")
class Solver(LabCase):
    def on_board(self, name, body):
        code = (f'Board board; if (!board_load("{DATA / name}", &board)) {{ return 1; }}\n' + body)
        return run_solver(code)

    def test_can_place(self):
        body = ('printf("%d %d %d %d %d\\n", can_place(&board, 0, 4, 3), can_place(&board, 3, 3, 4),'
                " can_place(&board, 0, 4, 8), can_place(&board, 0, 4, 5), can_place(&board, 0, 4, 1));")
        self.check(self.on_board("facil.txt", body), "0 0 0 1 1",
                   "can_place: 3 está en la fila, 4 en la columna, 8 en la caja; 5 y 1 están libres.")

    def test_can_place_looks_at_the_whole_box(self):
        # Un 5 en el centro: (3, 3), (5, 5) y (3, 5) lo ven solo por la caja, y (2, 2) no lo ve.
        digits = ["0"] * 81
        digits[40] = "5"
        code = ('Board board; if (!board_load("in.txt", &board)) { return 1; }\n'
                'printf("%d %d %d %d\\n", can_place(&board, 3, 3, 5), can_place(&board, 5, 5, 5),'
                " can_place(&board, 3, 5, 5), can_place(&board, 2, 2, 5));")
        self.check(run_solver(code, {"in.txt": as_rows("".join(digits))}), "0 0 0 1",
                   "can_place con un 5 en el centro del tablero.")

    def test_count_options(self):
        body = ('printf("%d %d %d\\n", count_options(&board, 0, 2), count_options(&board, 0, 4),'
                " count_options(&board, 8, 0));")
        self.check(self.on_board("facil.txt", body), "3 2 1", "count_options en tres celdas de facil.txt.")

    def solved(self, method, name):
        """Comprueba el tablero con solo mirarlo: que respete las pistas, que esté lleno y sea legal."""
        original = (DATA / name).read_text().replace("\n", "")
        body = (f"long nodes = 0; int found = {method}(&board, &nodes);\n"
                'printf("%d %ld %d\\n", found, nodes, board_is_legal(&board));\n' + print_cells())
        out, code = self.on_board(name, body)
        if code != 0:
            self.fail(f"{method} con {name}: el programa terminó con error.\n{out}")
        first, cells = out.split("\n")[:2]
        found, nodes, legal = first.split()
        if found != "1":
            self.fail(f"{method} con {name}: dijo que no hay solución, y sí hay una.")
        if "0" in cells:
            self.fail(f"{method} con {name}: el tablero quedó con celdas vacías.\n{cells}")
        if legal != "1":
            self.fail(f"{method} con {name}: el tablero quedó con repetidos.\n{cells}")
        if any(a != "0" and a != b for a, b in zip(original, cells)):
            self.fail(f"{method} con {name}: cambió una celda que venía dada.")
        return int(nodes)

    def test_solves_every_board_with_the_expected_nodes(self):
        for method, position in METHODS.items():
            for name, wanted in BOARDS.items():
                with self.subTest(method=method, board=name):
                    nodes = self.solved(method, name)
                    if nodes != wanted[position]:
                        self.fail(f"{method} con {name}: el tablero queda bien, pero visitó {nodes} nodos y "
                                  f"se esperaban {wanted[position]}. Revisen las reglas de lab/solver.h.")

    def test_unsolvable_board_is_left_as_it_was(self):
        for method, position in METHODS.items():
            code = ('Board board; if (!board_load("in.txt", &board)) { return 1; }\n'
                    f'long nodes = 0; int found = {method}(&board, &nodes); printf("%d %ld\\n", found, nodes);\n' + print_cells())
            with self.subTest(method=method):
                self.check(run_solver(code, {"in.txt": as_rows(UNSOLVABLE)}),
                           f"0 {UNSOLVABLE_NODES[position]}\n{UNSOLVABLE}",
                           f"{method} en un tablero sin solución: debe devolver 0, contar los nodos y dejar el "
                           "tablero igual. Si cambió, falta deshacer.")

    def test_full_board_is_one_node(self):
        for method in METHODS:
            code = (f'Board board; if (!board_load("{DATA / "facil.txt"}", &board)) {{ return 1; }}\n'
                    f"long nodes = 0; if (!{method}(&board, &nodes)) {{ return 1; }}\n"
                    f'printf("%d ", {method}(&board, &nodes)); printf("%ld\\n", nodes);')
            with self.subTest(method=method):
                self.check(run_solver(code), "1 1", f"{method} en un tablero ya lleno: un nodo, y devuelve 1.")

    def test_empty_board_has_a_solution(self):
        for method in METHODS:
            code = ('Board board; if (!board_load("in.txt", &board)) { return 1; }\n'
                    f"long nodes = 0; int found = {method}(&board, &nodes);\n"
                    "int empty = 0; for (int r = 0; r < BOARD_SIZE; r++) { for (int c = 0; c < BOARD_SIZE; c++) "
                    "{ if (board.cells[r][c] == 0) { empty++; } } }\n"
                    'printf("%d %d %d\\n", found, empty, board_is_legal(&board));')
            with self.subTest(method=method):
                self.check(run_solver(code, {"in.txt": as_rows("0" * 81)}), "1 0 1",
                           f"{method} en un tablero vacío: hay muchas soluciones, y basta la primera.")

    def test_the_counter_starts_again_in_each_call(self):
        for method, position in METHODS.items():
            code = (f'Board a; Board b; if (!board_load("{DATA / "facil.txt"}", &a)) {{ return 1; }}\n'
                    "b = a; long first = 0; long second = 0;\n"
                    f"{method}(&a, &first); {method}(&b, &second);\n"
                    'printf("%ld %ld\\n", first, second);')
            wanted = BOARDS["facil.txt"][position]
            with self.subTest(method=method):
                self.check(run_solver(code), f"{wanted} {wanted}",
                           "Dos llamadas seguidas deben contar lo mismo: el contador no es una variable static.")


@unittest.skipUnless((HERE / "solution" / "count_solutions.c").exists(), "falta la solución")
class GivenBoards(unittest.TestCase):
    def test_every_given_board_has_exactly_one_solution(self):
        paths = sorted(DATA.glob("*.txt"))
        with tempfile.TemporaryDirectory() as name:
            binary = pathlib.Path(name) / "count_solutions"
            sources = [HERE / "solution" / "count_solutions.c", HERE / "solution" / "solver.c", BOARD_C]
            subprocess.run(["gcc", *FLAGS, f"-I{HERE / 'lab'}", *map(str, sources), "-o", str(binary)], check=True)
            done = subprocess.run([str(binary), *map(str, paths)], text=True, stdout=subprocess.PIPE, timeout=60)
        self.assertEqual(done.returncode, 0)
        self.assertEqual(done.stdout, "".join(f"{path}: 1\n" for path in paths))


if __name__ == "__main__":
    unittest.main()