ETOOBUSY ðŸš€ minimal blogging for the impatient
PWC085  Triplet Sum
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 that1 < 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 level0, 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 purePerl (which makes it easy to install everywhere) and provides us with an iteratorbased 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.