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