by Arne Sommer

# Twice as Good with Raku

[219] Published 14. January 2023 (and updated 15. January).

This is my response to The Weekly Challenge #199.

## Challenge #199.1: Good Pairs

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

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.

File: good-pairs ```#! /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 ```

### Update 15. January 2023

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

## Challenge #199.2: 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 ``` 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 ```
File: good-triplets ```#! /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.