laurent_r

These are some answers to the Week 243, Task 1, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on November 19, 2023 at 23:59). This blog post offers some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

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

Reverse Pairs in Raku

Although we could possibly use Raku built-in functions such as permutations and combinations, I found that using a doubly nested loop provides a better and finer control on the implementation of the specification of reverse pairs.

sub count-reverse-pairs (@in) {
    my $count = 0;
    for 0..^@in.end -> $i {
        for $i+1..@in.end -> $j {
            $count++ if @in[$i] > 2 * @in[$j];
        }
    }
    return $count;
}

for <1 3 2 3 1>, <2 4 3 5 1> -> @test {
    print "@test[] => ";
    say count-reverse-pairs @test;
}

This program displays the following output:

$ raku ./reverse-pairs.raku
1 3 2 3 1 => 2
2 4 3 5 1 => 3

Reverse Pairs in Perl

This is a port to Perl of the above Raku program.

use strict;
use warnings;
use feature 'say';

sub count_reverse_pairs {
    my @in = @_;
    my $end = $#in;
    my $count = 0;
    for my $i (0..$end-1) {
        for my $j ($i..$end) {
            $count++ if $in[$i] > 2 * $in[$j];
        }
    }
    return $count;
}

for my $test ([qw<1 3 2 3 1>], [qw<2 4 3 5 1>]) {
    print "@$test => ";
    say count_reverse_pairs @$test;
}

This program displays the following output:

$ perl ./reverse-pairs.pl
1 3 2 3 1 => 2
2 4 3 5 1 => 3

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on November 26, 2023. And, please, also spread the word about the Perl Weekly Challenge if you can.