PWC 226 String Shuffle, Zero Array

Perl Weekly Challenge 226

The weekly challenge goes on. Congratulations to our intrepid administrator Mohammad Sajid Anwar for the award of the White Camel at the Toronto Perl and Raku conference. Well deserved.

Task 1: String Shuffle

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.

Example 1

Input: $string = 'lacelengh', @indices = (3,2,0,5,4,8,6,7,1)
Output: 'challenge'

I am embarrassed at the amount of time I spent understanding the relationship between the input, the indices, and the output. It is quite easy once I saw it: The output is formed by using the indices to select characters from the input. Remembering that array indexing is zero-based, the 3rd character in 'challenge' (the first 'l') comes from position 0 in 'lacelengh'; the 2nd character in 'challenge' (the 'a') comes from position 1 in 'lacelengh'; and so on.

The literal implementation of this mapping can be done by looping over @indices and placing the characters one by one:

my @result;
my @s = split(//, $str);
while ( my ($inIndex, $outIndex) = each @indices )
{
    $result[$outIndex] = $s[$inIndex]
}

The each function is convenient here to give names to both of the values we need from the @indices array.

The way that feels more idiomatically Perl-ish to me, however, is to use an array slice. Indexing an array with an array is a concise statement, with none of the vexing loop issues of array boundaries or side effects from each.

sub shuffleString($str, @indices)
{
    my @result;
    @result[@indices] = split(//, $str);
    return join("", @result);
}

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.

Example 1:

Input: @ints = (1, 5, 0, 3, 5)
Output: 3

operation 1: pick 1 => (0, 4, 0, 2, 4)
operation 2: pick 2 => (0, 2, 0, 0, 2)
operation 3: pick 2 => (0, 0, 0, 0, 0)

Clearly, the best operation for each move will be to subtract the minimum element. If we're lucky, the minimum will be repeated and we can zero more than one element. We could take the instructions literally and manipulate the array, but the number of operations will be the number of unique non-zero elements in the array, and that will be a much more efficient way to get the answer.

If we did want to take the instructions literally, the solution would involve List::Util::min to find the minimum value, and an application of map to do the subtraction. That would be inside a loop controlled by using grep to see if there were any non-zero elements left.

But not today, Satan. This will be a one-liner:

sub zeroArray(@ints)
{
    return scalar(grep { $_ != 0 } uniq @ints);
}

From right to left:

• uniq @ints -- the uniq function comes from List::Util

• grep { $_ != 0 } -- selecting from a list should always ring the bell for applying grep. And grep returns the number of matches, which is what we want.

• scalar(...) -- or does it? The result from grep depends on its context. In scalar context, it returns the number of matches; but in array context, it returns a list of the matching results. When I tested the function, I used say zeroArray(4,7,19) and was momentarily surprised when the output was 4719. Why? Well, say provides array context for the function call and Perl helpfully did the reasonable thing: when in array town, do what the array-ians do. If I always want the scalar result, I had to say so.