RogerBW's Blog

Perl Weekly Challenge 85: Triplet Power 05 November 2020

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.


  1. Posted by RogerBW at 10:01am on 12 November 2020

    For part 1, some people considered the optimisation, others didn't. Some got very baroque…

    For part 2, some people tried factorising. I didn't use that because factorising is computationally expensive, and I find it should only be used if there's no alternative.

    Interestingly, several people considered only prime factors. But what of 36, expressible as 6 ^ 2? I made that mistake last time and so avoided it this time…

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.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1