laurent_r

These are some answers to the Week 277, Task 2, 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 July 14, 2024, known in France as Bastille Day, at 23:59). This blog post provides some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

Task 2: Strong Pair

You are given an array of integers, @ints.

Write a script to return the count of all strong pairs in the given array.

A pair of integers x and y is called strong pair if it satisfies: 0 < |x - y| < min(x, y).

Example 1

Input: @ints = (1, 2, 3, 4, 5)
Ouput: 4

Strong Pairs: (2, 3), (3, 4), (3, 5), (4, 5)

Example 2

Input: @ints = (5, 7, 1, 7)
Ouput: 1

Strong Pairs: (5, 7)

We have a slight problem with example 2: since the integer 7 appears twice in the input array, we will find twice the strong pair (5, 7) and the output will be 2, not 1. To solve this issue and obtain the result specified in the example, we will remove duplicates from the input array before we start building the pairs.

Strong Pair in Raku

First, we use the unique method to remove duplicates from the input array, then we use the combinations method to generate all possible pairs. We increment the $count counter for each pair matching the strong pair criteria, and finally return the counter.

sub strong-pairs (@in) {
    my` $count = 0;
    for @in.unique.combinations: 2 -> @pair {
        $count++ if 0 < (@pair[0] - @pair[1]).abs < @pair.min;
    }
    return $count;
}

my @tests = (1, 2, 3, 4, 5), (5, 7, 1, 7);
for @tests -> @test {
    printf "%-10s => ", "@test[]";
    say strong-pairs @test;
}

This program displays the following output:

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

Strong Pair in Perl

This is essentially a port to Perl of the above Raku program. In Perl, the canonical way to remove duplicates is to coerce the input list into a hash and then retrieve the keys of the hash. Then we use two nested for loops to generate all the possible pairs. Next, we increment the $count counter for each pair matching the strong pair criteria, and finally return the counter.

sub strong_pairs {
    my %input = map { $_ => 1 } @_; # remove duplicates
    my @in = keys %input;
    my $count = 0;
    for my $i (0..$#in) {
        for my $j ($i+1..$#in) {
            my $min = $in[$i] < $in[$j] ? $i : $j;
            $count++ if 0 < abs($in[$i] - $in[$j]) and
                abs($in[$i] - $in[$j]) < $in[$min];
        }
    }
    return $count;
}

my @tests = ([1, 2, 3, 4, 5], [5, 7, 1, 7]);
for my $test (@tests) {
    printf "%-10s => ", "@$test";
    say strong_pairs @$test;
}

This program displays the following output:

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

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 July 21, 2024. And, please, also spread the word about the Perl Weekly Challenge if you can.