problemreductions/rules/
exactcoverby3sets_algebraicequationsovergf2.rs

1//! Reduction from ExactCoverBy3Sets to AlgebraicEquationsOverGF2.
2
3use crate::models::algebraic::AlgebraicEquationsOverGF2;
4use crate::models::set::ExactCoverBy3Sets;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7
8#[derive(Debug, Clone)]
9pub struct ReductionX3CToAlgebraicEquationsOverGF2 {
10    target: AlgebraicEquationsOverGF2,
11}
12
13impl ReductionResult for ReductionX3CToAlgebraicEquationsOverGF2 {
14    type Source = ExactCoverBy3Sets;
15    type Target = AlgebraicEquationsOverGF2;
16
17    fn target_problem(&self) -> &Self::Target {
18        &self.target
19    }
20
21    fn extract_solution(
22        &self,
23        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
24    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
25        crate::rules::traits::validate_target_witness(
26            self.target_problem(),
27            target_solution,
28            |value| value.0,
29            "target witness is not satisfying",
30        )?;
31
32        Ok(target_solution.to_vec())
33    }
34}
35
36#[crate::aggregate_reduction(identity)]
37impl crate::rules::AggregateReductionResult for ReductionX3CToAlgebraicEquationsOverGF2 {}
38
39#[reduction(
40    transform = upper_bound {
41    num_variables = "num_subsets",
42    num_equations = "universe_size + 9 * num_subsets^2",
43})]
44impl ReduceTo<AlgebraicEquationsOverGF2> for ExactCoverBy3Sets {
45    type Result = ReductionX3CToAlgebraicEquationsOverGF2;
46
47    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
48        let mut sets_per_element = vec![Vec::new(); self.universe_size()];
49        for (set_index, set) in self.sets().iter().enumerate() {
50            for &element in set {
51                sets_per_element[element].push(set_index);
52            }
53        }
54
55        let mut equations = Vec::new();
56        for containing_sets in sets_per_element {
57            let mut linear_equation = containing_sets
58                .iter()
59                .map(|&set_index| vec![set_index])
60                .collect::<Vec<_>>();
61            linear_equation.push(vec![]);
62            equations.push(linear_equation);
63
64            for left in 0..containing_sets.len() {
65                for right in (left + 1)..containing_sets.len() {
66                    equations.push(vec![vec![containing_sets[left], containing_sets[right]]]);
67                }
68            }
69        }
70
71        let target = AlgebraicEquationsOverGF2::new(self.num_sets(), equations).map_err(
72            crate::rules::ReductionError::construction::<
73                ExactCoverBy3Sets,
74                AlgebraicEquationsOverGF2,
75            >,
76        )?;
77        Ok(ReductionX3CToAlgebraicEquationsOverGF2 { target })
78    }
79}
80
81#[cfg(feature = "example-db")]
82pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
83    use crate::export::SolutionPair;
84
85    vec![crate::example_db::specs::RuleExampleSpec {
86        id: "exactcoverby3sets_to_algebraicequationsovergf2",
87        build: || {
88            crate::example_db::specs::rule_example_with_witness::<_, AlgebraicEquationsOverGF2>(
89                ExactCoverBy3Sets::new(6, vec![[0, 1, 2], [3, 4, 5], [0, 3, 4]]),
90                SolutionPair {
91                    source_config: serde_json::json!(vec![true, true, false]),
92                    target_config: serde_json::json!(vec![true, true, false]),
93                },
94            )
95        },
96    }]
97}
98
99#[cfg(test)]
100#[path = "../unit_tests/rules/exactcoverby3sets_algebraicequationsovergf2.rs"]
101mod tests;
problemreductions/rules/exactcoverby3sets_algebraicequationsovergf2.rs

problemreductions/rules/
exactcoverby3sets_algebraicequationsovergf2.rs
