problemreductions/rules/

threedimensionalmatching_threepartition.rs

//! Reduction from ThreeDimensionalMatching to ThreePartition.
//!
//! This follows the classical three-step chain:
//! 1. 3DM -> ABCD-Partition
//! 2. ABCD-Partition -> 4-Partition
//! 3. 4-Partition -> 3-Partition

use crate::models::misc::ThreePartition;
use crate::models::set::ThreeDimensionalMatching;
use crate::reduction;
use crate::rules::traits::{ReduceTo, ReductionResult};

#[derive(Debug, Clone, Copy)]
enum Step2Item {
    A {
        source_triple: usize,
        w: usize,
        x: usize,
        y: usize,
    },
    B {
        w: usize,
        first_occurrence: bool,
    },
    C {
        x: usize,
        first_occurrence: bool,
    },
    D {
        y: usize,
        first_occurrence: bool,
    },
}

/// Result of reducing ThreeDimensionalMatching to ThreePartition.
#[derive(Debug, Clone)]
pub struct ReductionThreeDimensionalMatchingToThreePartition {
    target: ThreePartition,
    step2_items: Vec<Step2Item>,
    pair_keys: Vec<(usize, usize)>,
    num_source_triples: usize,
}

impl ReductionThreeDimensionalMatchingToThreePartition {
    fn num_regulars(&self) -> usize {
        self.step2_items.len()
    }

    fn pairing_start(&self) -> usize {
        self.num_regulars()
    }

    fn filler_start(&self) -> usize {
        self.pairing_start() + 2 * self.pair_keys.len()
    }

    fn decode_real_group(&self, step2_group: [usize; 4]) -> Option<usize> {
        let mut a_item = None;
        let mut b_item = None;
        let mut c_item = None;
        let mut d_item = None;

        for step2_index in step2_group {
            match self.step2_items[step2_index] {
                Step2Item::A {
                    source_triple,
                    w,
                    x,
                    y,
                } => {
                    a_item = Some((source_triple, w, x, y));
                }
                Step2Item::B {
                    w,
                    first_occurrence,
                } => {
                    b_item = Some((w, first_occurrence));
                }
                Step2Item::C {
                    x,
                    first_occurrence,
                } => {
                    c_item = Some((x, first_occurrence));
                }
                Step2Item::D {
                    y,
                    first_occurrence,
                } => {
                    d_item = Some((y, first_occurrence));
                }
            }
        }

        let (source_triple, aw, ax, ay) = a_item?;
        let (bw, b_first) = b_item?;
        let (cx, c_first) = c_item?;
        let (dy, d_first) = d_item?;

        if aw != bw || ax != cx || ay != dy {
            return None;
        }

        if b_first && c_first && d_first {
            Some(source_triple)
        } else {
            None
        }
    }

