1use crate::models::misc::ThreePartition;
9use crate::models::set::ThreeDimensionalMatching;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use std::collections::HashMap;
13
14#[derive(Debug, Clone, Copy)]
15enum Step2Item {
16 A {
17 source_triple: usize,
18 w: usize,
19 x: usize,
20 y: usize,
21 },
22 B {
23 w: usize,
24 first_occurrence: bool,
25 },
26 C {
27 x: usize,
28 first_occurrence: bool,
29 },
30 D {
31 y: usize,
32 first_occurrence: bool,
33 },
34}
35
36#[derive(Debug, Clone, Copy)]
37enum PairingKind {
38 U,
39 UPrime,
40}
41
42#[derive(Debug, Default, Clone, Copy)]
43struct PairUsage {
44 saw_u: bool,
45 uprime_regulars: Option<[usize; 2]>,
46}
47
48#[derive(Debug, Clone)]
50pub struct ReductionThreeDimensionalMatchingToThreePartition {
51 target: ThreePartition,
52 step2_items: Vec<Step2Item>,
53 pair_keys: Vec<(usize, usize)>,
54 num_source_triples: usize,
55}
56
57impl ReductionThreeDimensionalMatchingToThreePartition {
58 fn num_regulars(&self) -> usize {
59 self.step2_items.len()
60 }
61
62 fn pairing_start(&self) -> usize {
63 self.num_regulars()
64 }
65
66 fn filler_start(&self) -> usize {
67 self.pairing_start() + 2 * self.pair_keys.len()
68 }
69
70 fn classify_target_element(&self, element_index: usize) -> TargetElement {
71 if element_index < self.num_regulars() {
72 return TargetElement::Regular {
73 step2_index: element_index,
74 };
75 }
76
77 if element_index < self.filler_start() {
78 let pairing_offset = element_index - self.pairing_start();
79 let pair_index = pairing_offset / 2;
80 let kind = if pairing_offset.is_multiple_of(2) {
81 PairingKind::U
82 } else {
83 PairingKind::UPrime
84 };
85 return TargetElement::Pairing { pair_index, kind };
86 }
87
88 TargetElement::Filler
89 }
90
91 fn decode_real_group(&self, step2_group: [usize; 4]) -> Option<usize> {
92 let mut a_item = None;
93 let mut b_item = None;
94 let mut c_item = None;
95 let mut d_item = None;
96
97 for step2_index in step2_group {
98 match self.step2_items[step2_index] {
99 Step2Item::A {
100 source_triple,
101 w,
102 x,
103 y,
104 } => {
105 a_item = Some((source_triple, w, x, y));
106 }
107 Step2Item::B {
108 w,
109 first_occurrence,
110 } => {
111 b_item = Some((w, first_occurrence));
112 }
113 Step2Item::C {
114 x,
115 first_occurrence,
116 } => {
117 c_item = Some((x, first_occurrence));
118 }
119 Step2Item::D {
120 y,
121 first_occurrence,
122 } => {
123 d_item = Some((y, first_occurrence));
124 }
125 }
126 }
127
128 let (source_triple, aw, ax, ay) = a_item?;
129 let (bw, b_first) = b_item?;
130 let (cx, c_first) = c_item?;
131 let (dy, d_first) = d_item?;
132
133 if aw != bw || ax != cx || ay != dy {
134 return None;
135 }
136
137 if b_first && c_first && d_first {
138 Some(source_triple)
139 } else {
140 None
141 }
142 }
143
144 #[cfg(test)]
145 fn build_target_witness(&self, source_solution: &[usize]) -> Vec<usize> {
146 let mut a_indices = vec![0usize; self.num_source_triples];
147 let mut first_b_by_w = HashMap::new();
148 let mut first_c_by_x = HashMap::new();
149 let mut first_d_by_y = HashMap::new();
150 let mut dummy_bs_by_w: HashMap<usize, Vec<usize>> = HashMap::new();
151 let mut dummy_cs_by_x: HashMap<usize, Vec<usize>> = HashMap::new();
152 let mut dummy_ds_by_y: HashMap<usize, Vec<usize>> = HashMap::new();
153
154 for (step2_index, item) in self.step2_items.iter().copied().enumerate() {
155 match item {
156 Step2Item::A { source_triple, .. } => {
157 a_indices[source_triple] = step2_index;
158 }
159 Step2Item::B {
160 w,
161 first_occurrence,
162 } => {
163 if first_occurrence {
164 first_b_by_w.insert(w, step2_index);
165 } else {
166 dummy_bs_by_w.entry(w).or_default().push(step2_index);
167 }
168 }
169 Step2Item::C {
170 x,
171 first_occurrence,
172 } => {
173 if first_occurrence {
174 first_c_by_x.insert(x, step2_index);
175 } else {
176 dummy_cs_by_x.entry(x).or_default().push(step2_index);
177 }
178 }
179 Step2Item::D {
180 y,
181 first_occurrence,
182 } => {
183 if first_occurrence {
184 first_d_by_y.insert(y, step2_index);
185 } else {
186 dummy_ds_by_y.entry(y).or_default().push(step2_index);
187 }
188 }
189 }
190 }
191
192 let mut step2_groups = Vec::with_capacity(self.num_source_triples);
193 for source_triple in 0..self.num_source_triples {
194 let Step2Item::A { w, x, y, .. } = self.step2_items[a_indices[source_triple]] else {
195 unreachable!("A indices are populated from A items");
196 };
197
198 let group = if source_solution[source_triple] == 1 {
199 [
200 a_indices[source_triple],
201 *first_b_by_w
202 .get(&w)
203 .expect("selected triple must have a first-occurrence B item"),
204 *first_c_by_x
205 .get(&x)
206 .expect("selected triple must have a first-occurrence C item"),
207 *first_d_by_y
208 .get(&y)
209 .expect("selected triple must have a first-occurrence D item"),
210 ]
211 } else {
212 [
213 a_indices[source_triple],
214 dummy_bs_by_w
215 .get_mut(&w)
216 .and_then(|items| items.pop())
217 .expect("unselected triple must have a dummy B item"),
218 dummy_cs_by_x
219 .get_mut(&x)
220 .and_then(|items| items.pop())
221 .expect("unselected triple must have a dummy C item"),
222 dummy_ds_by_y
223 .get_mut(&y)
224 .and_then(|items| items.pop())
225 .expect("unselected triple must have a dummy D item"),
226 ]
227 };
228
229 step2_groups.push(group);
230 }
231
232 let pair_to_index: HashMap<(usize, usize), usize> = self
233 .pair_keys
234 .iter()
235 .copied()
236 .enumerate()
237 .map(|(pair_index, pair)| (pair, pair_index))
238 .collect();
239 let mut pair_used = vec![false; self.pair_keys.len()];
240 let mut target_solution = vec![0usize; self.target.num_elements()];
241 let mut next_group = 0usize;
242
243 for mut step2_group in step2_groups {
244 step2_group.sort_unstable();
245 let pair_key = (step2_group[0], step2_group[1]);
246 let pair_index = *pair_to_index
247 .get(&pair_key)
248 .expect("chosen regular pair must exist in the pairing gadget");
249 pair_used[pair_index] = true;
250
251 let u_index = self.pairing_start() + 2 * pair_index;
252 let uprime_index = u_index + 1;
253
254 target_solution[step2_group[0]] = next_group;
255 target_solution[step2_group[1]] = next_group;
256 target_solution[u_index] = next_group;
257 next_group += 1;
258
259 target_solution[step2_group[2]] = next_group;
260 target_solution[step2_group[3]] = next_group;
261 target_solution[uprime_index] = next_group;
262 next_group += 1;
263 }
264
265 let mut filler_index = self.filler_start();
266 for (pair_index, used) in pair_used.into_iter().enumerate() {
267 if used {
268 continue;
269 }
270
271 let u_index = self.pairing_start() + 2 * pair_index;
272 let uprime_index = u_index + 1;
273 target_solution[u_index] = next_group;
274 target_solution[uprime_index] = next_group;
275 target_solution[filler_index] = next_group;
276 filler_index += 1;
277 next_group += 1;
278 }
279
280 assert_eq!(filler_index, self.target.num_elements());
281 assert_eq!(next_group, self.target.num_groups());
282
283 target_solution
284 }
285}
286
287impl ReductionResult for ReductionThreeDimensionalMatchingToThreePartition {
288 type Source = ThreeDimensionalMatching;
289 type Target = ThreePartition;
290
291 fn target_problem(&self) -> &Self::Target {
292 &self.target
293 }
294
295 fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
298 let mut groups = vec![Vec::new(); self.target.num_groups()];
299 for (element_index, &group_index) in target_solution.iter().enumerate() {
300 groups[group_index].push(element_index);
301 }
302
303 let mut pair_usage: HashMap<(usize, usize), PairUsage> = HashMap::new();
304
305 for members in groups.into_iter().filter(|members| !members.is_empty()) {
306 let mut regulars = Vec::new();
307 let mut pairing = None;
308 let mut has_filler = false;
309
310 for element_index in members {
311 match self.classify_target_element(element_index) {
312 TargetElement::Regular { step2_index } => regulars.push(step2_index),
313 TargetElement::Pairing { pair_index, kind } => {
314 pairing = Some((pair_index, kind))
315 }
316 TargetElement::Filler => has_filler = true,
317 }
318 }
319
320 if has_filler || regulars.len() != 2 {
321 continue;
322 }
323
324 let Some((pair_index, kind)) = pairing else {
325 continue;
326 };
327
328 let pair_key = self.pair_keys[pair_index];
329 let regular_pair = sorted_pair(regulars[0], regulars[1]);
330 let usage = pair_usage.entry(pair_key).or_default();
331
332 match kind {
333 PairingKind::U => {
334 if regular_pair == [pair_key.0, pair_key.1] {
335 usage.saw_u = true;
336 }
337 }
338 PairingKind::UPrime => {
339 usage.uprime_regulars = Some(regular_pair);
340 }
341 }
342 }
343
344 let mut source_solution = vec![0; self.num_source_triples];
345
346 for ((left, right), usage) in pair_usage {
347 let Some(other_two) = usage.uprime_regulars else {
348 continue;
349 };
350 if !usage.saw_u {
351 continue;
352 }
353
354 let mut group = [left, right, other_two[0], other_two[1]];
355 group.sort_unstable();
356 if group.windows(2).any(|window| window[0] == window[1]) {
357 continue;
358 }
359
360 if let Some(source_triple) = self.decode_real_group(group) {
361 source_solution[source_triple] = 1;
362 }
363 }
364
365 source_solution
366 }
367}
368
369#[derive(Debug, Clone, Copy)]
370enum TargetElement {
371 Regular {
372 step2_index: usize,
373 },
374 Pairing {
375 pair_index: usize,
376 kind: PairingKind,
377 },
378 Filler,
379}
380
381fn checked_mul(lhs: u128, rhs: u128, context: &str) -> u128 {
382 lhs.checked_mul(rhs)
383 .unwrap_or_else(|| panic!("{context} overflowed during multiplication"))
384}
385
386fn checked_add(lhs: u128, rhs: u128, context: &str) -> u128 {
387 lhs.checked_add(rhs)
388 .unwrap_or_else(|| panic!("{context} overflowed during addition"))
389}
390
391fn checked_sub(lhs: u128, rhs: u128, context: &str) -> u128 {
392 lhs.checked_sub(rhs)
393 .unwrap_or_else(|| panic!("{context} underflowed during subtraction"))
394}
395
396fn to_u64(value: u128, context: &str) -> u64 {
397 u64::try_from(value).unwrap_or_else(|_| panic!("{context} does not fit into u64"))
398}
399
400fn sorted_pair(a: usize, b: usize) -> [usize; 2] {
401 if a <= b {
402 [a, b]
403 } else {
404 [b, a]
405 }
406}
407
408fn enumerate_pair_keys(num_regulars: usize) -> Vec<(usize, usize)> {
409 let capacity = num_regulars
410 .checked_mul(num_regulars.saturating_sub(1))
411 .and_then(|value| value.checked_div(2))
412 .expect("pair count overflow for 4-Partition gadget");
413 let mut pairs = Vec::with_capacity(capacity);
414 for left in 0..num_regulars {
415 for right in left + 1..num_regulars {
416 pairs.push((left, right));
417 }
418 }
419 pairs
420}
421
422#[reduction(overhead = {
423 num_elements = "24 * num_triples * num_triples - 3 * num_triples",
424 num_groups = "8 * num_triples * num_triples - num_triples",
425})]
426impl ReduceTo<ThreePartition> for ThreeDimensionalMatching {
427 type Result = ReductionThreeDimensionalMatchingToThreePartition;
428
429 fn reduce_to(&self) -> Self::Result {
430 let q = self.universe_size();
431 let t = self.num_triples();
432
433 assert!(q > 0, "3DM -> ThreePartition requires universe_size > 0");
434 assert!(
435 t > 0,
436 "3DM -> ThreePartition requires at least one source triple"
437 );
438
439 let mut covered_w = vec![false; q];
440 let mut covered_x = vec![false; q];
441 let mut covered_y = vec![false; q];
442 for &(w, x, y) in self.triples() {
443 covered_w[w] = true;
444 covered_x[x] = true;
445 covered_y[y] = true;
446 }
447 if covered_w.iter().any(|&covered| !covered)
448 || covered_x.iter().any(|&covered| !covered)
449 || covered_y.iter().any(|&covered| !covered)
450 {
451 return ReductionThreeDimensionalMatchingToThreePartition {
452 target: ThreePartition::new(vec![6, 6, 6, 6, 7, 9], 20),
453 step2_items: Vec::new(),
454 pair_keys: Vec::new(),
455 num_source_triples: t,
456 };
457 }
458
459 let q128 = q as u128;
460 let r = checked_mul(32, q128, "r = 32q");
461 let r2 = checked_mul(r, r, "r^2");
462 let r3 = checked_mul(r2, r, "r^3");
463 let r4 = checked_mul(r3, r, "r^4");
464 let target1 = checked_mul(40, r4, "T1 = 40r^4");
465
466 let mut step2_items = Vec::with_capacity(4 * t);
467 let mut step2_values = Vec::with_capacity(4 * t);
468
469 let mut seen_w = std::collections::HashSet::new();
470 let mut seen_x = std::collections::HashSet::new();
471 let mut seen_y = std::collections::HashSet::new();
472
473 for (source_triple, &(w, x, y)) in self.triples().iter().enumerate() {
474 let w128 = w as u128;
475 let x128 = x as u128;
476 let y128 = y as u128;
477
478 let a_value = checked_sub(
479 checked_sub(
480 checked_sub(
481 checked_mul(10, r4, "A digit"),
482 checked_mul(y128, r3, "A y-term"),
483 "A after y",
484 ),
485 checked_mul(x128, r2, "A x-term"),
486 "A after x",
487 ),
488 checked_mul(w128, r, "A w-term"),
489 "A after w",
490 );
491 step2_values.push(to_u64(
492 checked_add(checked_mul(16, a_value, "step2 A"), 1, "step2 A tag"),
493 "step2 A",
494 ));
495 step2_items.push(Step2Item::A {
496 source_triple,
497 w,
498 x,
499 y,
500 });
501
502 let w_first = seen_w.insert(w);
503 let b_digit = if w_first { 10 } else { 11 };
504 let b_value = checked_add(
505 checked_mul(b_digit, r4, "B digit"),
506 checked_mul(w128, r, "B coordinate"),
507 "B value",
508 );
509 step2_values.push(to_u64(
510 checked_add(checked_mul(16, b_value, "step2 B"), 2, "step2 B tag"),
511 "step2 B",
512 ));
513 step2_items.push(Step2Item::B {
514 w,
515 first_occurrence: w_first,
516 });
517
518 let x_first = seen_x.insert(x);
519 let c_digit = if x_first { 10 } else { 11 };
520 let c_value = checked_add(
521 checked_mul(c_digit, r4, "C digit"),
522 checked_mul(x128, r2, "C coordinate"),
523 "C value",
524 );
525 step2_values.push(to_u64(
526 checked_add(checked_mul(16, c_value, "step2 C"), 4, "step2 C tag"),
527 "step2 C",
528 ));
529 step2_items.push(Step2Item::C {
530 x,
531 first_occurrence: x_first,
532 });
533
534 let y_first = seen_y.insert(y);
535 let d_digit = if y_first { 10 } else { 8 };
536 let d_value = checked_add(
537 checked_mul(d_digit, r4, "D digit"),
538 checked_mul(y128, r3, "D coordinate"),
539 "D value",
540 );
541 step2_values.push(to_u64(
542 checked_add(checked_mul(16, d_value, "step2 D"), 8, "step2 D tag"),
543 "step2 D",
544 ));
545 step2_items.push(Step2Item::D {
546 y,
547 first_occurrence: y_first,
548 });
549 }
550
551 let target2 = checked_add(checked_mul(16, target1, "T2 base"), 15, "T2");
552 let pair_keys = enumerate_pair_keys(step2_values.len());
553
554 let num_fillers = 8usize
555 .checked_mul(t)
556 .and_then(|value| value.checked_mul(t))
557 .and_then(|value| value.checked_sub(3 * t))
558 .expect("filler count overflow");
559
560 let total_elements = step2_values
561 .len()
562 .checked_add(2 * pair_keys.len())
563 .and_then(|value| value.checked_add(num_fillers))
564 .expect("3-Partition element count overflow");
565
566 let mut sizes = Vec::with_capacity(total_elements);
567
568 for &step2_value in &step2_values {
569 let regular = checked_add(
570 checked_mul(
571 4,
572 checked_add(
573 checked_mul(5, target2, "regular base"),
574 u128::from(step2_value),
575 "regular inner",
576 ),
577 "regular outer",
578 ),
579 1,
580 "regular tag",
581 );
582 sizes.push(to_u64(regular, "regular element"));
583 }
584
585 for &(left, right) in &pair_keys {
586 let a_i = u128::from(step2_values[left]);
587 let a_j = u128::from(step2_values[right]);
588
589 let u_value = checked_add(
590 checked_mul(
591 4,
592 checked_sub(
593 checked_mul(6, target2, "u base"),
594 checked_add(a_i, a_j, "u pair sum"),
595 "u inner",
596 ),
597 "u outer",
598 ),
599 2,
600 "u tag",
601 );
602 sizes.push(to_u64(u_value, "pairing u element"));
603
604 let uprime_value = checked_add(
605 checked_mul(
606 4,
607 checked_add(
608 checked_mul(5, target2, "u' base"),
609 checked_add(a_i, a_j, "u' pair sum"),
610 "u' inner",
611 ),
612 "u' outer",
613 ),
614 2,
615 "u' tag",
616 );
617 sizes.push(to_u64(uprime_value, "pairing u' element"));
618 }
619
620 let filler_value = to_u64(checked_mul(20, target2, "filler"), "filler element");
621 sizes.extend(std::iter::repeat_n(filler_value, num_fillers));
622
623 let bound = to_u64(
624 checked_add(
625 checked_mul(64, target2, "3-Partition bound"),
626 4,
627 "3-Partition bound tag",
628 ),
629 "3-Partition bound",
630 );
631
632 ReductionThreeDimensionalMatchingToThreePartition {
633 target: ThreePartition::new(sizes, bound),
634 step2_items,
635 pair_keys,
636 num_source_triples: t,
637 }
638 }
639}
640
641#[cfg(feature = "example-db")]
642pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
643 use crate::export::SolutionPair;
644
645 vec![crate::example_db::specs::RuleExampleSpec {
646 id: "threedimensionalmatching_to_threepartition",
647 build: || {
648 crate::example_db::specs::rule_example_with_witness::<_, ThreePartition>(
649 ThreeDimensionalMatching::new(1, vec![(0, 0, 0)]),
650 SolutionPair {
651 source_config: vec![1],
652 target_config: vec![
653 0, 0, 1, 1, 0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 2, 3, 4, 5, 6,
654 ],
655 },
656 )
657 },
658 }]
659}
660
661#[cfg(test)]
662#[path = "../unit_tests/rules/threedimensionalmatching_threepartition.rs"]
663mod tests;