Perl Weekly Challenge 243.
My solutions (task 1 and task 2 ) to the The Weekly Challenge - 243.
Task 1: Reverse Pairs
Submitted by: Mohammad S Anwar
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
A very simple solution may be obtained with PDL. I make a square
matrix by repeating the row of inputs and masking out the triangular
submatrix with i<j. Then I compare every element to twice
that of the transpose and sum the resulting bits. This allows a
one-liner. The code makes about twice as many comparisons as needed,
the price of its simplicity.
Example 1:
perl -MPDL -E '
$y=pdl(@ARGV)->dummy(1,0+@ARGV); say "@ARGV ->",(($y->xvals<$y->yvals)&($y>2*$y->transpose))->sum
' 1 3 2 3 1
Results:
1 3 2 3 1 ->2
Example 2:
perl -MPDL -E '
$y=pdl(@ARGV)->dummy(1,0+@ARGV); say "@ARGV ->",(($y->xvals<$y->yvals)&($y>2*$y->transpose))->sum
' 2 4 3 5 1
Results:
2 4 3 5 1 ->3
The full code follows:
1 # Perl weekly challenge 243
2 # Task 1: Reverse Pairs
3 #
4 # See https://wlmb.github.io/2023/11/13/PWC243/#task-1-reverse-pairs
5 use v5.36;
6 use PDL;
7 die <<~"FIN" unless @ARGV;
8 Usage: $0 N1 [N2...]
9 to find how many reversed pairs are in the array N1 N2...
10 FIN
11 my $matrix=pdl(@ARGV)->dummy(1,0+@ARGV);
12 say "@ARGV ->",
13 (($matrix->xvals < $matrix->yvals) & ($matrix > 2*$matrix->transpose))->sum;
Examples:
./ch-1.pl 1 3 2 3 1
./ch-1.pl 2 4 3 5 1
Results:
1 3 2 3 1 ->2
2 4 3 5 1 ->3
Task 2: Floor Sum
Submitted by: Mohammad S Anwar
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
This is also soved easily with PDL. I make a square matrix by repeating the input, divide it by its transpose, calculate the floor and sum. I take advantage of the fact that PDL grows size one dimensions as needed to fit the result into a halfliner; I convert a vector into a matrix by adding a size 1 dummy dimension.
Example 1:
perl -MPDL -E '$x=pdl(@ARGV); say "$x -> ", ($x/$x->dummy(0))->floor->sum' 2 5 9
Results:
[2 5 9] -> 10
Example 2
perl -MPDL -E '$x=pdl(@ARGV); say "$x -> ", ($x/$x->dummy(0))->floor->sum' 7 7 7 7 7 7 7
Results:
[7 7 7 7 7 7 7] -> 49
The full code is identical.
1 # Perl weekly challenge 243
2 # Task 2: Floor Sum
3 #
4 # See https://wlmb.github.io/2023/11/13/PWC243/#task-2-floor-sum
5 use v5.36;
6 use PDL;
7 my $in=pdl(@ARGV);
8 say "$in -> ", ($in/$in->dummy(0))->floor->sum;
Examples:
./ch-2.pl 2 5 9
./ch-2.pl 7 7 7 7 7 7 7
Results:
[2 5 9] -> 10
[7 7 7 7 7 7 7] -> 49
/;