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.

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.