laurent_r

These are some answers to the Week 106 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a couple of days (April 4, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 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

Trying all combinations would imply an algorithmic complexity of O(n²), whereas the obviously immediate solution, i.e. first sorting the array has a better algorithmic complexity of O(n log n). So we will start with sorting the array and then explore the successive gaps to find the largest one.

Maximum Gap in Raku

We might start with a standard for loop to find the largest gap , as we would do in C or in Pascal.

use v6;

my @input = 2, 9, 3, 5;
my @sorted = sort @input;
my $max = 0;
for 1..@sorted.end -> $i {
    $max = @sorted[$i] - @sorted[$i-1] if @sorted[$i] - @sorted[$i-1] > $max;
}
say "Max gap: $max";

This works fine and the output is what we expect:

$ raku max-gap.raku
Max gap: 4

But we can make the code slightly shorter with functional programming:

my @input = 2, 9, 3, 5;
say 0 and exit if @input <= 1;
my @sorted = sort @input;
my $max = max map { @sorted[$_] - @sorted[$_-1] }, 1..@sorted.end;
say "Max gap: $max";

The line where $max is declared and defined is a data pipeline and should be read from right to left. We first generate a list of array subscripts from 1 to the index of the last item, the use the map to generate of gaps between each element and the previous one, and finally call the built-in max function on this new list.

We display the same output:

$ raku max-gap2.raku
Max gap: 4

Raku provides some built-in functions that make it possible to solve the problem in just one single line of code. The rotor routine takes an array or a list as input parameter and returns a sequence of lists, where each sublist is made up of elements of the invocant. You can define the number of items of each sublist and a gap between the sublists. With a negative gap, the sublists overlap. Here, with a number of item equal to 2 and a gap of -1, we get a series of two-items sequence on which we can compare the differences.

say "Max gap = ", <2 9 3 5>.sort.rotor(2 => -1).map({$_[1] - $_[0]}).max;

Note that the one-liner program just above doesn’t handle lists with only one element, but that’s trivial and left as an exercise to the reader.

Again, this program displays the following:

Max gap: 4

Maximum Gap in Perl

Computing the maximum gap with a traditional for loop:

use strict;
use warnings;
use feature "say";

my @input = (2, 9, 3, 5);
my @sorted = sort { $a <=> $b} @input;
my $max = 0;
for my $i (1..$#sorted) {
    $max = $sorted[$i] - $sorted[$i-1] if $sorted[$i] - $sorted[$i-1] > $max;
}
say "Max gap: $max";

Output:

$ perl max-gap.pl
Max gap: 4

Just as before, we can also choose a functional programming approach and build a data pipeline:

use strict;
use warnings;
use feature "say";

my @input = (2, 9, 3, 5);
my @sorted = sort { $a <=> $b} @input;
my $max = @input <= 1 ? 0 : 
    (sort { $b <=> $a} map { $sorted[$_] - $sorted[$_-1] } 1..$#sorted)[0];
say "Max gap = $max";

Maximum Gap in Scala

Here, again, we use a functional programming approach:

object root extends App {
  val tests = Seq(2, 9, 3, 5)
  val sorted = tests.sorted
  val max = if (sorted.size <= 1) 0 else
    (1 to sorted.length - 1).map(i => sorted(i) - sorted(i - 1)).max
  println("Max gap is: " + max)
}

Output:

Max gap is: 4

Maximum Gap in Python

Again the functional programming approach:

tests = [2, 9, 3, 5]
sorted = sorted(tests)
max = 0 if len(sorted) <= 1 else (
    max(map(lambda i: sorted[i] - sorted[i-1], 
    range(1, len(sorted) ))))
print("Max gap = ", max)

Output:

Max gap =  4

Maximum Gap in Julia

Also a functional approach:

tests = [17, 2, 9, 3, 5]
sorted = sort(tests)
gaps = map(i -> sorted[i] - sorted[i - 1], 2:length(sorted))
@printf("Max gap is %i", maximum(gaps))

Output:

Max gap is 8

Maximum Gap in Ruby

Functional approach, again:

test = [2, 9, 3, 5]
sorted = test.sort
gaps = (1.upto(sorted.length()-1)).map { |i| sorted[i] - sorted[i - 1] }
print "Max gap is: ", gaps.max

Output:

Max gap is: 4

Maximum Gap in Rust

Again functional programming approach, except that the test vector must be mutable because the Rust sort method sorts data in-place. There may be some other solution, but I didn’t find it (I don’t know Rust well enough).

fn main () {
    let mut test = vec![2, 9, 3, 5];
    test.sort();
    let gaps: Vec<i32> = (1..test.len()).map(|i| test[i] - test[i-1]).collect();
    println!("Max gap is: {:?}",  gaps.iter().max());
}

This also finds 4 as the maximum gap.

Task 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)"

Decimal String in Raku

Raku has a built-in method, base-repeating, provided by role Rational, that just do that:

use v6;

sub MAIN( Int $num, Int $den where $den != 0  ) {
    my ($non-rep, $repeating) = ($num / $den).base-repeating;
    my $suffix = $repeating ?? "($repeating)" !! "";
    printf '%s%s', $non-rep, $suffix;
}

These are some example outputs for various input values:

$ raku decimal-str.raku 100 25
4

$ raku decimal-str.raku 10 3
3.(3)

$ raku decimal-str.raku 4 625
0.0064

$ raku decimal-str.raku 5 66
0.0(75)

Decimal String in Perl

This turned out to be much more complicated, since we don’t have any built-in subroutine for that.

My initial idea was to let Perl just perform the division and to look for repeated digit groups (with regular expression or some other means) in the result. But that turned out to be impractical and also wrong for some input values, since Perl only computes only about 15 decimal digits. It might be feasible with a big integer module, but I did not try and decided to go for another method (explained below). I kept, however, the part of the program which counts the initial number of zeros at the beginning (when the denominator is larger than the numerator).

So I decided to compute decimal digits by hand one by one and check at each step whether the remainder of the division has already been seen before. Whenever this happens, we know that the digits found since the last time we’ve found the same remainder form a repeated grouping of digits and we can stop.

While I was working on that, I came across a Python program (see below) just implementing this. So, out of laziness, I more or less ported to Perl this Python program.

The following program does what is required (provided the input values are positive):

use strict;
use warnings;
use feature "say";

sub compute_dec_str {
    my ($num, $den) = @_;
    die "Please provide positive numbers" if $num < 0 or $den <= 0;
    my $c = 10 * ($num % $den);
    my $quotient = $num/$den;
    # get the quotient leading 0s if any
    $quotient =~ s/(^\d+\.?0*)\d*/$1/;
    $c *= 10 for split " ",  ($quotient =~ /\.(0+)/);
    my (@digits, %passed);
    my $i = 0;
    while (1) {
        if (exists $passed{$c}) {
            my @repeated = @digits[$passed{$c}..$#digits];
            my $result = $quotient . join("", @digits[0..$passed{$c} - 1]);
            if ( @repeated > 1 or $repeated[0] != 0) {
                $result .= "(" . join("", @repeated) . ")";
            }
            $result =~ s/\.$//; # remove trailing dot if any
            return $result;
        }
        push @digits, int($c / $den);
        $passed{$c} = $i;
        $i++;
        $c = 10 * ($c % $den);
    }
}
my $result = compute_dec_str @ARGV;
say $result;

Output:

$ perl decimal_string.pl 1 33
0.0(30)

$ perl decimal_string.pl 4 625
0.00064

$ perl decimal_string.pl 5 66
0.0(75)

Decimal String in Python

This is the Python program on which I loosely based my Perl solution. It can be found there. Please note that this program isn’t from me, but I don’t know who the author is.

def divide(m, n):
    quotient, c = str(m // n) + ".", 10 * (m % n)
    while c and c < n:
        c *= 10
        quotient += "0"
    digits = ""
    passed = {}
    i = 0
    while True:
        if c in passed:
            prefix = digits[:passed[c]]
            cycle = digits[passed[c]:]
            result = quotient + prefix + "(" + cycle + ")"
            return result.replace("(0)", "").rstrip(".")
        q, r = c // n, c % n
        passed[c] = i
        digits += str(q)
        i += 1
        c = 10 * r

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, April 11, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.