RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved string convolution and array reduction. (Note that this ends today.)

Task 1: Shuffle String

You are given a string and an array of indices of same length as string.

Write a script to return the string after re-arranging the indices in the correct order.

Each entry is the index into the target string: so a entry of 3 at position 0 means "take character 0 from the original, and place it at position 3 in the output".

There are two language features that affect how this problem gets solved. First, are strings casually treated as character arrays? If so (JavaScript, Kotlin, PostScript, Python, Ruby), I can index into them. Otherwise (Lua, Perl, Raku, Rust), I split the string into an array so that I can index into that.

Second, are strings invariant? If they aren't (PostScript, Ruby), then I can build an output string and insert characters into it in arbitrary order. If they are invariant or simply if they aren't casually write-indexable (JavaScript, Kotlin, Lua, Perl, Python, Raku, Rust), I do the same with an array and then combine it.

Rust:

fn shufflestring(st: &str, mp: Vec<usize>) -> String {
    let q = st.chars().collect::<Vec<char>>();
    let mut r = vec![' '; q.len()];
    for (i, ix) in mp.iter().enumerate() {
        r[*ix] = q[i];
    }
    r.iter().collect::<String>()
}

PostScript:

/shufflestring {
    4 dict begin
    /mp exch def
    /st exch def
    /r st length string def
    0 1 mp length 1 sub {
        /ix exch def
        r mp ix get st ix get put
    } for
    r
    end
} bind def

Task 2: Zero Array

You are given an array of non-negative integers, @ints.

Write a script to return the minimum number of operations to make every element equal zero.

In each operation, you are required to pick a positive number less than or equal to the smallest element in the array, then subtract that from each positive element in the array.

One could do this by the iterative process shown, but it's easier to give it some thought and see that that process maps to "always pick the highest possible positive number" and therefore the answer is the number of distinct non-zero values in the input. In other words, we can use a set (where available) or a hash (where not) and it's a very straightforward three-step process, here in Perl:

sub zeroarray($a) {

Turn the array into a set (or hash).

  my %s = map {$_ => 1} @{$a};

Delete set/hash key zero.

  delete $s{0};

Return the number of keys left.

  return scalar keys %s;
}

Full code on github.