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<u64>,
18    source_bound: u64,
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(&self, target_solution: &[usize]) -> Vec<usize> {
30        let mut x_indices_by_pair_sum: BTreeMap<i64, Vec<usize>> = BTreeMap::new();
31        for (x_index, &y_index) in target_solution.iter().enumerate() {
32            let pair_sum = self.target.sizes_x()[x_index]
33                .checked_add(self.target.sizes_y()[y_index])
34                .expect("NMTS witness must not overflow i64 pair sums");
35            x_indices_by_pair_sum
36                .entry(pair_sum)
37                .or_default()
38                .push(x_index);
39        }
40
41        let mut x_perm = Vec::with_capacity(self.source_sizes_w.len());
42        let mut y_perm = Vec::with_capacity(self.source_sizes_w.len());
43        for &w_size in &self.source_sizes_w {
44            let target_sum = checked_target_sum_to_i64(self.source_bound, w_size);
45            let x_index = x_indices_by_pair_sum
46                .get_mut(&target_sum)
47                .and_then(Vec::pop)
48                .expect("satisfying NMTS witness must realize every target complement");
49            x_perm.push(x_index);
50            y_perm.push(target_solution[x_index]);
51        }
52
53        x_perm.extend(y_perm);
54        x_perm
55    }
56}
57
58fn checked_size_to_i64(size: u64) -> i64 {
59    i64::try_from(size).expect(
60        "Numerical3DimensionalMatching -> NumericalMatchingWithTargetSums requires X/Y sizes to fit in i64",
61    )
62}
63
64fn checked_target_sum_to_i64(bound: u64, w_size: u64) -> i64 {
65    let target_sum = bound
66        .checked_sub(w_size)
67        .expect("N3DM invariants require each w_i to be strictly smaller than B");
68    i64::try_from(target_sum).expect(
69        "Numerical3DimensionalMatching -> NumericalMatchingWithTargetSums requires each complement B - s(w_i) to fit in i64",
70    )
71}
72
73#[reduction(overhead = {
74    num_pairs = "num_groups",
75})]
76impl ReduceTo<NumericalMatchingWithTargetSums> for Numerical3DimensionalMatching {
77    type Result = ReductionN3DMToNMTS;
78
79    fn reduce_to(&self) -> Self::Result {
80        let target = NumericalMatchingWithTargetSums::new(
81            self.sizes_x()
82                .iter()
83                .copied()
84                .map(checked_size_to_i64)
85                .collect(),
86            self.sizes_y()
87                .iter()
88                .copied()
89                .map(checked_size_to_i64)
90                .collect(),
91            self.sizes_w()
92                .iter()
93                .copied()
94                .map(|w_size| checked_target_sum_to_i64(self.bound(), w_size))
95                .collect(),
96        );
97
98        ReductionN3DMToNMTS {
99            target,
100            source_sizes_w: self.sizes_w().to_vec(),
101            source_bound: self.bound(),
102        }
103    }
104}
105
106#[cfg(feature = "example-db")]
107pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
108    use crate::export::SolutionPair;
109
110    vec![crate::example_db::specs::RuleExampleSpec {
111        id: "numerical3dimensionalmatching_to_numericalmatchingwithtargetsums",
112        build: || {
113            crate::example_db::specs::rule_example_with_witness::<_, NumericalMatchingWithTargetSums>(
114                Numerical3DimensionalMatching::new(vec![4, 5], vec![4, 5], vec![5, 7], 15),
115                SolutionPair {
116                    source_config: vec![0, 1, 1, 0],
117                    target_config: vec![1, 0],
118                },
119            )
120        },
121    }]
122}
123
124#[cfg(test)]
125#[path = "../unit_tests/rules/numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs"]
126mod tests;
problemreductions/rules/numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs

problemreductions/rules/
numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs
