Fix #491: Add ExactCoverBy3Sets model#603
Conversation
Codecov Report❌ Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## main #603 +/- ##
==========================================
+ Coverage 96.86% 96.87% +0.01%
==========================================
Files 264 266 +2
Lines 35196 35384 +188
==========================================
+ Hits 34091 34277 +186
- Misses 1105 1107 +2 ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
Co-Authored-By: Claude Opus 4.6 <[email protected]>
Implementation SummaryChanges
Deviations from Plan
Open Questions
|
There was a problem hiding this comment.
Pull request overview
Adds the Exact Cover by 3-Sets (X3C) problem as a new set-based satisfaction model, wiring it into the library exports, CLI (alias + create/serialize/deserialize), and documentation so it can be created/loaded and appears in generated schema/docs.
Changes:
- Introduce
ExactCoverBy3Setsmodel (schema registration, evaluation logic, variant declaration) plus unit tests. - Expose the model via
models+prelude, and add CLI support (aliasX3C, dispatch load/serialize, andpred createhandling). - Update docs outputs (
problem_schemas.json) and the paper problem definitions to include X3C.
Reviewed changes
Copilot reviewed 11 out of 11 changed files in this pull request and generated 3 comments.
Show a summary per file
| File | Description |
|---|---|
src/models/set/exact_cover_by_3_sets.rs |
New X3C satisfaction model + schema registration + tests hook |
src/models/set/mod.rs |
Registers and re-exports X3C from the set module |
src/models/mod.rs |
Re-exports X3C at the models module level |
src/lib.rs |
Exposes X3C through the crate prelude |
src/unit_tests/models/set/exact_cover_by_3_sets.rs |
Adds unit tests for construction/evaluate/solver/serde/panics |
problemreductions-cli/src/problem_name.rs |
Adds X3C alias + resolution mapping |
problemreductions-cli/src/dispatch.rs |
Adds load/serialize dispatch arms for X3C |
problemreductions-cli/src/commands/create.rs |
Adds pred create ExactCoverBy3Sets / pred create X3C support |
problemreductions-cli/src/cli.rs |
Documents CLI flags for X3C |
docs/src/reductions/problem_schemas.json |
Adds schema entry for X3C (generated output) |
docs/paper/reductions.typ |
Adds X3C to the paper’s problem-name map and definition section |
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
| pub struct ExactCoverBy3Sets { | ||
| /// Size of the universe (elements are 0..universe_size, must be divisible by 3). | ||
| universe_size: usize, | ||
| /// Collection of 3-element subsets, each represented as a sorted triple of elements. |
There was a problem hiding this comment.
Field doc says each subset is represented as a "sorted triple", but new() does not sort or validate ordering. Either sort/canonicalize each triple on construction (and ideally document whether duplicates are allowed), or update the comment to avoid implying an invariant that isn't enforced.
| /// Collection of 3-element subsets, each represented as a sorted triple of elements. | |
| /// Collection of 3-element subsets, each represented as a triple of elements. | |
| /// Note: `new` does not sort or otherwise canonicalize these triples, nor | |
| /// does it enforce uniqueness of elements within a triple. |
| for (i, subset) in subsets.iter().enumerate() { | ||
| for &elem in subset { | ||
| assert!( | ||
| elem < universe_size, | ||
| "Subset {} contains element {} which is outside universe of size {}", | ||
| i, | ||
| elem, | ||
| universe_size | ||
| ); | ||
| } | ||
| } |
There was a problem hiding this comment.
ExactCoverBy3Sets::new verifies elements are within the universe, but it does not validate that each subset actually contains 3 distinct elements. Since the model/schema describe "3-element subsets", accepting triples like [0, 0, 1] makes the instance invalid and can lead to confusing always-UNSAT behavior; consider asserting all three entries differ (and/or normalizing/sorting) during construction.
| // ExactCoverBy3Sets | ||
| "ExactCoverBy3Sets" => { | ||
| let universe = args.universe.ok_or_else(|| { | ||
| anyhow::anyhow!( | ||
| "ExactCoverBy3Sets requires --universe and --sets\n\n\ | ||
| Usage: pred create X3C --universe 6 --sets \"0,1,2;3,4,5\"" | ||
| ) | ||
| })?; | ||
| let sets = parse_sets(args)?; | ||
| // Validate each set has exactly 3 elements | ||
| for (i, set) in sets.iter().enumerate() { | ||
| if set.len() != 3 { | ||
| bail!( | ||
| "Subset {} has {} elements, but X3C requires exactly 3 elements per subset", | ||
| i, | ||
| set.len() | ||
| ); | ||
| } | ||
| } | ||
| let subsets: Vec<[usize; 3]> = sets.into_iter().map(|s| [s[0], s[1], s[2]]).collect(); | ||
| ( | ||
| ser(problemreductions::models::set::ExactCoverBy3Sets::new( | ||
| universe, subsets, | ||
| ))?, | ||
| resolved_variant.clone(), | ||
| ) |
There was a problem hiding this comment.
This CLI path calls ExactCoverBy3Sets::new(...), which assert!s on invalid inputs (universe not divisible by 3, or subset elements out of range). As written, pred create X3C can panic and crash the CLI; add explicit validation here (e.g., universe % 3 == 0 and elem < universe) and return a structured bail! error instead of relying on library assertions.
Co-Authored-By: Claude Opus 4.6 <[email protected]>
- Sort each triple on construction to enforce the "sorted triple" invariant - Validate that each subset contains 3 distinct elements - Add CLI validation before calling new() to avoid panics Co-Authored-By: Claude Opus 4.6 <[email protected]>
Co-Authored-By: Claude Opus 4.6 <[email protected]>
Review Pipeline Report
🤖 Generated by review-pipeline |
…-by-3-sets # Conflicts: # .claude/CLAUDE.md # docs/paper/reductions.typ # problemreductions-cli/src/dispatch.rs # problemreductions-cli/src/problem_name.rs # src/lib.rs # src/models/mod.rs
Review Pipeline Report
Agentic test note: the X3C CLI flow worked end-to-end ( 🤖 Generated by review-pipeline |
Remove 3 duplicate display-name entries (OptimalLinearArrangement, RuralPostman, LongestCommonSubsequence) introduced by merge conflict in reductions.typ. Add missing should_panic test for duplicate-element validation in X3C constructor. Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
… helper Add load-model-example() Typst function (mirrors load-example() for rules) that loads canonical model examples from generated models.json. Rewrite the ExactCoverBy3Sets problem-def example to derive all concrete values from JSON instead of hand-writing them. Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
- Migrate 28 problem-def example sections in reductions.typ to use load-model-example() instead of hand-written data. All concrete values now derived from models.json via Typst expressions. - Add load-model-example() helper (mirrors load-example() for rules) - Add concrete X3C example to CLI help text and docs/src/cli.md - 10 problems without models.json entries remain hand-written: GraphPartitioning, OptimalLinearArrangement, BinPacking, Knapsack, RuralPostman, SubgraphIsomorphism, LongestCommonSubsequence, SubsetSum, MinimumFeedbackArcSet, FlowShopScheduling Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
Summary
Add the Exact Cover by 3-Sets (X3C) problem as a satisfaction problem model. X3C is a classical NP-complete problem from Garey & Johnson (A3 SP2): given a universe X with |X| = 3q elements and a collection C of 3-element subsets, determine whether C contains a subcollection of q disjoint triples covering every element exactly once.
Fixes #491