**Advent Calendar 2023**

### | **Day 23** | **Day 24** | **Day 25** |

The gift is presented by `Jorg Sommrey`

. Today he is talking about his solution to **The Weekly Challenge - 243**. This is re-produced for `Advent Calendar 2023`

from the original **post**.

## Count the Pairs on the Floor

### Task 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
```

### Solution

Using the `Perl Data Language`

to solve this task.

First we create a `1-d long ndarray`

from the given numbers.

```
$nums = long 1, 3, 2, 3, 1;
```

Then we create a sequence in the same shape as `$nums`

, i.e. a `1-d ndarray`

holding the column indices of `$nums`

and a second sequence as a single column holding the row indices. When combining these index `ndarrays`

, according to `PDL`

's broadcasting rules both will be extended by replicating along a dimension to fit each other. For visualization, these replications may be performed explicitly:

### A) Add a dummy dimension 1 to the row and replicate it five times.

```
say sequence(5)->dup(1, 5);
[
[0 1 2 3 4]
[0 1 2 3 4]
[0 1 2 3 4]
[0 1 2 3 4]
[0 1 2 3 4]
]
```

### B) Replicate dimension 0 of the column five times.

```
say sequence(1, 5)->dup(0, 5);
[
[0 0 0 0 0]
[1 1 1 1 1]
[2 2 2 2 2]
[3 3 3 3 3]
[4 4 4 4 4]
]
```

Hence we get an upper right triangular matrix of ones when comparing the indices:

```
say sequence($nums) > sequence(1, $nums->dim(0));
[
[0 1 1 1 1]
[0 0 1 1 1]
[0 0 0 1 1]
[0 0 0 0 1]
[0 0 0 0 0]
]
```

In the same manner we can compare `$nums`

as a column with itself as a doubled row:

```
say $nums->dummy(0) > 2 * $nums
[
[0 0 0 0 0]
[1 0 0 0 1]
[0 0 0 0 0]
[1 0 0 0 1]
[0 0 0 0 0]
]
```

The `"bit and"`

of both matrices literally follows the definition of reverse pairs. The sum over the and’ed matrices yields the total number of reverse pairs:

```
((sequence($nums) > sequence(1, $nums->dim(0)))
& ($nums->dummy(0) > 2 * $nums))->sum;
```

```
#!/usr/bin/perl -s
use Test2::V0 '!float';
use PDL;
our ($tests, $examples);
run_tests() if $tests || $examples; # does not return
die <<EOS unless @ARGV;
usage: $0 [-examples] [-tests] [--] [N...]
-examples
run the examples from the challenge
-tests
run some tests
N...
list of integers
EOS
### Input and Output
say count_reverse_pairs(@ARGV);
### Implementation
# Count element pairs where $j > $i and $nums[$i] > 2 * $nums[$j].
sub count_reverse_pairs {
my $nums = long @_;
((sequence($nums) > sequence(1, $nums->dim(0)))
& ($nums->dummy(0) > 2 * $nums))->sum;
}
### Examples and tests
sub run_tests {
SKIP: {
skip "examples" unless $examples;
is count_reverse_pairs(1, 3, 2, 3, 1), 2, 'example 1';
is count_reverse_pairs(2, 4, 3, 5, 1), 3, 'example 2';
}
SKIP: {
skip "tests" unless $tests;
is count_reverse_pairs(1, 0, -1), 3, 'zero and negative';
}
done_testing;
exit;
}
```

### Task 2: Floor Sum

```
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
```

### Solution

Again, using `PDL`

.

Creating a `1-d double ndarray`

from the given numbers:

```
$nums = pdl 2, 5, 9;
```

Divide `$nums`

as row by `$nums`

as column in the same manner as in `task 1`

and apply `floor()`

:

```
say floor $nums / $nums->dummy(0);
[
[1 2 4]
[0 1 1]
[0 0 1]
]
```

Finally, sum over this matrix:

```
floor($nums / $nums->dummy(0))->sum;
```

This works not only for positive integers but for all non-zero integers.

```
#!/usr/bin/perl -s
use Test2::V0 '!float';
use PDL;
our ($tests, $examples);
run_tests() if $tests || $examples; # does not return
die <<EOS unless @ARGV;
usage: $0 [-examples] [-tests] [N...]
-examples
run the examples from the challenge
-tests
run some tests
N...
list of positive integers
EOS
### Input and Output
say floor_sum(@ARGV);
### Implementation
# Sum over floor($nums[$i] / $nums[$j]).
sub floor_sum {
my $nums = pdl @_;
floor($nums / $nums->dummy(0))->sum;
}
### Examples and tests
sub run_tests {
SKIP: {
skip "examples" unless $examples;
is floor_sum(2, 5, 9), 10, 'example 1';
is floor_sum(7, 7, 7, 7, 7, 7, 7), 49, 'example 2';
}
SKIP: {
skip "tests" unless $tests;
# floor(3 / (-2)) = -2
# floor((-2) / 3) = -1
is floor_sum(3, -2), -1, 'negative elements';
}
done_testing;
exit;
}
```

If you have any suggestion then please do share with us perlweeklychallenge@yahoo.com.