"""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 \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()