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
-- theuniq
function comes fromList::Util
grep { $_ != 0 }
-- selecting from a list should always ring the bell for applyinggrep
. Andgrep
returns the number of matches, which is what we want.scalar(...)
-- or does it? The result fromgrep
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 usedsay zeroArray(4,7,19)
and was momentarily surprised when the output was4719
. 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.
Top comments (0)