# RogerBW's Blog

The Weekly Challenge 199: Good N-lets 15 January 2023

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

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;
}
``````

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.