RogerBW's Blog

I’ve been doing the Perl Weekly Challenges. The latest involved a lot of nested loops.

Given an array @L of integers. Write a script to find all unique triplets such that a + b + c is same as the given target T. Also make sure a <= b <= c.

Here is wiki page for more information.

Example:

@L = (-25, -10, -7, -3, 2, 4, 8, 10);

One such triplet for target 0 i.e. -10 + 2 + 8 = 0.

A brute-force solution seemed like the simplest approach. One could also hash the inputs and determine whether a suitable third number was present to make the desired sum, but this would involve more complication. (If I had a number list long enough that the iteration time were a concern, I'd use it; this algorithm is something like O(N³).)

@l=sort {$a <=> $b} @l;
my %r;
foreach my $a (0..$#l-2) {
  foreach my $b ($a+1..$#l-1) {
    foreach my $c ($b+1..$#l) {
      if ($l[$a]+$l[$b]+$l[$c]==$t) {
        $r{$l[$a]}{$l[$b]}{$l[$c]}=1;
      }
    }
  }
}

foreach my $d (sort {$a <=> $b} keys %r) {
  foreach my $e (sort {$a <=> $b} keys %{$r{$d}}) {
    foreach my $f (sort {$a <=> $b} keys %{$r{$d}{$e}}) {
      print "$d + $e + $f\n";
    }
  }
}

Perl6 is much the same.

Write a script to display all Colorful Number with 3 digits.

A number can be declare Colorful Number where all the products of consecutive subsets of digit are different.

For example, 263 is a Colorful Number since 2, 6, 3, 2x6, 6x3, 2x6x3 are unique.

There are some obvious optimisations for colourful numbers (no digits 0 or 1, no repeated digits); but most of the numbers that survive that, about one-third, turn out to be colourful, with only a few exceptions (e.g. 236).

foreach my $a (2..9) { # 1?? will never be colourful
  foreach my $b (2..9) { # ?0? and ?1? will never be colourful
    if ($a==$b) {
      next;
    }
    foreach my $c (2..9) { # ??0 and ??1 will never be colourful
      if ($a==$c || $b==$c) {
        next;
      }
      my %p;
      $p{$a}++;
      $p{$b}++;
      $p{$c}++;
      $p{$a*$b}++;
      $p{$b*$c}++;
      $p{$a*$b*$c}++;
      if (max(values %p) < 2) {
        print "$a$b$c\n";
      }
    }
  }
}

One could optimise this slightly by pre-loading and copying %p, and for longer numbers by doing an actual iteration rather than just individual calculations, but again at this scale it's not worth the extra complexity.