    #[cfg(test)]
    fn build_target_witness(&self, source_solution: &[usize]) -> Vec<usize> {
        use std::collections::HashMap;

        let mut a_indices = vec![0usize; self.num_source_triples];
        let mut first_b_by_w = HashMap::new();
        let mut first_c_by_x = HashMap::new();
        let mut first_d_by_y = HashMap::new();
        let mut dummy_bs_by_w: HashMap<usize, Vec<usize>> = HashMap::new();
        let mut dummy_cs_by_x: HashMap<usize, Vec<usize>> = HashMap::new();
        let mut dummy_ds_by_y: HashMap<usize, Vec<usize>> = HashMap::new();

        for (step2_index, item) in self.step2_items.iter().copied().enumerate() {
            match item {
                Step2Item::A { source_triple, .. } => {
                    a_indices[source_triple] = step2_index;
                }
                Step2Item::B {
                    w,
                    first_occurrence,
                } => {
                    if first_occurrence {
                        first_b_by_w.insert(w, step2_index);
                    } else {
                        dummy_bs_by_w.entry(w).or_default().push(step2_index);
                    }
                }
                Step2Item::C {
                    x,
                    first_occurrence,
                } => {
                    if first_occurrence {
                        first_c_by_x.insert(x, step2_index);
                    } else {
                        dummy_cs_by_x.entry(x).or_default().push(step2_index);
                    }
                }
                Step2Item::D {
                    y,
                    first_occurrence,
                } => {
                    if first_occurrence {
                        first_d_by_y.insert(y, step2_index);
                    } else {
                        dummy_ds_by_y.entry(y).or_default().push(step2_index);
                    }
                }
            }
        }

        let mut step2_groups = Vec::with_capacity(self.num_source_triples);
        for source_triple in 0..self.num_source_triples {
            let Step2Item::A { w, x, y, .. } = self.step2_items[a_indices[source_triple]] else {
                unreachable!("A indices are populated from A items");
            };

            let group = if source_solution[source_triple] == 1 {
                [
                    a_indices[source_triple],
                    *first_b_by_w
                        .get(&w)
                        .expect("selected triple must have a first-occurrence B item"),
                    *first_c_by_x
                        .get(&x)
                        .expect("selected triple must have a first-occurrence C item"),
                    *first_d_by_y
                        .get(&y)
                        .expect("selected triple must have a first-occurrence D item"),
                ]
            } else {
                [
                    a_indices[source_triple],
                    dummy_bs_by_w
                        .get_mut(&w)
                        .and_then(|items| items.pop())
                        .expect("unselected triple must have a dummy B item"),
                    dummy_cs_by_x
                        .get_mut(&x)
                        .and_then(|items| items.pop())
                        .expect("unselected triple must have a dummy C item"),
                    dummy_ds_by_y
                        .get_mut(&y)
                        .and_then(|items| items.pop())
                        .expect("unselected triple must have a dummy D item"),
                ]
            };

            step2_groups.push(group);
        }

        let pair_to_index: HashMap<(usize, usize), usize> = self
            .pair_keys
            .iter()
            .copied()
            .enumerate()
            .map(|(pair_index, pair)| (pair, pair_index))
            .collect();
        let mut pair_used = vec![false; self.pair_keys.len()];
        let mut target_solution = vec![0usize; self.target.num_elements()];
        let mut next_group = 0usize;

        for mut step2_group in step2_groups {
            step2_group.sort_unstable();
            let pair_key = (step2_group[0], step2_group[1]);
            let pair_index = *pair_to_index
                .get(&pair_key)
                .expect("chosen regular pair must exist in the pairing gadget");
            pair_used[pair_index] = true;

            let u_index = self.pairing_start() + 2 * pair_index;
            let uprime_index = u_index + 1;

            target_solution[step2_group[0]] = next_group;
            target_solution[step2_group[1]] = next_group;
            target_solution[u_index] = next_group;
            next_group += 1;

            target_solution[step2_group[2]] = next_group;
            target_solution[step2_group[3]] = next_group;
            target_solution[uprime_index] = next_group;
            next_group += 1;
        }

        let mut filler_index = self.filler_start();
        for (pair_index, used) in pair_used.into_iter().enumerate() {
            if used {
                continue;
            }

            let u_index = self.pairing_start() + 2 * pair_index;
            let uprime_index = u_index + 1;
            target_solution[u_index] = next_group;
            target_solution[uprime_index] = next_group;
            target_solution[filler_index] = next_group;
            filler_index += 1;
            next_group += 1;
        }

        assert_eq!(filler_index, self.target.num_elements());
        assert_eq!(next_group, self.target.num_groups());

        target_solution
    }
}

impl ReductionResult for ReductionThreeDimensionalMatchingToThreePartition {
    type Source = ThreeDimensionalMatching;
    type Target = ThreePartition;

    fn target_problem(&self) -> &Self::Target {
        &self.target
    }

