RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved filtering pairs and triplets out of a list. (Note that this ends today.)

Task 1: Good Pairs

You are given a list of integers, @list.

Write a script to find the total count of Good Pairs.

A pair (i, j) is called good if list[i] == list[j] and i < j.

The simple, probably naïve, way of doing that is to look at each pair of numbers, either by running the indices oneself or by using a combination generator that does the same thing, and count the ones that match. Here's a Perl version of that, using Algorithm::Combinatorics for the pairing:

sub goodpairs($l) {
  my $c = 0;
  my $i = combinations($l, 2);
  while (my $x = $i->next) {
    if ($x->[0] == $x->[1]) {
      $c++;
    }
  }
  return $c;
}

But this must inevitably be O(n²), and I was sure it could be done more efficiently – for example, by binning the input list into a hash, then for each hash value adding the corresponding triangular number n × (n-1) ÷ 2 to the total (2 adds 1, 3 adds 3, 4 adds 6, 5 adds 10, etc.) So here's that version, the one I actually wrote and submitted, which on a 5,000-element list of random numbers 1..100 runs four orders of magnitude faster, and it's not even significantly longer. (As an extra optimisation I divide by 2 just once at the end. It might be worth looking into cacheing the triangular number values too.)

sub goodpairs($l) {
  my $c = 0;
  my %k;
  map {$k{$_}++} @{$l};
  foreach my $v (values %k) {
    $c += $v * ($v-1);
  }
  return $c / 2;
}

Task 2: Good Triplets

You are given an array of integers, @array and three integers $x,$y,$z.

Write a script to find out total Good Triplets in the given array.

A triplet array[i], array[j], array[k] is good if it satisfies the following conditions:

a) 0 <= i < j < k <= n (size of given array)
b) abs(array[i] - array[j]) <= x
c) abs(array[j] - array[k]) <= y
d) abs(array[i] - array[k]) <= z

No room for optimisations here with those separate constraints, so it's a matter of iterating over (i, j, k) triplets. I can get one short-cut out of this, by skipping the innermost k loop if the (i, j) pair will already fail the test. Kotlin:

fun goodtriplets(a: List<Int>, x: Int, y: Int, z: Int): Int {
    var c = 0
    for (i in 0..a.size-3) {
        for (j in i+1..a.size-2) {
            if (abs(a[i] - a[j]) <= x) {
                for (k in j+1..a.size-1) {
                    if (abs(a[j] - a[k]) <= y &&
                        abs(a[i] - a[k]) <= z) {
                        c += 1
                    }
                }
            }
        }
    }
    return c
}

Full code on github.