laurent_r

These are some answers to the Week 290, 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 October 13, 2024, 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: Double Exist

You are given an array of integers, @ints.

Write a script to find if there exist two indices $i and $j such that:

1) $i != $j
2) 0 <= ($i, $j) < scalar @ints
3) $ints[$i] == 2 * $ints[$j]

Example 1

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

For $i = 0, $j = 2
$ints[$i] = 6 => 2 * 3 =>  2 * $ints[$j]

Example 2

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

Example 3

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

For $i = 2, $j = 3
$ints[$i] = 4 => 2 * 2 =>  2 * $ints[$j]

I initially didn't understand condition (2). This ($i, $j) expression didn't make sense to me, until I understood that it meant that both $i and $j have to be greater than or equal to zero, and smaller than the number of items in the array.

Note that the first condition, $i != $j, is unnecessary since, if $i == $j, then we cannot meet condition (3), $ints[$i] == 2 * $ints[$j]. Well, that is except if the value is 0, but zeros should be avoided anyway because we could have 0 = 2 * 0, which is technically true, but that's not really the meaning of the task. I'll therefore consider that the input should be an array of non-zero integers because what we should do with the zero special case is unclear and not specified in the task. Thus, there is no need to check condition (1) in our code (this applies only to the Perl implementation, as we don't have this issue with the Raku implementation).

Double Exist in Raku

In Raku, the built-in combinations routine make it possible to generate automatically all combinations of two items of an array. Combinations are unordered. In other words, with an input such as <1 2 3>, the combinations method will generate the following combinations: (1 2) (1 3) (2 3), but not (2, 1), (3, 1), or (3, 2). Therefore, for each combination, we need to compare both ways: is the first item the double of the second, and is the second item the double of the first.

sub double-exists (@in) {
    for @in.combinations: 2 -> $comb {
        return True if $comb[0] == 2 * $comb[1] or 
            $comb[1] == 2 * $comb[0];
    }
    False;
}

my @tests = <1 2 3 4>, <6 2 3 3>, <3 1 4 13>, <2 1 4 2>;
for @tests -> @test {
    printf "%-10s => ", "@test[]";
    say double-exists @test;
}

This program displays the following output:

$ raku ./double-exists.raku
1 2 3 4    => True
6 2 3 3    => True
3 1 4 13   => False
2 1 4 2    => True

Double Exist in Perl

Perl doesn't have a built-in combinations subroutine, so we will apply the canonical method of generating them (as well as those reversing the value order) using two nested loops. Please read my comments at the beginning of this post concerning the first condition ($i != $j) and the need to avoid zero values in the input. If you disagree with my view, it is very easy to add a code list such as:

next if $i == $j;

in the inner loop of the code below.

sub double_exists {
    for my $i (0..$#_) {
        for my $j (0..$#_) {
            return "True" if $_[$i] == 2 * $_[$j];
        }
    }
    return "False";
}

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

This program displays the following output:

$ perl ./double-exists.pl
1 2 3 4    => True
6 2 3 3    => True
3 1 4 13   => False
2 1 4 2    => True

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