    /// Reverse the 4-Partition -> 3-Partition pairing gadget, then decode the
    /// surviving real ABCD groups back into selected source triples.
    fn extract_solution(
        &self,
        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
        crate::rules::traits::validate_target_witness(
            self.target_problem(),
            target_solution,
            |value| value.0,
            "target assignment is not a feasible 3-partition",
        )?;

        if self.num_source_triples == 0 {
            return Ok(Vec::new());
        }
        let mut groups = vec![Vec::with_capacity(3); self.target.num_groups()];
        let mut positions = Vec::with_capacity(target_solution.len());
        for (element, &group) in target_solution.iter().enumerate() {
            positions.push((group, groups[group].len()));
            groups[group].push(element);
        }

        // Garey--Johnson's reverse construction first normalizes filler triples.
        // Each has two pairing elements whose sum equals that of an original
        // U/UPrime pair. Exchange the second element with the first's mate:
        // they have equal sizes, so both affected triples remain valid. A mate
        // cannot belong to an already normalized filler triple unless it is
        // already here, so each iteration permanently normalizes one triple.
        // Initial index order puts regulars first and fillers last; exchanges
        // only move pairing elements, preserving those positions.
        let pairing_start = self.pairing_start();
        for filler in self.filler_start()..target_solution.len() {
            let (group, _) = positions[filler];
            let first = groups[group][0];
            let second = groups[group][1];
            let mate = pairing_start + ((first - pairing_start) ^ 1);
            let (mate_group, mate_slot) = positions[mate];
            groups[group][1] = mate;
            groups[mate_group][mate_slot] = second;
            positions[mate] = (group, 1);
            positions[second] = (mate_group, mate_slot);
        }

        let mut source_solution = vec![false; self.num_source_triples];
        for first in (pairing_start..self.filler_start()).step_by(2) {
            let (left, _) = positions[first];
            if groups[left][0] >= pairing_start {
                continue; // This complete pair is used by a filler triple.
            }
            let (right, _) = positions[first + 1];
            // Use the actual regular elements, not the pair's construction
            // indices: equal-valued pairing elements are interchangeable.
            let regulars = [
                groups[left][0],
                groups[left][1],
                groups[right][0],
                groups[right][1],
            ];
            if let Some(source_triple) = self.decode_real_group(regulars) {
                source_solution[source_triple] = true;
            }
        }
        Ok(source_solution)
    }
}

fn enumerate_pair_keys(num_regulars: usize) -> Option<Vec<(usize, usize)>> {
    let capacity = num_regulars
        .checked_mul(num_regulars.saturating_sub(1))
        .and_then(|value| value.checked_div(2))?;
    let mut pairs = Vec::with_capacity(capacity);
    for left in 0..num_regulars {
        for right in left + 1..num_regulars {
            pairs.push((left, right));
        }
    }
    Some(pairs)
}

#[crate::aggregate_reduction(identity)]
impl crate::rules::AggregateReductionResult for ReductionThreeDimensionalMatchingToThreePartition {}

#[reduction(
    transform = upper_bound {
        // B=64*(16*40*(32q)^4+15)+4; fixed YES/NO bounds are 3/20.
        bound = "40960 * (32 * universe_size)^4 + 964",
        max_numeric_magnitude_bits = "4 * universe_size + 36",
        num_elements = "24 * num_triples * num_triples - 3 * num_triples + 6",
        num_groups = "8 * num_triples * num_triples - num_triples + 2",
    })]
impl ReduceTo<ThreePartition> for ThreeDimensionalMatching {
    type Result = ReductionThreeDimensionalMatchingToThreePartition;

    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
        let q = self.universe_size();
        let t = self.num_triples();

        if q == 0 {
            // The empty matching covers the empty universe.
            return Ok(ReductionThreeDimensionalMatchingToThreePartition {
                target: ThreePartition::new(vec![1, 1, 1], 3),
                step2_items: Vec::new(),
                pair_keys: Vec::new(),
                num_source_triples: 0,
            });
        }

        let mut covered_w = vec![false; q];
        let mut covered_x = vec![false; q];
        let mut covered_y = vec![false; q];
        for &(w, x, y) in self.triples() {
            covered_w[w] = true;
            covered_x[x] = true;
            covered_y[y] = true;
        }
        if covered_w.iter().any(|&covered| !covered)
            || covered_x.iter().any(|&covered| !covered)
            || covered_y.iter().any(|&covered| !covered)
        {
            return Ok(ReductionThreeDimensionalMatchingToThreePartition {
                target: ThreePartition::new(vec![6, 6, 6, 6, 7, 9], 20),
                step2_items: Vec::new(),
                pair_keys: Vec::new(),
                num_source_triples: t,
            });
        }

