"""Cells for `find_duplicate` (Q95, volt, 2026-10-28). The module had no cell in any gate, and the record that opened Q95 measured a `raise ValueError("no duplicate present in nums")` that no validated input can reach. These cells do two things a green gate could not do before: they grade the behaviour over the whole validated domain (n = 1..4, every array), and they grade the *shape* of the code -- the no-duplicate guard is declared as the module's only unexecuted line, so deleting it, or growing new dead code beside it, moves a cell. Run from the lane directory: python3 -m pytest -q test_find_duplicate.py """ import ast import itertools import sys import unittest from pathlib import Path import find_duplicate as fd MODULE_PATH = Path(fd.__file__) def _module_source(): return MODULE_PATH.read_text(encoding="utf-8") def _traced_call(func, *args): """Call func(*args), returning (result_or_exception, executed_line_set).""" executed = set() def local(frame, event, arg): if event == "line" and frame.f_code.co_filename == str(MODULE_PATH): executed.add(frame.f_lineno) return local previous = sys.gettrace() sys.settrace(local) try: try: result = func(*args) except Exception as exc: # noqa: BLE001 - the caller grades the class result = exc finally: sys.settrace(previous) return result, executed def _valid_arrays(n): return itertools.product(range(1, n + 1), repeat=n + 1) NO_DUPLICATE_INPUTS = ([], [1], [0, 1], [1, 3], [1, 2, 3, 4], [True, 1], [1.0, 1], ["1", 1]) NO_DUPLICATE_PERMUTATIONS = ([1, 2, 3, 4], [2, 1], [1, 2, 3]) class KnownDuplicates(unittest.TestCase): def test_each_documented_case_returns_its_duplicate(self): cases = [ ([1, 3, 4, 2, 2], 2), ([3, 1, 3, 4, 2], 3), ([1, 1], 1), ([2, 2, 2], 2), ([1, 2, 3, 4, 5, 5], 5), ([2, 4, 3, 2, 1], 2), # Phase 1's meeting point is inside the cycle and its value (3) # occurs once; only phase 2's entrance (2) is the duplicate. A # suite whose cases all have meeting == entrance cannot see phase 2 # go missing -- this case can. ([1, 2, 3, 4, 2], 2), ] for nums, expected in cases: with self.subTest(nums=nums): self.assertEqual(fd.find_duplicate(list(nums)), expected) def test_input_is_not_mutated(self): nums = [3, 1, 3, 4, 2] snapshot = list(nums) fd.find_duplicate(nums) self.assertEqual(nums, snapshot) def test_repeated_calls_are_deterministic(self): nums = [4, 3, 4, 2, 1] reads = {fd.find_duplicate(list(nums)) for _ in range(5)} self.assertEqual(reads, {4}) class ValidatedDomain(unittest.TestCase): def test_domain_size_is_the_pigeonhole_domain(self): # n**(n+1) for n = 1..4 -> 1 + 8 + 81 + 1024 self.assertEqual(sum(n ** (n + 1) for n in range(1, 5)), 1114) def test_every_validated_array_returns_a_value_occurring_twice(self): total = 0 for n in range(1, 5): for array in _valid_arrays(n): total += 1 nums = list(array) with self.subTest(nums=nums): got = fd.find_duplicate(nums) self.assertGreaterEqual(nums.count(got), 2) def test_no_validated_array_raises_anything(self): total = raises = 0 for n in range(1, 5): for array in _valid_arrays(n): total += 1 try: fd.find_duplicate(list(array)) except Exception as exc: # noqa: BLE001 - any raise is the finding raises += 1 self.fail("validated input raised %r: %r" % (array, exc)) self.assertEqual((total, raises), (1114, 0)) class RefusedInputs(unittest.TestCase): def test_short_arrays_are_refused_by_the_length_gate(self): for bad in ([], [1]): with self.subTest(bad=bad): with self.assertRaises(ValueError) as ctx: fd.find_duplicate(list(bad)) self.assertIn("at least 2 elements", str(ctx.exception)) def test_out_of_range_values_are_refused_by_the_range_gate(self): for bad in ([0, 1], [1, 3], [1, 2, 3, 4], [-1, 1]): with self.subTest(bad=bad): with self.assertRaises(ValueError) as ctx: fd.find_duplicate(list(bad)) self.assertIn("out of range", str(ctx.exception)) def test_bools_floats_and_strings_are_not_ints_for_this_contract(self): for bad in ([True, 1], [1.0, 1], ["1", 1]): with self.subTest(bad=bad): with self.assertRaises(ValueError) as ctx: fd.find_duplicate(list(bad)) self.assertIn("out of range", str(ctx.exception)) def test_no_duplicate_shape_is_refused_by_the_range_gate_not_by_floyd(self): # Q95's reading: a no-duplicate array of length n+1 over 1..n cannot # exist, so the nearest no-duplicate shape is one short and dies on the # range gate -- never on the "no duplicate present" branch. for permutation in NO_DUPLICATE_PERMUTATIONS: with self.subTest(permutation=permutation): with self.assertRaises(ValueError) as ctx: fd.find_duplicate(list(permutation)) message = str(ctx.exception) self.assertIn("out of range", message) self.assertNotIn("no duplicate present", message) class DeadBranchIsDeclared(unittest.TestCase): """The no-duplicate guard is the module's only unexecuted line.""" def _guard_raise_lineno(self): tree = ast.parse(_module_source()) for node in ast.walk(tree): if isinstance(node, ast.Raise) and isinstance(node.exc, ast.Call): for arg in node.exc.args: if isinstance(arg, ast.Constant) and isinstance(arg.value, str): if "no duplicate present" in arg.value: return node.lineno self.fail("the no-duplicate raise is gone from find_duplicate.py") def _statement_lines(self): tree = ast.parse(_module_source()) def is_docstring(node): return ( isinstance(node, ast.Expr) and isinstance(node.value, ast.Constant) and isinstance(node.value.value, str) ) lines = set() for node in tree.body: if isinstance(node, (ast.FunctionDef, ast.AsyncFunctionDef)): if node.name == "_self_test": continue # its own asserts are not this module's behaviour # `def` itself emits no line event, and a docstring is an # Expr the interpreter never steps into. for inner in ast.walk(node): if isinstance(inner, ast.stmt) and not is_docstring(inner): lines.add(inner.lineno) lines.discard(node.lineno) return lines def test_only_the_no_duplicate_raise_is_unexecuted(self): executed = set() for n in range(1, 5): for array in _valid_arrays(n): _, seen = _traced_call(fd.find_duplicate, list(array)) executed |= seen for bad in NO_DUPLICATE_INPUTS + NO_DUPLICATE_PERMUTATIONS: _, seen = _traced_call(fd.find_duplicate, list(bad)) executed |= seen declared_dead = self._guard_raise_lineno() unexecuted = self._statement_lines() - executed self.assertEqual( unexecuted, {declared_dead}, "unexecuted lines (declared dead line %d): %s" % (declared_dead, sorted(unexecuted)), ) def test_the_guard_cannot_fire_on_validated_input(self): # Independent of line numbers: no validated call may produce the # "no duplicate present" message. for n in range(1, 5): for array in _valid_arrays(n): result, _ = _traced_call(fd.find_duplicate, list(array)) self.assertNotIsInstance(result, ValueError, array) if __name__ == "__main__": unittest.main()