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_solution(self.target_problem(), target_solution)?;
34
35        Ok({
36            let mut x_indices_by_pair_sum: BTreeMap<i64, Vec<usize>> = BTreeMap::new();
37            for (x_index, &y_index) in target_solution.iter().enumerate() {
38                let pair_sum = self.target.sizes_x()[x_index]
39                    .checked_add(self.target.sizes_y()[y_index])
40                    .ok_or_else(|| {
41                        crate::rules::ExtractionError::invalid(
42                            "target pair sum overflows the target numeric domain",
43                        )
44                    })?;
45                x_indices_by_pair_sum
46                    .entry(pair_sum)
47                    .or_default()
48                    .push(x_index);
49            }
50
51            let mut x_perm = Vec::with_capacity(self.source_sizes_w.len());
52            let mut y_perm = Vec::with_capacity(self.source_sizes_w.len());
53            for &w_size in &self.source_sizes_w {
54                let target_sum = checked_target_sum(self.source_bound, w_size)
55                    .map_err(crate::rules::ExtractionError::invalid)?;
56                let x_index = x_indices_by_pair_sum
57                    .get_mut(&target_sum)
58                    .and_then(Vec::pop)
59                    .ok_or_else(|| {
60                        crate::rules::ExtractionError::invalid(format!(
61                            "target matching does not realize required pair sum {target_sum}"
62                        ))
63                    })?;
64                x_perm.push(x_index);
65                y_perm.push(target_solution[x_index]);
66            }
67
68            x_perm.extend(y_perm);
69            x_perm
70        })
71    }
72}
73
74fn checked_target_sum(bound: i64, w_size: i64) -> Result<i64, &'static str> {
75    bound
76        .checked_sub(w_size)
77        .ok_or("computing a derived target sum overflowed")
78}
79
80#[reduction(
81    transform = exact {
82        num_pairs = "num_groups",
83    })]
84impl ReduceTo<NumericalMatchingWithTargetSums> for Numerical3DimensionalMatching {
85    type Result = ReductionN3DMToNMTS;
86
87    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
88        let map_error = |message| {
89            crate::rules::ReductionError::invalid_target::<
90                Numerical3DimensionalMatching,
91                NumericalMatchingWithTargetSums,
92            >(message)
93        };
94        let target = NumericalMatchingWithTargetSums::new(
95            self.sizes_x().to_vec(),
96            self.sizes_y().to_vec(),
97            self.sizes_w()
98                .iter()
99                .copied()
100                .map(|w_size| checked_target_sum(self.bound(), w_size))
101                .collect::<Result<_, _>>()
102                .map_err(map_error)?,
103        );
104
105        Ok(ReductionN3DMToNMTS {
106            target,
107            source_sizes_w: self.sizes_w().to_vec(),
108            source_bound: self.bound(),
109        })
110    }
111}
112
113#[cfg(feature = "example-db")]
114pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
115    use crate::export::SolutionPair;
116
117    vec![crate::example_db::specs::RuleExampleSpec {
118        id: "numerical3dimensionalmatching_to_numericalmatchingwithtargetsums",
119        build: || {
120            crate::example_db::specs::rule_example_with_witness::<_, NumericalMatchingWithTargetSums>(
121                Numerical3DimensionalMatching::new(vec![4, 5], vec![4, 5], vec![5, 7], 15),
122                SolutionPair {
123                    source_config: serde_json::json!(vec![0, 1, 1, 0]),
124                    target_config: serde_json::json!(vec![1, 0]),
125                },
126            )
127        },
128    }]
129}
130
131#[cfg(test)]
132#[path = "../unit_tests/rules/numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs"]
133mod tests;
problemreductions/rules/numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs

problemreductions/rules/
numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs
