Perl Weekly Challenge: Week 243
Challenge 1:
Reverse Pairs
You are given an array of integers.
Write a script to return the number of reverse pairs in the given array.
A reverse pair is a pair (i, j) where: a) 0 <= i < j < nums.length and b) nums[i] > 2 * nums[j].
Example 1
Input: @nums = (1, 3, 2, 3, 1)
Output: 2
(1, 4) => nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) => nums[3] = 3, nums[4] = 1, 3 > 2 * 1
Example 2
Input: @nums = (2, 4, 3, 5, 1)
Output: 3
(1, 4) => nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) => nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) => nums[3] = 5, nums[4] = 1, 5 > 2 * 1
Raku can do this in one line.
The first part of the code below makes a range of indices of the command-line argument array. Then we find each pair of such
indices with .combinations(). We filter the pairs using .grep() looking for ones where the command-line argument with the index of the first member of the pair is two times the argument with the index of the second member. We count the number of such pairs found with .elems() and print the result with .say().
(0 .. @*ARGS.end).combinations(2).grep({@*ARGS[@$_[0]]>2*@*ARGS[@$_[1]]}).elems.say;
Unfortunately the Perl version is longer because we have to provide our own combinations() function. I cut and pasted the code I've used in many previous weeks challenges.
Armed with this we follow the same plan as in the Raku version albeit more verbosely.
my @nums = @ARGV;
my @indices = 0 .. scalar @nums - 1;
say scalar grep {
my ($i, $j) = @{$_};
$nums[$i] > 2 * $nums[$j];
} combinations(\@indices, 2)
Challenge 2:
Floor Sums
You are given an array of positive integers (>=1).
Write a script to return the sum of floor(nums[i] / nums[j]) where 0 <= i,j < nums.length. The floor() function returns the integer part of the division.
Example 1
Input: @nums = (2, 5, 9)
Output: 10
floor(2 / 5) = 0
floor(2 / 9) = 0
floor(5 / 9) = 0
floor(2 / 2) = 1
floor(5 / 5) = 1
floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1
Example 2
Input: @nums = (7, 7, 7, 7, 7, 7, 7)
Output: 49
Raku one-liner again.
We get the input array from the command-line arguments and create all the combinations of two elements of that array using the
cross-product (X) operator. Then using .map() we find the floor of the first member of the combination divided by the second member for each combination. These results are added together with .sum() and the final answer is printed with .sum().
(@*ARGS X @*ARGS).map({(@$_[0]/@$_[1]).floor}).sum.say
As has so often been the case, we have to do things a little more verbosely for Perl.
my @nums = @ARGV;
my $sum = 0;
This time we are using a double loop to create the cross-product and keeping a running sum as we go.
for my $i (@nums) {
for my $j (@nums) {
$sum += floor($i / $j);
}
}
say $sum;