Peter
Peter Campbell Smith

All good things

Weekly challenge 199 — 9 January 2023

Week 199: 9 Jan 2023

Task 2

Task — 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

Examples


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

Once again it seems inevitable that we perform nested loops:

for $i (0 .. $n - 2) {
    for $j ($i + 1 .. $n - 1) {
        for $k ($j + 1 .. $n) {
            if (abs($array[$i] - $array[$j]) <= $x
            and abs($array[$j] - $array[$k]) <= $y
            and abs($array[$i] - $array[$k]) <= $z) {
                -- we have an answer
            }
        }
    }
}

As before, the for loop limits impose $i < $j < $k and we only need to test the three differences against $x, $y and $z to identify good triplets.

If @array is long then this will be quite time-consuming, but we can optimise the algorithm somewhat because in the loop over $j we can already test for the first of the 'abs' conditions and skip the loop over $k:

for $i (0 .. $n - 2) {
    for $j ($i + 1 .. $n - 1) {
        next unless abs($array[$i] - $array[$j]) <= $x;

        for $k ($j + 1 .. $n) {
            if (abs($array[$j] - $array[$k]) <= $y
            and abs($array[$i] - $array[$k]) <= $z) {
                -- we have an answer
            }
        }
    }
}

Try it 

Try running the script with any input:



example: 3, 0, 1, 1, 9, 7



example: 7, 2, 3

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2023-01-09
# PWC 199 task 2

use v5.28;
use utf8;
use warnings;

# loop over tests
good_triplets(7, 2, 3, [3, 0, 1, 1, 9, 7]);
good_triplets(0, 0, 1, [1, 1, 2, 2, 3]);
good_triplets(1, 2, 1, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]);

sub good_triplets {

    # initialise
    my ($i, $j, $k, @array, $rubric, $count, $max_i, $max_j, $max_k);
    my ($x, $y, $z, $a) = @_;
    @array = @$a;
    $max_k = scalar(@array) - 1;
    $max_j = $max_k - 1;
    $max_i = $max_j - 1;
    
    # loop over i, j, k such that i < j < k
    for $i (0 .. $max_i) {
        for $j ($i + 1 .. $max_j) {
            
            # if this test fails then no need to check $k
            next unless abs($array[$i] - $array[$j]) <= $x;
            
            # apply tests on $k
            for $k ($j + 1 .. $max_k) {
                if (abs($array[$j] - $array[$k]) <= $y and
                    abs($array[$i] - $array[$k]) <= $z) {
                    $rubric .= qq[($array[$i], $array[$j], $array[$k]) where (i = $i, j = $j, k = $k)\n];
                    $count ++;
                }
            }
        }
    }
    
    # output result
    say qq[Input: \@array = (] . join(', ', @array) . qq[), x = $x, y = $y, z = $z];
    say $count ? qq[Output: $count\nGood triplets are:\n$rubric] : qq[Output: 0\n];
}

Output


Input: @array = (3, 0, 1, 1, 9, 7), x = 7, y = 2, z = 3
Output: 4
Good triplets are:
(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)

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

Input: @array = (3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5), x = 1, y = 2, z = 1
Output: 14
Good triplets are:
(3, 4, 2) where (i = 0, j = 2, k = 6)
(3, 4, 3) where (i = 0, j = 2, k = 9)
(3, 2, 3) where (i = 0, j = 6, k = 9)
(1, 1, 2) where (i = 1, j = 3, k = 6)
(4, 5, 5) where (i = 2, j = 4, k = 8)
(4, 5, 3) where (i = 2, j = 4, k = 9)
(4, 5, 5) where (i = 2, j = 4, k = 10)
(4, 5, 3) where (i = 2, j = 8, k = 9)
(4, 5, 5) where (i = 2, j = 8, k = 10)
(4, 3, 5) where (i = 2, j = 9, k = 10)
(5, 6, 5) where (i = 4, j = 7, k = 8)
(5, 6, 5) where (i = 4, j = 7, k = 10)
(5, 5, 5) where (i = 4, j = 8, k = 10)
(6, 5, 5) where (i = 7, j = 8, k = 10)

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain