String the Gap
with Raku

by Arne Sommer

String the Gap with Raku

[122] Published 4. April 2021.

This is my response to the Perl Weekly Challenge #106.

Challenge #106.1: Maximum Gap

You are given an array of integers @N.

Write a script to display the maximum difference between two successive elements once the array is sorted.

If the array contains only 1 element then display 0.

Example:
Input: @N = (2, 9, 3, 5)
Output: 4

Input: @N = (1, 3, 8, 2, 0)
Output: 5

Input: @N = (5)
Output: 0

Let us do this in two steps. The first is generating the pairs (after sorting the values), and the second is computing the differences (and choosing the largest).

File: maximum-gap
#! /usr/bin/env raku

multi sub MAIN (*@N where @N.elems == 1, :v($verbose))   # [1]
{
  say 0;
}

multi sub MAIN (*@N where @N.elems > 1 && all(@N) ~~ Int, :v($verbose))  # [2]
{
  my @pairs = all-pairs(@N.sort, $verbose);              # [3]

  say ": Pairs: { @pairs.raku }" if $verbose;

  say @pairs>>.reduce(&difference).max;                  # [12]
}

sub all-pairs (@list is copy, $verbose)                  # [3a]
{
  my $first = @list.shift;                               # [4]
  my $second;                                            # [5]
  my @result;                                            # [6]

  while (@list)                                          # [7]
  {
    $second = @list.shift;                               # [8]

    @result.push: ($first.Int => $second.Int);           # [9]

    say ": Added Pair: $first -> $second" if $verbose;

    $first = $second;                                    # [10]
  }

  return @result;                                        # [11]
}

sub difference (Pair $p)                                 # [13]
{
  return abs( $p.key - $p.value );                       # [13a]
}

[1] This version of the programs kicks in if we give it one argument only (regardless of the type), printing 0.

[2] This version kicks in if we give it more than one argument, and all of them must be integers.

[3] Sort the input list (with .sort), and pass it on to the «all-pairs» procedure to get all the pairs. Note the is copy in [3a], so that we can modify the array (in [4]).

[4] Get the first value (of a pair).

[5] The second value of the pairs go here.

[6] The resulting pairs go here.

[7] As long as we have more items.

[8] Get the new second value.

[9] Create a Pair object with the two values (the fat arrow => is the Pair constructor), and add it to the list.

IntStr as a Red Herring

Note the coercion to Int. The input originates from the command line and is of the IntStr type. The sort call (in [3]) got it right, and it is still ok here (and indeed in the subtraction in [12a]). The problem is that the Pair construction does not set up a new variable, but uses the current container (i.e. $second), so that when we change that one later on - we change them all. And end up with a wrong result.

Without the .Int coercers in [9]:

 ./maximum-gap-ERROR -v 22 122 1
: Added Pair: 1 -> 22
: Added Pair: 22 -> 122
: Pairs: [IntStr.new(1,  "1")  => IntStr.new(122, "122"),
          IntStr.new(22, "22") => IntStr.new(122, "122")]
121

With them:

$ ./maximum-gap -v 22 122 1
: Added Pair: 1 -> 22
: Added Pair: 22 -> 122
: Pairs: [1 => 22, 22 => 122]
100

The coercer gives us a new value, so that we have a unique value on the right hand side of the pairs.

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

[10] Save the second value for the next iteration (as the new first value).

[11] Return the list of Pair objects.

[12] Apply the reduce routine on all the Pairs (done with the >>. method call). The routine takes a procedure or operator as argument, and should return a single value (reduce somthing to a single value) The & syntax is there to pass a reference, as opposed to execute the procedure up front.

[13] For a given Pair, take the key minus the value and return the absolute value (i.e. get rid of the sign).

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

Running it:

Running it with the values from the challenge gives the same result:

$ ./maximum-gap 2 9 3 5
4

$ ./maximum-gap 1 3 8 2 0
5

$ ./maximum-gap 5
0

With verbose mode:

$ ./maximum-gap -v 2 9 3 5
: Added Pair: 2 -> 3
: Added Pair: 3 -> 5
: Added Pair: 5 -> 9
: Pairs: [2 => 3, 3 => 5, 5 => 9]
4

$ ./maximum-gap -v 1 3 8 2 0
: Added Pair: 0 -> 1
: Added Pair: 1 -> 2
: Added Pair: 2 -> 3
: Added Pair: 3 -> 8
: Pairs: [0 => 1, 1 => 2, 2 => 3, 3 => 8]
5

$ ./maximum-gap -v 5
0

IntStr and Sorting

Numbers are sorted as numbers:

> my @a = 1,2,11,4;
> say @a.^name;     # -> Array
> say @a[0].^name;  # -> Int
> say @a.sort;      # -> (1 2 4 9)

And strings are sorted as strings (by their ascii or Unicode order):