        let arithmetic_overflow = |context| {
            crate::rules::ReductionError::integer_overflow::<ThreeDimensionalMatching, ThreePartition>(
                context,
            )
        };
        let q = i64::try_from(q).map_err(|_| arithmetic_overflow("converting q to i64"))?;
        let r = 32_i64
            .checked_mul(q)
            .ok_or_else(|| arithmetic_overflow("computing r = 32q"))?;
        let r2 = r
            .checked_mul(r)
            .ok_or_else(|| arithmetic_overflow("computing r^2"))?;
        let r3 = r2
            .checked_mul(r)
            .ok_or_else(|| arithmetic_overflow("computing r^3"))?;
        let r4 = r3
            .checked_mul(r)
            .ok_or_else(|| arithmetic_overflow("computing r^4"))?;
        let target1 = 40_i64
            .checked_mul(r4)
            .ok_or_else(|| arithmetic_overflow("computing the ABCD-Partition target"))?;

        let mut step2_items = Vec::with_capacity(4 * t);
        let mut step2_values = Vec::with_capacity(4 * t);

        let mut seen_w = std::collections::HashSet::new();
        let mut seen_x = std::collections::HashSet::new();
        let mut seen_y = std::collections::HashSet::new();

        for (source_triple, &(w, x, y)) in self.triples().iter().enumerate() {
            let w_num = i64::try_from(w).map_err(|_| arithmetic_overflow("converting w to i64"))?;
            let x_num = i64::try_from(x).map_err(|_| arithmetic_overflow("converting x to i64"))?;
            let y_num = i64::try_from(y).map_err(|_| arithmetic_overflow("converting y to i64"))?;

            let a_value = 10_i64
                .checked_mul(r4)
                .and_then(|value| value.checked_sub(y_num.checked_mul(r3)?))
                .and_then(|value| value.checked_sub(x_num.checked_mul(r2)?))
                .and_then(|value| value.checked_sub(w_num.checked_mul(r)?))
                .ok_or_else(|| arithmetic_overflow("computing an A item"))?;
            let step2_a = 16_i64
                .checked_mul(a_value)
                .and_then(|value| value.checked_add(1))
                .ok_or_else(|| arithmetic_overflow("encoding an A item"))?;
            step2_values.push(step2_a);
            step2_items.push(Step2Item::A {
                source_triple,
                w,
                x,
                y,
            });

            let w_first = seen_w.insert(w);
            let b_digit: i64 = if w_first { 10 } else { 11 };
            let b_value = b_digit
                .checked_mul(r4)
                .and_then(|value| value.checked_add(w_num.checked_mul(r)?))
                .ok_or_else(|| arithmetic_overflow("computing a B item"))?;
            let step2_b = 16_i64
                .checked_mul(b_value)
                .and_then(|value| value.checked_add(2))
                .ok_or_else(|| arithmetic_overflow("encoding a B item"))?;
            step2_values.push(step2_b);
            step2_items.push(Step2Item::B {
                w,
                first_occurrence: w_first,
            });

            let x_first = seen_x.insert(x);
            let c_digit: i64 = if x_first { 10 } else { 11 };
            let c_value = c_digit
                .checked_mul(r4)
                .and_then(|value| value.checked_add(x_num.checked_mul(r2)?))
                .ok_or_else(|| arithmetic_overflow("computing a C item"))?;
            let step2_c = 16_i64
                .checked_mul(c_value)
                .and_then(|value| value.checked_add(4))
                .ok_or_else(|| arithmetic_overflow("encoding a C item"))?;
            step2_values.push(step2_c);
            step2_items.push(Step2Item::C {
                x,
                first_occurrence: x_first,
            });

            let y_first = seen_y.insert(y);
            let d_digit: i64 = if y_first { 10 } else { 8 };
            let d_value = d_digit
                .checked_mul(r4)
                .and_then(|value| value.checked_add(y_num.checked_mul(r3)?))
                .ok_or_else(|| arithmetic_overflow("computing a D item"))?;
            let step2_d = 16_i64
                .checked_mul(d_value)
                .and_then(|value| value.checked_add(8))
                .ok_or_else(|| arithmetic_overflow("encoding a D item"))?;
            step2_values.push(step2_d);
            step2_items.push(Step2Item::D {
                y,
                first_occurrence: y_first,
            });
        }

