Duplicates and triplets

Weekly challenge 234 — 11 September 2023

Week 234 - 11 Sep 2023

Task 2

You are given an array of positive integers. Write a script to find the number of triplets (i, j, k) that satisfies num[i] != num[j], num[j] != num[k] and num[k] != num[i].

Example 1Input: @ints = (4, 4, 2, 4, 3) Output: 3 (0, 2, 4) because 4 != 2 != 3 (1, 2, 4) because 4 != 2 != 3 (2, 3, 4) because 2 != 4 != 3Example 2Input: @ints = (1, 1, 1, 1, 1) Output: 0Example 3Input: @ints = (4, 7, 1, 10, 7, 4, 1, 1) Output: 28 triplets of 1, 4, 7 = 3x2×2 = 12 combinations triplets of 1, 4, 10 = 3×2×1 = 6 combinations triplets of 4, 7, 10 = 2×2×1 = 4 combinations triplets of 1, 7, 10 = 3x2x1 = 6 combinations

The requirement is that the three members of the triplet must all have different values,
but if a number is repeated in `@ints`

, then the separate instances
may form separate triplets. For example,
(1, 1, 2, 3) can form
two triplets, (1, 2, 3) and
(1, 2, 3). The ordering within the triplet is not
significant, so for example (1, 2, 3) and
(2, 1, 3) are considered the same triplet.

I therefore chose - as Mohammad has done in the examples - to show the members of each triplet in increasing order, knowing that any other order would merely duplicate one I had already.

My solutions starts with sorting `@ints`

in ascending numerical order.

I then loop over `@ints`

, building:

- an array
`@unique`

of unique values, and - an array
`@count`

of the number of occurrences of these values.

Now I use three nested loops to find every qualifying triplet. As the values are in increasing order, I only need to iterate:

- the first index from 0 to third last position,
- the third index from 2 to the last position, and
- the second index from the first index plus one to the third index minus one.

For each triplet this creates I need to add into the total the product of the
three corresponding `@count`

values. So using example 3 above, there
are three 1s, so every triplet involving 1 happens 3 times and so on.

#!/usr/bin/perl use v5.16; # The Weekly Challenge - 2023-09-11 use utf8; # Week 234 task 2 - Unequal triplets use strict; # Peter Campbell Smith use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge my ($j, @ints); unequal_triplets(4, 4, 4, 2, 3); unequal_triplets(1, 1, 1, 1, 1); unequal_triplets(4, 7, 1, 10, 7, 4, 1, 1); unequal_triplets(-1, 0, 1); unequal_triplets(5, 4, 3); # bigger one for $j (1 .. 9) { push @ints, int(rand(6)); } unequal_triplets(@ints); sub unequal_triplets { my (@ints, $n, $j, $int, @count, @unique, $item1, $item2, $item3, $combs, $i, $explain, $total, $u); # sanity check @ints = sort {$a <=> $b} @_; $n = scalar @ints; return unless $n >= 3; # get unique values and count of each value $j = -1; for $i (0 .. $n - 1) { $j ++ if ($i == 0 or $ints[$i] != $unique[$j]); $unique[$j] = $ints[$i]; $count[$j] ++; } # get combinations $u = scalar @unique; $total = 0; $explain = ''; for $item1 (0 .. $u - 3) { for $item3 (2 .. $u - 1) { for $item2 ($item1 + 1 .. $item3 - 1) { $combs = $count[$item1] * $count[$item2] * $count[$item3]; $total += $combs; $explain .= qq[\n triplet $unique[$item1], $unique[$item2], $unique[$item3] => ] . qq[$count[$item1] * $count[$item2] * $count[$item3] = $combs]; } } } say qq[\nInput: \@ints = (] . join(', ', @_) . ')'; say qq[Output: $total$explain]; }

Input: @ints = (4, 4, 4, 2, 3) Output: 3 triplet 2, 3, 4 => 1 * 1 * 3 = 3 Input: @ints = (1, 1, 1, 1, 1) Output: 0 Input: @ints = (4, 7, 1, 10, 7, 4, 1, 1) Output: 28 triplet 1, 4, 7 => 3 * 2 * 2 = 12 triplet 1, 4, 10 => 3 * 2 * 1 = 6 triplet 1, 7, 10 => 3 * 2 * 1 = 6 triplet 4, 7, 10 => 2 * 2 * 1 = 4 Input: @ints = (-1, 0, 1) Output: 1 triplet -1, 0, 1 => 1 * 1 * 1 = 1 Input: @ints = (5, 4, 3) Output: 1 triplet 3, 4, 5 => 1 * 1 * 1 = 1 Input: @ints = (0, 3, 3, 1, 2, 3, 0, 5, 3) Output: 43 triplet 0, 1, 2 => 2 * 1 * 1 = 2 triplet 0, 1, 3 => 2 * 1 * 4 = 8 triplet 0, 2, 3 => 2 * 1 * 4 = 8 triplet 0, 1, 5 => 2 * 1 * 1 = 2 triplet 0, 2, 5 => 2 * 1 * 1 = 2 triplet 0, 3, 5 => 2 * 4 * 1 = 8 triplet 1, 2, 3 => 1 * 1 * 4 = 4 triplet 1, 2, 5 => 1 * 1 * 1 = 1 triplet 1, 3, 5 => 1 * 4 * 1 = 4 triplet 2, 3, 5 => 1 * 4 * 1 = 4

Peter Campbell Smith is hereby placed in the public domain