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_solution(self.target_problem(), target_solution)?;
26
27        Ok(target_solution.to_vec())
28    }
29}
30
31#[reduction(transform = upper_bound {
32    num_variables = "num_sets",
33    num_equations = "universe_size + 9 * num_sets^2",
34})]
35impl ReduceTo<AlgebraicEquationsOverGF2> for ExactCoverBy3Sets {
36    type Result = ReductionX3CToAlgebraicEquationsOverGF2;
37
38    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
39        let mut sets_per_element = vec![Vec::new(); self.universe_size()];
40        for (set_index, set) in self.sets().iter().enumerate() {
41            for &element in set {
42                sets_per_element[element].push(set_index);
43            }
44        }
45
46        let mut equations = Vec::new();
47        for containing_sets in sets_per_element {
48            let mut linear_equation = containing_sets
49                .iter()
50                .map(|&set_index| vec![set_index])
51                .collect::<Vec<_>>();
52            linear_equation.push(vec![]);
53            equations.push(linear_equation);
54
55            for left in 0..containing_sets.len() {
56                for right in (left + 1)..containing_sets.len() {
57                    equations.push(vec![vec![containing_sets[left], containing_sets[right]]]);
58                }
59            }
60        }
61
62        let target = AlgebraicEquationsOverGF2::new(self.num_sets(), equations).map_err(
63            crate::rules::ReductionError::construction::<
64                ExactCoverBy3Sets,
65                AlgebraicEquationsOverGF2,
66            >,
67        )?;
68        Ok(ReductionX3CToAlgebraicEquationsOverGF2 { target })
69    }
70}
71
72#[cfg(feature = "example-db")]
73pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
74    use crate::export::SolutionPair;
75
76    vec![crate::example_db::specs::RuleExampleSpec {
77        id: "exactcoverby3sets_to_algebraicequationsovergf2",
78        build: || {
79            crate::example_db::specs::rule_example_with_witness::<_, AlgebraicEquationsOverGF2>(
80                ExactCoverBy3Sets::new(6, vec![[0, 1, 2], [3, 4, 5], [0, 3, 4]]),
81                SolutionPair {
82                    source_config: serde_json::json!(vec![true, true, false]),
83                    target_config: serde_json::json!(vec![true, true, false]),
84                },
85            )
86        },
87    }]
88}
89
90#[cfg(test)]
91#[path = "../unit_tests/rules/exactcoverby3sets_algebraicequationsovergf2.rs"]
92mod tests;
problemreductions/rules/exactcoverby3sets_algebraicequationsovergf2.rs

problemreductions/rules/
exactcoverby3sets_algebraicequationsovergf2.rs
