laurent_r

These are some answers to the Week 249, 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 December 31, 2023 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 1: Equal Pairs

You are given an array of integers with even number of elements.

Write a script to divide the given array into equal pairs such that:

a) Each element belongs to exactly one pair. b) The elements present in a pair are equal.

Example 1

Input: @ints = (3, 2, 3, 2, 2, 2)
Output: (2, 2), (3, 3), (2, 2)

There are 6 elements in @ints.
They should be divided into 6 / 2 = 3 pairs.
@ints is divided into the pairs (2, 2), (3, 3), and (2, 2) satisfying all the conditions.

Example 2

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

There is no way to divide @ints 2 pairs such that the pairs satisfy every condition.

Equal Pairs in Raku

In Raku, we will first sort the input array and then pick up items from the sorted array two at a time. If they are equal, then we've found a matching pair and store it in the @pairs array; otherwise, the task is impossible for the input data and we can return immediately from the equal-pairs subroutine. If we get to the end of the for loop, then we can just return the @pairs array.

sub equal-pairs (@in) {
    my @pairs;
    for @in.sort -> $a, $b {
        return "()" unless $a == $b;
        push @pairs, ($a, $b);
    }
    return @pairs;
}

for (3, 2, 3, 2, 2, 2), (1, 2, 3, 4) -> @test {
    printf "%-15s => ", "@test[]";
    say equal-pairs @test;
}

This program displays the following output:

$ raku ./equal-pairs.raku
3 2 3 2 2 2     => [(2 2) (2 2) (3 3)]
1 2 3 4         => ()

Equal Pairs in Perl

We'll use a completely different approach in Perl. The equal_pairs subroutine counts the number of occurrences of each integer in the %histo hash. We have no solution and return "()" if any of the frequencies is odd. When a frequency is even (we may have 2 items, but also possibly 4, 6, etc.), we add pairs to the $pairs string until we've exhausted them. Note that I have used here a C-style loop; I do that so rarely that I had to look up the syntax in the documentation (I wasn't sure of the order of the three expressions in the loop header).

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


sub equal_pairs {
    my %histo;
    my $pairs;
    $histo{$_}++ for @_;  # histogram to store frequencies
    for my $key (keys %histo) {
        return "()" if $histo{$key} % 2;
        for (my $i = $histo{$key}; $i > 0; $i -= 2) {
            $pairs .= "($key $key) ";
        }
    }
    return $pairs;
}

for my $test ([3, 2, 3, 2, 2, 2], [1, 2, 3, 4]) {
    printf "%-15s => ", "@$test";
    say equal_pairs @$test;
}

This program displays the following output:

$ perl  ./equal-pairs.pl
3 2 3 2 2 2     => (2 2) (2 2) (3 3)
1 2 3 4         => ()

Note that it would probably simpler, better and more perlish to remove the inner C-style for loop and replace it with something like this:

    for my $key (keys %histo) {
        return "()" if $histo{$key} % 2;
        $pairs .= "($key $key) " x ($histo{$key} / 2);
    }

yielding the same result.

Wrapping up

Season's greetings to everyone. 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 January 7, 2024. And, please, also spread the word about the Perl Weekly Challenge if you can.