I have written a Rust solution of the "Nuts and bolts" problem:
The problem asks to sort two different permutations of the same sequence of integers, but you can only compare one value with the values of the other sequence (so I think in Rust you can't define Ord on the values).
In the end I've not used a tuple, but a more "readable" struct with two named fields, that contain a pair of the first and second sequence. At the end of the program the two fields must contain the same values.
While this code seems to work (I have used design by contracts, unittesting and fuzzying) it has lot of code duplication. In D language I can write code similar to this (representing Pair as a tuple, and indexing its fields with compile-time integers) using just one swap() and one three_way_partition() function. Can I reduce the code duplication in this Rust program? (I am feeling a lack of abstraction power in Rust).
use std::cmp::Ordering;
type Size = u32;
#[derive(Debug, Clone, Copy)] struct Bolt { size: Size }
#[derive(Debug, Clone, Copy)] struct Nut { size: Size }
#[derive(Debug)] struct Pair { n: Nut, b: Bolt }
impl Bolt {
fn compare(&self, other: &Nut) -> Ordering {
self.size.cmp(&other.size)
}
}
impl Nut {
fn compare(&self, other: &Bolt) -> Ordering {
self.size.cmp(&other.size)
}
}
fn swap_nuts(arr: &mut [Pair], i: usize, j: usize) {
// Can't use arr.swap() here.
assert!(i < arr.len() && j < arr.len());
let aux = arr[i].n;
arr[i].n = arr[j].n;
arr[j].n = aux;
}
fn swap_bolts(arr: &mut [Pair], i: usize, j: usize) {
assert!(i < arr.len() && j < arr.len());
let aux = arr[i].b;
arr[i].b = arr[j].b;
arr[j].b = aux;
}
fn three_way_partition_nuts(arr: &mut [Pair], lo: usize, hi: usize, pivot: Bolt)
-> ((usize, usize), (usize, usize), (usize, usize)) {
assert!(lo < arr.len() && hi < arr.len());
if lo >= hi {
return ((0, 0), (0, 0), (0, 0));
}
let mut lt = lo;
let mut gt = hi;
let mut i = lo + 1;
while i <= gt {
let t = arr[i].n;
if t.compare(&pivot) == Ordering::Less {
swap_nuts(arr, lt, i);
lt += 1;
i += 1;
} else if t.compare(&pivot) == Ordering::Greater {
swap_nuts(arr, i, gt);
gt -= 1;
} else {
i += 1;
}
}
((lo, lt), (lt, gt + 1), (gt + 1, hi))
}
fn three_way_partition_bolts(arr: &mut [Pair], lo: usize, hi: usize, pivot: Nut)
-> ((usize, usize), (usize, usize), (usize, usize)) {
assert!(lo < arr.len() && hi < arr.len());
if lo >= hi {
return ((0, 0), (0, 0), (0, 0));
}
let mut lt = lo;
let mut gt = hi;
let mut i = lo + 1;
while i <= gt {
let t = arr[i].b;
if t.compare(&pivot) == Ordering::Less {
swap_bolts(arr, lt, i);
lt += 1;
i += 1;
} else if t.compare(&pivot) == Ordering::Greater {
swap_bolts(arr, i, gt);
gt -= 1;
} else {
i += 1;
}
}
((lo, lt), (lt, gt + 1), (gt + 1, hi))
}
fn inner(arr: &mut [Pair], lo: usize, hi: usize) {
assert!(!arr.is_empty() && hi < arr.len());
if lo >= hi {
return;
}
let pivot1 = arr[lo].b;
for p in lo .. hi + 1 {
if arr[p].n.compare(&pivot1) == Ordering::Equal {
swap_nuts(arr, lo, p);
break;
}
}
let (_, eq0, _) = three_way_partition_nuts(arr, lo, hi, pivot1);
let pivot2 = arr[eq0.0].n;
for p in lo .. hi + 1 {
if arr[p].b.compare(&pivot2) == Ordering::Equal {
swap_bolts(arr, lo, p);
break;
}
}
let (inf1, _, sup1) = three_way_partition_bolts(arr, lo, hi, pivot2);
inner(arr, inf1.0, inf1.1);
inner(arr, sup1.0, sup1.1);
}
fn solve(arr: &mut [Pair]) {
if !arr.is_empty() {
let hi = arr.len() - 1;
inner(arr, 0, hi);
}
}
fn main() {
let nut_sizes = [2, 3, 5, 6, 2, 2, 1, 1, 3, 3];
let bolt_sizes = [1, 3, 2, 2, 3, 3, 6, 5, 2, 1];
let mut pairs = nut_sizes
.iter()
.zip(&bolt_sizes)
.map(|(&s1, &s2)| Pair{ n: Nut{ size: s1 }, b: Bolt{ size: s2 } })
.collect::<Vec<Pair>>();
println!("{:?}\n", pairs);
solve(&mut pairs);
println!("{:?}\n", pairs);
}
This code is mutation-heavy (later I'll write a blog post about this, with more functional alternative versions of the code that mutate less), and there are some invariants to keep in the three-way cross-partition algorithm. So in such code I'd like to use pre-conditions, post-conditions, loop invariants, and loop variants. So for such code I'd like Design by Contract built in Rust (in another version of this program I have used asserts to implement post-conditions, but if your function has more than one exit point, you have to duplicate the asserts or move them in an inner function).
But for me it's less clear...