#!/usr/bin/env python3 """ verify_ca.py - Covering Array CA(N; t, k, v) Verifier Verifies whether a given array is a covering array CA(N; t, k, v). Exhaustively checks every t-subset of k columns and every one of the v^t tuples. """ import argparse import itertools import math import sys def verify_ca(lines, t: int, k: int, v: int, n: int) -> tuple[bool, str]: """ Verifies covering array properties on an iterable of text lines. Returns: (True, accept_message) if valid covering array. (False, reject_message) if invalid or uncovered tuple found. """ if t < 1 or k < 1 or v < 1 or n < 1: return False, f"REJECT: T, K, V, and N must all be positive integers (got t={t}, k={k}, v={v}, n={n})" if k < t: return False, f"REJECT: number of columns K ({k}) must be at least strength T ({t})" rows = [] for line_no, raw_line in enumerate(lines, 1): line = raw_line.rstrip("\r\n") stripped = line.strip() if not stripped or stripped.startswith("#"): continue tokens = stripped.split() if len(tokens) != k: return False, f"REJECT: line {line_no} has {len(tokens)} entries, expected K={k}" row = [] for tok in tokens: try: val = int(tok) except ValueError: return False, f"REJECT: line {line_no} is malformed: entry '{tok}' is not an integer" if val < 0 or val >= v: return False, f"REJECT: line {line_no} entry {val} is not in range [0, {v - 1}]" row.append(val) rows.append(tuple(row)) if len(rows) != n: return False, f"REJECT: row count {len(rows)} != N ({n})" target_tuples = v ** t # Exhaustive coverage check using a bytearray per column t-subset. # Specialized loops for t = 1, 2, 3, 4 for optimal performance. if t == 1: for (c0,) in itertools.combinations(range(k), 1): seen = bytearray(target_tuples) for row in rows: seen[row[c0]] = 1 missing = seen.find(b"\x00") if missing != -1: return False, f"REJECT: uncovered columns ({c0},) tuple ({missing},)" elif t == 2: for c0, c1 in itertools.combinations(range(k), 2): seen = bytearray(target_tuples) for row in rows: seen[row[c0] * v + row[c1]] = 1 missing = seen.find(b"\x00") if missing != -1: return False, f"REJECT: uncovered columns ({c0}, {c1}) tuple ({missing // v}, {missing % v})" elif t == 3: v2 = v * v for c0, c1, c2 in itertools.combinations(range(k), 3): seen = bytearray(target_tuples) for row in rows: seen[row[c0] * v2 + row[c1] * v + row[c2]] = 1 missing = seen.find(b"\x00") if missing != -1: u2 = missing % v rem = missing // v u1 = rem % v u0 = rem // v return False, f"REJECT: uncovered columns ({c0}, {c1}, {c2}) tuple ({u0}, {u1}, {u2})" elif t == 4: v2 = v * v v3 = v2 * v for c0, c1, c2, c3 in itertools.combinations(range(k), 4): seen = bytearray(target_tuples) for row in rows: seen[row[c0] * v3 + row[c1] * v2 + row[c2] * v + row[c3]] = 1 missing = seen.find(b"\x00") if missing != -1: temp = missing u = [0] * 4 for i in range(3, -1, -1): u[i] = temp % v temp //= v return False, f"REJECT: uncovered columns ({c0}, {c1}, {c2}, {c3}) tuple {tuple(u)}" else: for comb in itertools.combinations(range(k), t): seen = bytearray(target_tuples) for row in rows: idx = 0 for c in comb: idx = idx * v + row[c] seen[idx] = 1 missing = seen.find(b"\x00") if missing != -1: temp = missing u = [0] * t for i in range(t - 1, -1, -1): u[i] = temp % v temp //= v return False, f"REJECT: uncovered columns {comb} tuple {tuple(u)}" num_subsets = math.comb(k, t) total_tuples = num_subsets * target_tuples return True, f"ACCEPT: {num_subsets} subsets and {total_tuples} tuples checked" def run_selftest() -> bool: """ Self-test routine: 1. Builds the trivial CA(v^t; t, t, v) of all tuples (expects ACCEPT). 2. Deletes one row (expects REJECT). 3. Changes one entry to v (expects REJECT). 4. Drops one column (expects REJECT, wrong k). """ t, v = 2, 3 k = t n = v ** t # 9 base_rows = [list(p) for p in itertools.product(range(v), repeat=t)] def to_lines(rows): return [" ".join(str(x) for x in r) for r in rows] # Test 1: Trivial CA of all tuples -> ACCEPT ok, _ = verify_ca(to_lines(base_rows), t=t, k=k, v=v, n=n) if not ok: return False # Test 2: Delete one row -> REJECT del_rows = base_rows[1:] ok, msg = verify_ca(to_lines(del_rows), t=t, k=k, v=v, n=n) if ok or not msg.startswith("REJECT"): return False # Test 3: Change one entry to v -> REJECT bad_entry_rows = [list(r) for r in base_rows] bad_entry_rows[0][0] = v ok, msg = verify_ca(to_lines(bad_entry_rows), t=t, k=k, v=v, n=n) if ok or not msg.startswith("REJECT"): return False # Test 4: Drop one column -> REJECT (wrong k) drop_col_rows = [r[:-1] for r in base_rows] ok, msg = verify_ca(to_lines(drop_col_rows), t=t, k=k, v=v, n=n) if ok or not msg.startswith("REJECT") or ("entries" not in msg and "K" not in msg): return False return True def main(): parser = argparse.ArgumentParser(description="Verify Covering Array CA(N; t, k, v)") parser.add_argument("file", nargs="?", default=None, help="Input covering array file") parser.add_argument("--t", type=int, help="Strength t") parser.add_argument("--k", type=int, help="Number of columns k") parser.add_argument("--v", type=int, help="Alphabet size v") parser.add_argument("--n", type=int, help="Number of rows N") parser.add_argument("--selftest", action="store_true", help="Run self-tests and exit") args = parser.parse_args() if args.selftest: if run_selftest(): print("SELFTEST PASS") sys.exit(0) else: print("SELFTEST FAIL") sys.exit(1) if args.file is None or args.t is None or args.k is None or args.v is None or args.n is None: parser.print_usage(sys.stderr) print("REJECT: Missing required arguments. Usage: python3 verify_ca.py FILE --t T --k K --v V --n N", file=sys.stderr) sys.exit(1) try: with open(args.file, "r", encoding="utf-8") as f: lines = f.readlines() except Exception as e: print(f"REJECT: Cannot read file '{args.file}': {e}") sys.exit(1) ok, message = verify_ca(lines, t=args.t, k=args.k, v=args.v, n=args.n) print(message) sys.exit(0 if ok else 1) if __name__ == "__main__": main()