I’ve been doing the Perl Weekly
Challenges. The
latest
involved searching combinations and integer powers. (Note that this is
open until 8 November 2020.)
Task #1 › Triplet Sum
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
.
This is a job for a combinations library. But lacking that in Perl,
while I could use my standard incrementing counter pattern, this is
specifically for finding three numbers and won't be used for more so
I'll just do nested loops.
sub ts {
my @n=grep {$_ < 2} @_;
foreach my $a (0..$#n-2) {
foreach my $b ($a+1..$#n-1) {
foreach my $c ($b+1..$#n) {
my $s=sum(map {$n[$_]} ($a,$b,$c));
if ($s>1 && $s<2) {
return 1;
}
}
}
}
return 0;
}
There might be room for optimisation by summing $n[$a]
and $n[$b]
first and cacheing the result, particularly if one checked for the sum
exceeding the limit at that point. (And one could then grep the
candidates out of the remaining space rather than summing them
individually.) As an experiment:
sub ts {
my @n=grep {$_ < 2} @_;
foreach my $a (0..$#n-2) {
foreach my $b ($a+1..$#n-1) {
my $s=$n[$a]+$n[$b];
if ($s>=2) {
next;
}
my $sb=2-$s;
my $sa=1-$s;
if (grep {$n[$_]>$sa && $n[$_]<$sb} ($b+1..$#n)) {
return 1;
}
}
}
return 0;
}
This seems to offer roughly a 25% time saving.
All the other languages I'm using do have some kind of combinations
function (which would make the more efficient algorithm more difficult
to implement), so for example in Raku:
sub ts(**@a) {
my @n=grep {$_ < 2}, @a;
for @a.combinations(3) -> @b {
my $s=sum(@b);
if ($s > 1 && $s < 2) {
return 1;
}
}
return 0;
}
and similarly in Python and Ruby. (The grep-block-like function I want
is called find_all
in Ruby. In Python it's a list comprehension of
course.)
Task #2 › Power of Two Integers
You are given a positive integer $N
.
Write a script to find if it can be expressed as a ^ b
where a > 0
and b > 1
. Print 1
if you succeed otherwise 0
.
This came out pretty much the same way in each language. I establish a
list of integers that are candidates for a
(from 2 to the square
root of n
; a=1
is a degenerate case), For each one, I take
log(n)/log(candidate)
(having calculated the former in advance). In
an ideal world, that would be an exact integer if I have a match, but
floating point is floating point and this clearly won't work. Some of
these languages have a ceil
function, but because of floating point
imprecision I just check the integer value of the log quotient and the
same value plus one as potential exponents. Thus Perl:
sub pti {
my $n=shift;
my $l=log($n);
foreach my $ca (2..int(sqrt($n))) {
my $bg=int($l/log($ca));
foreach my $cb ($bg,$bg+1) {
if ($ca ** $cb == $n) {
return 1;
}
}
}
return 0;
}
Similarly in Raku, Python and Ruby.
Full code on github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.