RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved sets and combinations. (Note that this ends today.)

Since I'm away at the moment I only did this one in Rust. It's my preferred language for solving things these days.

Task 1: Missing Integers

You are given an array of n integers.

Write a script to find all the missing integers in the range 1..n in the given array.

Sets are the obvious way to do this, so I did.

range: the set of numbers that should be present. present: the set of numbers that are present. d: the difference between those sets. Privilege: Raku

fn missingintegers(a: Vec<i32>) -> Vec<i32> {

range is the set of numbers that should be present.

    let range = (1..=a.len() as i32).collect::<HashSet<i32>>();

present is the set of numbers that actually are present.

    let present = a.into_iter().collect::<HashSet<i32>>();

So we take the difference between those two sets,

    let mut b = range.difference(&present).copied().collect::<Vec<i32>>();

Sort it, and return it.

    b.sort_unstable();
    b
}

Task 2: MAD

You are given an array of distinct integers.

Write a script to find all pairs of elements with minimum absolute difference (MAD) of any two elements.

Again, one could work this out in full but using an existing combination generator needs less new code and leaves a function that's easier to understand, if perhaps less efficient..

fn mad(a: Vec<i32>) -> Vec<Vec<i32>> {

Generate all combinations (putting them low value first for convenience in comparison), and

    let mut combs: Vec<Vec<i32>> = Vec::new();
    a.combination(2).for_each(|l| {
        let mut m = l.clone();
        m.sort_unstable();
        combs.push(vec![*m[0], *m[1]]);
    });

Calculate all the differences, and take the minimum.

    let dif = combs.iter().map(|x| x[1] - x[0]).min().unwrap();

Filter the combination list for those that match the minimum.

(This could probably be done more efficiently by keeping a rolling list of the minimum difference value, or by hashing the pairs by difference value and pulling out the lowest-value bucket. If I were doing this in reality, I'd benchmark each approach against the real data.)

    let mut res = combs
        .iter()
        .cloned()
        .filter(|x| x[1] - x[0] == dif)
        .collect::<Vec<Vec<i32>>>();

Sort the results (Rust's sort does the right thing when given a list of lists).

    res.sort_unstable();
    res
}

Full code on github.