TL;DR

Here we are with TASK #1 from the Perl Weekly Challenge #085. Enjoy!

# The challenge

You are given an array of real numbers greater than zero. Write a script to find if there exists a triplet (a,b,c) such that 1 < a+b+c < 2. Print 1 if you succeed otherwise 0.

# The questions

This is one of those annoyingly great challenges! Those where youâ€™re too lazy to find an optimized solution, sort of know that you can do better, do some research but still the answers do not apply. So one question might beâ€¦ can we solve 3SUM instead?

I guess the answer will beâ€¦ NO.

OK, fair enough. Legitimate question then:

• should we be wary of corner cases involving the imperfect representation of floating point numbers in computers? Something related to this, for example:
$perl -E 'say 0.1 + 0.2 == 0.3 ? "equal" : "different"' different  • how big is the input list of numbers? In other terms: does it make sense to look for an optimized solution or is it sufficient to give a correct but less scalable one? • (Iâ€™m getting tired of this) how should we treat incorrect inputs? # The solution The very boring, hence good level-0, algorithm that comes to mind is: take every possible subset of three items from the input array, calculate the sum and check against the allowed range. Return 1 as soon as you find a match, return 0 otherwise. Generating all the subsets is a challenge by itself, but I think that in this case we should take extra care to generate only the really needed ones. I mean, if we get a list with 0.5 repeated 10000 times, any three of them will doâ€¦ and we donâ€™t really need to generate all the possible$\binom{10000}{3} = \frac{10000 \cdot 9999 \cdot 9998}{3 \cdot 2} = 166616670000$combinations beforehand, right?!? For this reason, the best here would be to have a way to generate new combinations on the spot, just when they are needed. We need an iterator. Luckily enough, CPAN provides us with Math::Combinatorics: itâ€™s pure-Perl (which makes it easy to install everywhere) and provides us with an iterator-based implementation to get combinations. Yay! This is the solving function:  1 sub triplet_sum { 2 my @R = grep {$_ <= 2.0 } @_; # remove cruft
3    my $combiner = Math::Combinatorics->new(count => 3, data => \@R); 4 while (my ($x, $y,$z) = $combiner->next_combination) { 5$x += $y +$z;
6       return 1 if 1 <= $x &&$x <= 2;
7    }
8    return 0;
9 };


Line 2 collects the input, making sure to keep only the ones that can possibly contribute to a successful sum. This means that everything above 2.0 will get filtered out.

Line 3 creates a Math::Combinatorics object that will be suitable to generate combinations of three items (option count) out of our (filtered) input data @R.

From this point, itâ€™s just a matter of applying our algorithm above:

• take the next triplet (line 4);
• do the sum (line 5);
• check against the target range (line 6).

And until I get an answer to the need for something more efficientâ€¦ Iâ€™ll stick with this solution ðŸ˜‡

The full code, should you be interested into it, is the following:

#!/usr/bin/env perl
use 5.024;
use warnings;
use experimental qw< postderef signatures >;
no warnings qw< experimental::postderef experimental::signatures >;

use FindBin '$Bin'; use lib "$Bin/local/lib/perl5";

use Math::Combinatorics ();

sub triplet_sum {
my @R = grep { $_ <= 2.0 } @_; # remove cruft my$combiner = Math::Combinatorics->new(count => 3, data => \@R);
while (my ($x,$y, $z) =$combiner->next_combination) {
$x +=$y + $z; return 1 if 1 <=$x && \$x <= 2;
}
return 0;
};

my @input = scalar @ARGV ? @ARGV : (0.5, 1.1, 0.3, 0.7);
say triplet_sum(@input);


It assumes that the Math::Combinatorics module is installed in local/lib/perl5 starting from the same position as where the program is saved.

Comments? Octodon, , GitHub, Reddit, or drop me a line!