> my @b = "1", "2", "11", "4";
> say @b[0].^name;  # -> Str
> say @b.sort;      # -> (1 11 2 4)

The IntStr type, which we get from the command line on input that can be a number (but may not), can also be constructed with the Quote Words <…> operator:

> my @c = <1 2 11 4>;
> say @c[0].^name;  # -> IntStr
> say @c.sort;      # -> (1 2 4 11)

Note the numeric sort order.

This one shows that all the numeric values are sorted as numbers, even if we add string values to the mix:

> my @d = <1 2 foo 11 4>;
> say @d.sort;  # -> (1 2 4 11 foo)

> my @e = 1, 2, "bar", 4, 11;
> say @e.sort;  # -> (1 2 4 11 bar)

See docs.raku.org/routine/< > for more information about the Quote Word operator < >.

We can simplify this quite a bit, by getting rid of the Pairs:

File: maximum-gap-simplified
#! /usr/bin/env raku

multi sub MAIN (*@N where @N.elems == 1, :v($verbose))
{
  say 0;
}

multi sub MAIN (*@N where @N.elems > 1 && all(@N) ~~ Int, :v($verbose))
{
  my @diffs = diff-pairs(@N.sort, $verbose);  # [1]

  say @diffs.max;                             # [3]
}

sub diff-pairs (@list is copy, $verbose)
{
  my $first = @list.shift;
  my $second;
  my @result;

  while (@list)
  {
    $second = @list.shift;

    @result.push: abs($first - $second);      # [2]

    say ": Added diff from Pair: $first,$second -> { abs($first - $second) }"
      if $verbose;

    $first = $second;
  }

  return @result;
}

[1] Get a list of difference values (instead of Pairs).

[2] Save the current difference (instead of the Pair).

[3] Print the largest one.

Running it gives the correct answers:

$ ./maximum-gap-simplified -v 2 9 3 5
: Added diff from Pair: 2,3 -> 1
: Added diff from Pair: 3,5 -> 2
: Added diff from Pair: 5,9 -> 4
4

$ ./maximum-gap-simplified -v 1 3 8 2 0
: Added diff from Pair: 0,1 -> 1
: Added diff from Pair: 1,2 -> 1
: Added diff from Pair: 2,3 -> 1
: Added diff from Pair: 3,8 -> 5
5

$ ./maximum-gap-simplified -v 5
0

Challenge #106.2: Decimal String

You are given numerator and denominator i.e. $N and $D.

Write a script to convert the fraction into decimal string. If the fractional part is recurring then put it in parenthesis.

Example:
Input: $N = 1, $D = 3
Output: "0.(3)"

Input: $N = 1, $D = 2
Output: "0.5"

Input: $N = 5, $D = 66
Output: "0.0(75)"

Let us have a go in REPL mode:

$ Raku
> say 1/3;   # -> 0.333333
> say 1/2;   # -> 0.5
> say 5/66;  # -> 0.075758

The first one is easy to detect (recurring 3s), the second one is the correct value, and the third one has been rounded up.

Let us slap on fmt (as in format, the method version of printf):

> say (5/66).fmt("%020f");  # -> 0000000000000.075758

That did not help. «020» requests 20 digits (or more), and the initial zero asks for zero padding (instead of using spaces).

The problem is the coercion to string, caused by printing the value. Coercion to Num, before printing, gives us a better (longer) value:

> say (1/6).Str;   # -> 0.166667
> say (1/6).Num;   # -> 0.16666666666666666
> say (5/66).Str;  # -> 0.075758
> say (5/66).Num;  # -> 0.07575757575757576

See docs.raku.org/routine/fmt more information about fmt.

Rat (Rational Numbers)

Raku has a Rat type used for Rational Numbers:

> say (5/66).^name;  # -> (Rat)
> say (5/66).nude;   # -> (5 66)
> say (15/66).nude;  # -> (5 22)

The rudely named nude method gives us the numerator and denominator of the value (as a list). Note that the values are reduced (simplified) as much as possible, as shown for the last example above.

See docs.raku.org/type/Rat for more information about the Rat class.

Reading the documentation, generally a good idea, for Rat revealed that it has a base-repeating method. That method does just what we are looking for:

File: decimal-string
#! /usr/bin/env raku

unit sub MAIN (Int $N where $N != 0, Int $D where $D != 0);  # [1]

my $rat = $N / $D;                        # [2]

my ($base, $rep) = $rat.base-repeating;   # [3]

say $base, ( $rep ?? "($rep)" !! '');     # [4]

[1] Ensure that the input are integers, and avoid zero.

[2] The divison.

[3] Get the base value, and the recurring pattern (if any).

[4] Print the value, and the recurring pattern (if any).

Running it:

$ ./decimal-string 1 3
0.(3)

$ ./decimal-string 1 2
0.5

$ ./decimal-string 5 66
0.0(75)

Looking good.

And that's it.