This is my response to the Perl Weekly Challenge #106.
@N.
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.
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
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
$N and $D.
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.
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:
#! /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.