H 4η και η 8η στηλη με την προσθήκη μιας διπλης ευκαιρίας γινεται μια στηλη. Στις στήλες 10 και 14 με την προσθηκη παλι διπλης ευκαιριας γινεται μια στηλη και μειωνονται συνολικά οι στήλες στις 14. Και εκεί σταματάει δεν πέφτει παρακαπω πχ 13. Με 14 στήλες καλύπτεις και τις 42.
Τσεκαρισε και το σκριπτ και μου λες
from itertools import product
from ortools.sat.python import cp_model
RAW_COLUMNS = [
["X","1","1","X","1","X","1"],
["X","1","X","1","X","X","1"],
["1","1X","X","1","X","X","1"],
["1X","1","X","X","1","X","1"],
["1X","X","1","1","X","X","1"],
["1X","X","1","X","1","X","1"],
["X","1","1","X","1","1X","X"],
["X","1","X","1","1","X","1X"],
["X","1","X","1","X","1","1X"],
["X","X","1","1","X","1","1X"],
["1","1X","X","1","1","X","1X"],
["1","1X","X","1","X","1","1X"],
["1X","1","X","X","1","1X","X"],
["1","X","1","1X","X","1","1X"],
["1X","X","1","X","1","1X","X"],
["X","1X","1","X","X","1","1X"],
]
MATCHES = 7
TOKENS = ["1", "X", "1X"]
def expand(token: str) -> set[str]:
if token == "1":
return {"1"}
if token == "X":
return {"X"}
if token == "1X":
return {"1", "X"}
raise ValueError(f"Bad token: {token}")
def violates(seq: tuple[str, ...] | list[str]) -> bool:
for i in range(len(seq) - 2):
if expand(seq) & expand(seq[i + 1]) & expand(seq[i + 2]):
return True
return False
def covers(col: tuple[str, ...] | list[str], outcome: tuple[str, ...]) -> bool:
return all(outcome in expand(col) for i in range(MATCHES))
def normalize_columns(cols: list[list[str]]) -> list[tuple[str, ...]]:
out = []
for c in cols:
if len(c) != MATCHES:
raise ValueError(f"Column has length {len(c)} instead of {MATCHES}: {c}")
for t in c:
if t not in TOKENS:
raise ValueError(f"Invalid token {t} in column {c}")
out.append(tuple(c))
return out
def all_binary_outcomes() -> list[tuple[str, ...]]:
return list(product(["1", "X"], repeat=MATCHES))
def covered_outcomes_by_system(cols: list[tuple[str, ...]], outcomes: list[tuple[str, ...]]) -> list[tuple[str, ...]]:
target = []
for o in outcomes:
if any(covers(c, o) for c in cols):
target.append(o)
return target
def generate_all_valid_columns() -> list[tuple[str, ...]]:
cols = []
for c in product(TOKENS, repeat=MATCHES):
if not violates(c):
cols.append(c)
return cols
def solve_min_cover_exact(candidate_cols: list[tuple[str, ...]], target_outcomes: list[tuple[str, ...]]):
model = cp_model.CpModel()
n = len(candidate_cols)
x = [model.NewBoolVar(f"x{i}") for i in range(n)]
coverers = []
for o in target_outcomes:
idxs = [i for i, c in enumerate(candidate_cols) if covers(c, o)]
if not idxs:
raise RuntimeError(f"No candidate column covers target outcome {o}")
coverers.append(idxs)
model.Add(sum(x for i in idxs) >= 1)
model.Minimize(sum(x))
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 300
solver.parameters.num_search_workers = 8
status = solver.Solve(model)
if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
raise RuntimeError("Solver failed to find a feasible solution.")
selected_idx = [i for i in range(n) if solver.Value(x) == 1]
selected_cols = [candidate_cols for i in selected_idx]
return {
"status": status,
"selected_idx": selected_idx,
"selected_cols": selected_cols,
"objective": len(selected_cols),
}
def prove_no_solution_with_k_minus_1(candidate_cols: list[tuple[str, ...]], target_outcomes: list[tuple[str, ...]], k: int) -> bool:
model = cp_model.CpModel()
n = len(candidate_cols)
x = [model.NewBoolVar(f"x{i}") for i in range(n)]
for o in target_outcomes:
idxs = [i for i, c in enumerate(candidate_cols) if covers(c, o)]
if not idxs:
raise RuntimeError(f"No candidate column covers target outcome {o}")
model.Add(sum(x for i in idxs) >= 1)
model.Add(sum(x) <= k - 1)
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 300
solver.parameters.num_search_workers = 8
status = solver.Solve(model)
return status == cp_model.INFEASIBLE
def verify_solution_strict(selected_cols: list[tuple[str, ...]], target_outcomes: list[tuple[str, ...]]) -> None:
# 1) όλες valid
for i, c in enumerate(selected_cols, 1):
if violates(c):
raise AssertionError(f"Selected column {i} is INVALID: {c}")
# 2) όλα τα target outcomes καλύπτονται
missed = [o for o in target_outcomes if not any(covers(c, o) for c in selected_cols)]
if missed:
raise AssertionError(f"Solution misses target outcomes: {missed}")
# 3) reporting extra coverage
all_outcomes = all_binary_outcomes()
covered_now = [o for o in all_outcomes if any(covers(c, o) for c in selected_cols)]
print(f"Verification OK: selected system covers {len(covered_now)} / {len(all_outcomes)} total outcomes.")
def print_columns_pretty(cols, title="SYSTEM"):
print(f"\n=== {title} ===\n")
n_cols = len(cols)
n_rows = len(cols[0])
def fmt(x):
if x == "1X":
return "Δ"
return x
header = "Αγ | " + " ".join(f"{i+1:>2}" for i in range(n_cols))
print(header)
print("-" * len(header))
for r in range(n_rows):
row = f"{r+1:>2} | "
for c in range(n_cols):
val = fmt(cols[c][r])
row += f" {val:^2} "
print(row)
print("\nLegend: Δ = 1X\n")
def main():
raw_cols = normalize_columns(RAW_COLUMNS)
outcomes = all_binary_outcomes()
print("=== INPUT VALIDATION ===")
for i, c in enumerate(raw_cols, 1):
print(f"col {i:02d} valid: {not violates(c)}")
target_outcomes = covered_outcomes_by_system(raw_cols, outcomes)
print("\n=== CURRENT SYSTEM COVERAGE ===")
print(f"current covered: {len(target_outcomes)} / {len(outcomes)}")
valid_candidates = generate_all_valid_columns()
print("\n=== CANDIDATE SPACE ===")
print(f"all valid candidate columns: {len(valid_candidates)}")
res = solve_min_cover_exact(valid_candidates, target_outcomes)
k = res["objective"]
selected_cols = res["selected_cols"]
print("\n=== EXACT MINIMUM RESULT ===")
print(f"minimum columns needed: {k}")
print("\nSelected columns:")
for i, c in enumerate(selected_cols, 1):
print(f"{i:02d}: {' '.join(c)}")
print_columns_pretty(selected_cols, "FINAL SOLUTION")
print("\n=== STRICT VERIFICATION ===")
verify_solution_strict(selected_cols, target_outcomes)
print("\n=== MINIMALITY PROOF ===")
proof = prove_no_solution_with_k_minus_1(valid_candidates, target_outcomes, k)
print(f"No solution exists with {k-1} columns: {proof}")
if not proof:
raise AssertionError(
"WARNING: Solver found a solution, but k-1 infeasibility proof failed. "
"Do not publish this result."
)
print("\nFINAL STATUS: SAFE TO TRUST")
print(f"Exact minimum = {k}")
print("The printed columns are mathematically valid for the stated target coverage.")
if __name__ == "__main__":
main()