        let target2 = 16_i64
            .checked_mul(target1)
            .and_then(|value| value.checked_add(15))
            .ok_or_else(|| arithmetic_overflow("computing the 4-Partition target"))?;
        let pair_keys = enumerate_pair_keys(step2_values.len())
            .ok_or_else(|| arithmetic_overflow("computing the 4-Partition pair count"))?;

        let subtract_fillers =
            3usize.checked_mul(t).ok_or_else(|| {
                crate::rules::ReductionError::integer_overflow::<
                    ThreeDimensionalMatching,
                    ThreePartition,
                >("computing the filler count")
            })?;
        let num_fillers = 8usize
            .checked_mul(t)
            .and_then(|value| value.checked_mul(t))
            .and_then(|value| value.checked_sub(subtract_fillers))
            .ok_or_else(|| {
                crate::rules::ReductionError::integer_overflow::<
                    ThreeDimensionalMatching,
                    ThreePartition,
                >("computing the filler count")
            })?;

        let pair_elements =
            2usize.checked_mul(pair_keys.len()).ok_or_else(|| {
                crate::rules::ReductionError::integer_overflow::<
                    ThreeDimensionalMatching,
                    ThreePartition,
                >("computing the number of pair elements")
            })?;
        let total_elements = step2_values
            .len()
            .checked_add(pair_elements)
            .and_then(|value| value.checked_add(num_fillers))
            .ok_or_else(|| {
                crate::rules::ReductionError::integer_overflow::<
                    ThreeDimensionalMatching,
                    ThreePartition,
                >("computing the target element count")
            })?;

        let mut sizes = Vec::with_capacity(total_elements);

        for &step2_value in &step2_values {
            let regular = 5_i64
                .checked_mul(target2)
                .and_then(|value| value.checked_add(step2_value))
                .and_then(|value| value.checked_mul(4))
                .and_then(|value| value.checked_add(1))
                .ok_or_else(|| arithmetic_overflow("computing a regular element"))?;
            sizes.push(regular);
        }

        for &(left, right) in &pair_keys {
            let pair_sum = step2_values[left]
                .checked_add(step2_values[right])
                .ok_or_else(|| arithmetic_overflow("summing paired 4-Partition elements"))?;
            let u_value = 6_i64
                .checked_mul(target2)
                .and_then(|value| value.checked_sub(pair_sum))
                .and_then(|value| value.checked_mul(4))
                .and_then(|value| value.checked_add(2))
                .ok_or_else(|| arithmetic_overflow("computing a pairing u element"))?;
            sizes.push(u_value);

            let uprime_value = 5_i64
                .checked_mul(target2)
                .and_then(|value| value.checked_add(pair_sum))
                .and_then(|value| value.checked_mul(4))
                .and_then(|value| value.checked_add(2))
                .ok_or_else(|| arithmetic_overflow("computing a pairing u' element"))?;
            sizes.push(uprime_value);
        }

        let filler_value = 20_i64
            .checked_mul(target2)
            .ok_or_else(|| arithmetic_overflow("computing a filler element"))?;
        sizes.extend(std::iter::repeat_n(filler_value, num_fillers));

        let bound = 64_i64
            .checked_mul(target2)
            .and_then(|value| value.checked_add(4))
            .ok_or_else(|| arithmetic_overflow("computing the 3-Partition bound"))?;

        Ok(ReductionThreeDimensionalMatchingToThreePartition {
            target: ThreePartition::try_new(sizes, bound)
                .map_err(<Self as ReduceTo<ThreePartition>>::target_construction)?,
            step2_items,
            pair_keys,
            num_source_triples: t,
        })
    }
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
    use crate::export::SolutionPair;

    vec![crate::example_db::specs::RuleExampleSpec {
        id: "threedimensionalmatching_to_threepartition",
        build: || {
            crate::example_db::specs::rule_example_with_witness::<_, ThreePartition>(
                ThreeDimensionalMatching::new(1, vec![(0, 0, 0)]),
                SolutionPair {
                    source_config: serde_json::json!(vec![true]),
                    target_config: serde_json::json!(vec![
                        0, 0, 1, 1, 0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 2, 3, 4, 5, 6,
                    ]),
                },
            )
        },
    }]
}

#[cfg(test)]
#[path = "../unit_tests/rules/threedimensionalmatching_threepartition.rs"]
mod tests;