Not a Bad Couple… And There’s Always Room for One More, Baby

Wherein we ponder the axiom “If it feels good, do it.” And then we go and count the ways.

THE WEEKLY CHALLENGE – PERL & RAKU #199

---

“Too much is always better than not enough!“

—J. R. “Bob” Dobbs

---

Task 1: Good Pairs

Submitted by: Mohammad S Anwar

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.

Example 1

Input: @list = (1,2,3,1,1,3)
Output: 4

There are 4 good pairs found as below:
(0,3)
(0,4)
(3,4)
(2,5)

Example 2

Input: @list = (1,2,3)
Output: 0

Example 3

Input: @list = (1,1,1,1)
Output: 6

Good pairs are below:
(0,1)
(0,2)
(0,3)
(1,2)
(1,3)
(2,3)

ANALYSIS

Today we take on two studies into goodness contained within in lists of numbers: numerological axiology, if you will. As given, the definitions of the two tasks, covering good pairs of numbers and good triplets within a sequence, diverge as the complexity grows.

This in turn will require different approaches, or at least thats the excuse we’re going with in solving the problems in completely different ways. Despite the similarities, when three agents are interacting things always get more complicated. But no judgment — it’s just a simple statement of fact.

METHOD

The “pairs” in question here in the first task are pairs of equal values, expressed as their indices. The definition specifies that the first index be smaller than the second.

What this means is that every pair of equal values found in the input array can be ordered numerically by their indices and this result will constitute a single “good pair”. And further, for completeness, we note that the complement ordering, with the indices swapped, will always fail the condition so that each pairing of indexes of equal value will only be counted once.

The examples given show the actual good pairs found, however we are only asked for the number of such pairings. This can be solved by examination: we iterate through each element in the array and for each start position look at each succeeding element to see if it matches the value. Every time we find a match we increment a counter. Easy peasy. And arguably a bit drab.

Not to say drab simplicity is not a virtue in code. It’s not even very inefficient or anything.

This method looks at each element once in an outer loop, and then, within an inner loop, a sublist based on the initial index that shrinks as we proceed. This all will happen in O(n log n) time complexity. Not terrible at all.

On the other hand, what if we look at the problem combinatorially? If we have, say four 1s present in the list, then each 1 can be paired with each other 1 in another position. This results in n(n-1) combination pairings. But, as we have seen, each pairing will allow us to group the two indices in one of two orderings, of which only one ordering will constitute a “good pair”. Thus we divide the total groupings by 2 to find the number of good pairs.

Count = n(n-1)/2

For this method we need to traverse the list once to assemble a frequency hash of the values within it, then for each value we find, we can compute the count for that value based on its frequency and add that to a total sum. The result will be our final count of good pairs.

As we only traverse the list once, and then following in a separate action traverse the list of values assembled (which will always be equal to or smaller than the list size), the number of calculations performed is maximally twice the length of the original list.

This worst case happens with a list of unique values. However even then the time complexity is still O(n).

Which, you know, is better.

PERL 5 SOLUTION

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';



my @list =  @ARGV;
   @list == 0 and @list = (1,1,1,1);

my (%freq, $count);

$freq{$_}++             for @list;          ## create freq hash
$count += ($_*($_-1))/2 for values %freq;   ## sum for each hash value

say $count;

Task 2: Good Triplets

Submitted by: Mohammad S Anwar

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

Example 1

Input: @array = (3,0,1,1,9,7) and $x = 7, $y = 2, $z = 3
Output: 4

Good Triplets are as below:
(3,0,1) where (i=0, j=1, k=2)
(3,0,1) where (i=0, j=1, k=3)
(3,1,1) where (i=0, j=2, k=3)
(0,1,1) where (i=1, j=2, k=3)

Example 2

Input: @array = (1,1,2,2,3) and $x = 0, $y = 0, $z = 1
Output: 0

ANALYSIS and Observations

For the second version of our challenge, now in 3-D, the novel rule changes don’t allow a simple counting, so we are left with direct examination: three nested loops it is. However, extending our earlier time complexity analysis, each nesting only processes the remaining list length, adding the logarithm to our product. So things don’t really end up ballooning much at all. The counting solution, I have to admit, was more cleverness than anything, although of course it is more efficient, and quite nicely compact.

This, given the small effort applied, is always worth it. It’s good to be simple and succinct, and if you can be clever doing it, well all the better.

With the addition of arbitrary coefficients, though, I do think we’ve lost the plot somehow axiologically, at least with the sense of a pure, inherent, simple and graceful “goodness” that is innately quantifiable, instead finding ourselves descending a slippery slope into a morally relativistic swamp of subjective rationalizations. Messy, like love and life, and arguably all things are.

Hail Satan indeed.

Which brings us back around to: “If it feels good, do it, baby.” Just don’t hurt anyone.

Method

We are given a list and a set of constraits, and need to find out all possible triplets that satisfy our criteria. The way to do that, it appears, is to look through the possiblities and check them. Fortunately the indexes of any valid output sequence must be in ascending order, so out search space is drastically limited from the larger set of all possible permutation 3-element sublists.

So we start at all possible first indexes, then in each case select a candidate second index from those following the first, and then a third from those remaining, following the second. This give us O( n log n (log(log n) ) complexity.

Pretty sure that’s right. It makes my brain hurt a bit and I’m in a hurry.

We will make three loops and check the values we find, with a counter to tally our valid sequences.

Let’s get to it.

Perl 5 Solution

As you can see, the result is a bit more involved, but not what you would call exactly complicated, either. It’s just, as we said, three need loops wrapping a conditional that triggers a counter.

Easy peasy.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


my ($x, $y, $z, @list) =  @ARGV;
say count_trips($x, $y, $z, \@list) if @list;


sub count_trips ( $x, $y, $z, $arr ) {
    my $count = 0;
    
    for my $i ( 0..$arr->$#*-2 ) {
        for my $j ( $i+1..$arr->$#*-1 ) {
            for my $k ( $j+1..$arr->$#* ) {
                $count++ if 
                        abs($arr->[$i]-$arr->[$j]) <= $x 
                    and abs($arr->[$j]-$arr->[$k]) <= $y
                    and abs($arr->[$i]-$arr->[$k]) <= $z ;
            }
        }
    }
    return $count;
}