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.