with Raku

This is my response to The Weekly Challenge #199.

You are given a list of integers,

Write a script to find the total count of

A pair (i, j) is called good if list[i] == list[j] and i < j.

Example 1:

`@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)

The *actual* values are actually irrelevant; all we need is
the frequencies - which we can get with the `Bag`

type:

> <1 2 3 1 1 3>.Bag.raku
(IntStr.new(3, "3")=>2,IntStr.new(1, "1")=>3,IntStr.new(2, "2")=>1).Bag

Those pesky `InsStr`

(ings) are caused by Raku treating the input as both
strings and integers, so that the program can choose whichever type it wants without
resorting to an explicit coercer (a type cast). Coercing the values to integers makes
the output nicer though:

> <1 2 3 1 1 3>>>.Int.Bag.raku
(3=>2,2=>1,1=>3).Bag

The value on the left hand side of `=>`

(called a fat arrow) is the actual
value, and the one on the right is the weight (or frequency).

See
docs.raku.org/type/Bag
for more information about the `Bag`

type.

#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems > 0 && all(@list) ~~ /^<[0..9]>*$/,
:v(:$verbose)); # [1]
my $bag = @list>>.Int.Bag; # [2]
say ": { $bag.raku }" if $verbose;
my $total = 0; # [3]
for $bag.values -> $count # [4]
{
$total += (" " xx $count).combinations(2).elems; # [5]
}
say $total; # [6]

[1] Ensure at least one element, and they must all be non-negative integers. The Challenge does not exclude negative integers, but I have chosen to do so anyway.

[2] Turn the input into a `Bag`

of integers.

[3] The total number of Good Pairs will end up here.

[4] Iterate over the weights (frequencies).

[5]
Make a list containg the weight number of elements (a single
space character), using the list repetition operator `xx`

. Then we use
`combinations(2)`

to get all the combinations with exactly 2 elements.
Then we use `elems`

to count them, giving the number of Good pairs for
this value.

See
docs.raku.org/routine/xx
for more information about the list repetition operator `xx`

.

See
docs.raku.org/routine/combinations
for more information about `combinations`

.

[6] Print the result.

Running it:

$ ./good-pairs 1 2 3 1 1 3
4
$ ./good-pairs 1 1 1 1
6

Verbose mode does not help very much, but it is a start. Of sorts:

$ ./good-pairs -v 1 2 3 1 1 3
: (1=>3,2=>1,3=>2).Bag
4
$ ./good-pairs -v 1 1 1 1
: (1=>4).Bag
6

It is possible to make the program significantly shorter. Here it is as a one-liner (if we disregard the scaffolding):

File: good-pairs-map#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems > 0 && all(@list) ~~ /^<[0..9]>*$/);
say @list.Bag.values.map({ (" " xx $_).combinations(2).elems }).sum;

Running it gives the same result as before:

$ ./good-pairs-map 1 1 1 1
6
$ ./good-pairs-map 1 2 3 1 1 3
4

Verbose mode had to go.

Doing the `combinations`

is cumbersome, and I wondered if it was possible
to get to the values in a simpler (and faster) way.

It is.

File: good-pairs-map-shorter#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems > 0 && all(@list) ~~ /^<[0..9]>*$/);
say @list.Bag.values.map({ (^$_).sum }).sum;

Running it gives the correct answers:

$ ./good-pairs-map-shorter 1 1 1 1
6
$ ./good-pairs-map-shorter 1 2 3 1 1 3
4

If you want proof, this program may help:

File: good-pairs-test#! /usr/bin/env raku
for 1 .. 100 -> $i
{
my $comb = (" " xx $i).combinations(2).elems;
my $sum = (^$i).sum;
say "$i: $comb vs $sum { $comb == $sum ?? "OK" !! "NOT OK" }";
}

You are given an array of integers, @array and three integers

Write a script to find out total

A triplet array[i], array[j], array[k] is good if it satisfies the following conditions:

File: good-triplets
`$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

#! /usr/bin/env raku
unit sub MAIN (Int $x, Int $y, Int $z, *@array # [1]
where @array.elems > 0 && all(@array) ~~ /^<[0..9]>*$/, # [2]
:v(:$verbose));
my $triplets = 0; # [3]
for 0 .. @array.end - 2 -> $i # [4]
{
for $i + 1 .. @array.end - 1 -> $j # [5]
{
for $j + 1 .. @array.end -> $k # [6]
{
next unless abs(@array[$i] - @array[$j]) <= $x; # [7]
next unless abs(@array[$j] - @array[$k]) <= $y; # [7a]
next unless abs(@array[$i] - @array[$k]) <= $z; # [7b]
$triplets++; # [8]
say ": (@array[$i, $j, $k]) where (i=$i, j=$j, k=$k)" if $verbose;
}
}
}
say $triplets; # [9]

[1] [2] Specify the **x**, **y** and **z** values before the array. Note
that the first values are restricted to Integers, and thus can be negative, whilst
the array will only accept non-negative integers. Consider this a feature, caused
by programmer laziness.

[3] The triplet count (not the actual triplets) will end up here.

[4] Iterate over the possible index values for **i**. Note the
end (literally), so that we leave space for **j** and **k**.

See
docs.raku.org/routine/end
for more information about `end`

.

[5] Ditto for **j**. We start just after the current **i** value, and stop
one short off of the end (to leave room for **k**).

[6] Ditto for **k**. You get the index range idea.

[7] Skip the candidate if rule «a» fails, or rule «b» [7a], or rule «c» [7b].

[8] If none of the rules failed, we have a Good Triplet. Add it to the count

[9] Print the number of Good Triplets.

Running it:

$ ./good-triplets 7 2 3 3 0 1 1 9 7
4
$ ./good-triplets 0 0 1 1 1 2 2 3
0

Looking good.

Verbose mode is helpful, this time - when we have matches:

$ ./good-triplets -v 7 2 3 3 0 1 1 9 7
: (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)
4
$ ./good-triplets -v 0 0 1 1 1 2 2 3
0

And that's it.