Twice as Good with Raku

This is my response to The Weekly Challenge #199.

Challenge #199.1: Good Pairs

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)

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

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

#! /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.

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.

#! /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:

#! /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

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

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)

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.