problemreductions/rules/
numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs

1//! Reduction from Numerical 3-Dimensional Matching to Numerical Matching with Target Sums.
2//!
3//! Given N3DM sets W, X, Y with bound B, keep X and Y unchanged and absorb each
4//! w_i into a target sum B - s(w_i). The only implementation-specific caveat is
5//! that NMTS stores signed `i64` sizes, so copied X/Y sizes and complements must
6//! fit in `i64`.
7
8use crate::models::misc::{Numerical3DimensionalMatching, NumericalMatchingWithTargetSums};
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use std::collections::BTreeMap;
12
13/// Result of reducing Numerical3DimensionalMatching to NumericalMatchingWithTargetSums.
14#[derive(Debug, Clone)]
15pub struct ReductionN3DMToNMTS {
16    target: NumericalMatchingWithTargetSums,
17    source_sizes_w: Vec<i64>,
18    source_bound: i64,
19}
20
21impl ReductionResult for ReductionN3DMToNMTS {
22    type Source = Numerical3DimensionalMatching;
23    type Target = NumericalMatchingWithTargetSums;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        crate::rules::traits::validate_target_witness(
34            self.target_problem(),
35            target_solution,
36            |value| value.0,
37            "target witness does not satisfy the target problem",
38        )?;
39
40        Ok({
41            let mut x_indices_by_pair_sum: BTreeMap<i64, Vec<usize>> = BTreeMap::new();
42            for (x_index, &y_index) in target_solution.iter().enumerate() {
43                let pair_sum = self.target.sizes_x()[x_index]
44                    .checked_add(self.target.sizes_y()[y_index])
45                    .ok_or_else(|| {
46                        crate::rules::ExtractionError::invalid(
47                            "target pair sum overflows the target numeric domain",
48                        )
49                    })?;
50                x_indices_by_pair_sum
51                    .entry(pair_sum)
52                    .or_default()
53                    .push(x_index);
54            }
55
56            let mut x_perm = Vec::with_capacity(self.source_sizes_w.len());
57            let mut y_perm = Vec::with_capacity(self.source_sizes_w.len());
58            for &w_size in &self.source_sizes_w {
59                let target_sum = checked_target_sum(self.source_bound, w_size)
60                    .map_err(crate::rules::ExtractionError::invalid)?;
61                let x_index = x_indices_by_pair_sum
62                    .get_mut(&target_sum)
63                    .and_then(Vec::pop)
64                    .ok_or_else(|| {
65                        crate::rules::ExtractionError::invalid(format!(
66                            "target matching does not realize required pair sum {target_sum}"
67                        ))
68                    })?;
69                x_perm.push(x_index);
70                y_perm.push(target_solution[x_index]);
71            }
72
73            x_perm.extend(y_perm);
74            x_perm
75        })
76    }
77}
78
79fn checked_target_sum(bound: i64, w_size: i64) -> Result<i64, &'static str> {
80    bound
81        .checked_sub(w_size)
82        .ok_or("computing a derived target sum overflowed")
83}
84
85#[crate::aggregate_reduction(identity)]
86impl crate::rules::AggregateReductionResult for ReductionN3DMToNMTS {}
87
88#[reduction(
89    transform = exact {
90        num_pairs = "num_groups",
91    })]
92impl ReduceTo<NumericalMatchingWithTargetSums> for Numerical3DimensionalMatching {
93    type Result = ReductionN3DMToNMTS;
94
95    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
96        let map_error = |message| {
97            crate::rules::ReductionError::invalid_target::<
98                Numerical3DimensionalMatching,
99                NumericalMatchingWithTargetSums,
100            >(message)
101        };
102        let target = NumericalMatchingWithTargetSums::new(
103            self.sizes_x().to_vec(),
104            self.sizes_y().to_vec(),
105            self.sizes_w()
106                .iter()
107                .copied()
108                .map(|w_size| checked_target_sum(self.bound(), w_size))
109                .collect::<Result<_, _>>()
110                .map_err(map_error)?,
111        );
112
113        Ok(ReductionN3DMToNMTS {
114            target,
115            source_sizes_w: self.sizes_w().to_vec(),
116            source_bound: self.bound(),
117        })
118    }
119}
120
121#[cfg(feature = "example-db")]
122pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
123    use crate::export::SolutionPair;
124
125    vec![crate::example_db::specs::RuleExampleSpec {
126        id: "numerical3dimensionalmatching_to_numericalmatchingwithtargetsums",
127        build: || {
128            crate::example_db::specs::rule_example_with_witness::<_, NumericalMatchingWithTargetSums>(
129                Numerical3DimensionalMatching::new(vec![4, 5], vec![4, 5], vec![5, 7], 15),
130                SolutionPair {
131                    source_config: serde_json::json!(vec![0, 1, 1, 0]),
132                    target_config: serde_json::json!(vec![1, 0]),
133                },
134            )
135        },
136    }]
137}
138
139#[cfg(test)]
140#[path = "../unit_tests/rules/numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs"]
141mod tests;
problemreductions/rules/numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs

problemreductions/rules/
numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs
