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

Spoiler Alert: This weekly challenge deadline is due in a few days (April 25, 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: Chowla Numbers

Write a script to generate first 20 Chowla Numbers, named after, Sarvadaman D. S. Chowla, a London born Indian American mathematician. It is defined as:

C(n) = sum of divisors of n except 1 and n

Output:

0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21

Originally, the task requested us to generate the first 37 Chowla numbers and I wrote implementations in 12 different languages based on that requirement. This requirement has now been amended to the first 20 Chowla numbers. I’ll fix the program and output for some implementations, but will leave some as they were developed.

Chowla Numbers in Raku

For each number $n between 1 and 20, we print 0 if the number is less than 2 or if it is prime. Otherwise, we look for divisors of that number between 2 and $n / 2 (thereby excluding 1 and the number $n itself) and compute the sum of the divisors.

use v6;

sub chowla (Int $n) {
    return 0 if $n < 2 or $n.is-prime;
    return (2..$n div 2).grep({$n %% $_}).sum;
}
say "$_\t", chowla $_ for 1..20;

Note that for the first implementation of this task, I decided to print the source number and the Chowla number over two columns to make result checking easier. All other implementations will be printed over a single line for brevity. So this is our output over two columns:

$ raku ./chowla.raku
1   0
2   0
3   0
4   2
5   0
6   5
7   0
8   6
9   3
10  7
11  0
12  15
13  0
14  9
15  8
16  14
17  0
18  20
19  0
20  21

Chowla Numbers in Perl

Perl doesn’t have a built-in sum method as Raku, so I’ll compute the sums by hand (I know that there are modules doing that, but, as I have pointed out many times already, I do not want to use external libraries as I consider this would go against the true spirit of a coding challenge).

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

sub chowla {
    my $n = shift;
    return 0 if $n <= 2;
    my @divisors = grep {$n % $_== 0} 2..($n / 2);
    my $sum = 0;
    $sum += $_ for @divisors;
    return $sum;
}
say join ", ", map { chowla $_} 1..20;

This displays the following output.

$ perl chowla.pl
0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21

Chowla Numbers in Other Languages

Note that I don’t consider the example output provided with the task description to be part of the requirement. In some cases, I’ll output the values separated by commas, in others simply by a space. And since I do not want to test again all the programs below (for some, I would have to go on another computer), I’ll stick to the original requirement of the first 37 Chowla numbers for some of the programs below.

Chowla Numbers in Scala

Rather than storing the divisors in an array as I did in Perl, I just accumulate them into a sum variable. Note that in Scala, to get all integers between 1 and 20, you need to use 1 until 21, since the upper bound is not included in the range.

object chowla extends App {
  def chowla(n: Int): Int = {
    if (n <= 2) return 0
    var sum = 0;
    for (i <- 2 until n/2 + 1) {
      if (n % i == 0) sum += i
    }
    return sum
  }
  println((1 until 21).map(chowla(_)).mkString(", "))
}

Output:

0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21

Chowla Numbers in C

#include <stdio.h>

int chowla(int n) {
    int sum = 0;
    for (int i = 2; i <= n/2; i++) {
        if (n % i == 0) {
            sum += i;
        }
    }
    return sum;
}

int main() {
    for (int n = 1; n <= 37; n++) {
        printf("%i ", chowla(n));
    }
    printf("\n");
}

Output:

$ ./a.out
0 0 0 2 0 5 0 6 3 7 0 15 0 9 8 14 0 20 0 21 10 13 0 35 5 15 12 27 0 41 0 30 14 19 12 54 0

Chowla Numbers in Python

Here again (as in Scala), to get all integers between 1 and 20, you need to use range(1, 21), since the upper bound is not included in the range.

def chowla(n):
    sum = 0
    for i in range(2, int(n/2) +1):
        if n % i == 0:
            sum += i
    return sum

chowla_nums = []
for m in range (1, 21):
    chowla_nums.append (chowla(m))
print(chowla_nums)

Output:

[0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21]

Chowla Numbers in Awk

Very straight forward. Here, we are printing the 20th Chowla number separately to print a new line and avoid terminating the line with a comma.

function chowla(num) {
    sum = 0
    for (i = 2; i <= n/2; i++) {
        if (n % i == 0) {
            sum += i;
        }
    }
    return sum;  
}

BEGIN {
    for (n = 1; n <= 19; n++) {
        printf("%i, ", chowla(n));
    }
    printf("%i\n", chowla(20));
}

Output:

$ awk -f chowla.awk
0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21

Chowla in Julia

An interesting feature of Julia is that you can use Unicode letters in identifiers for variables or functions. Here we use capital Greek letter ∑ for our sum variable:

function chowla(n)
    ∑ = 0
    for i = 2:(trunc(Int, n/2))
        if (n % i == 0) ∑ += i end
    end 
    return ∑

end
for n = 1:37 print(chowla(n), " ") end

Output:

0 0 0 2 0 5 0 6 3 7 0 15 0 9 8 14 0 20 0 21 10 13 0 35 5 15 12 27 0 41 0 30 14 19 12 54 0

Chowla in Rust

fn chowla(n : i32) -> i32 {
    let mut sum = 0;
    for i in 2..=n/2 {
        if n % i == 0 {
            sum += i
        }
    }
    return sum
}
fn main() {
    for n in 1..20 {
        print!("{}, ", chowla(n));
    }
    println!("{} ", chowla(20));
}

Output:

0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21

Chowla in Go

package main

import "fmt"
func chowla(n int) int {
    var sum int = 0
    for i := 2; i <= n/2; i++ {
        if (n % i == 0) {
            sum += i;
        }
    }
    return sum;
}       
func main() {
    const MAX int = 37
    for i := 1; i <= MAX; i++ {
        fmt.Print(chowla(i), " ")
    }
}

Output:

0 0 0 2 0 5 0 6 3 7 0 15 0 9 8 14 0 20 0 21 10 13 0 35 5 15 12 27 0 41 0 30 14 19 12 54 0

Chowla in Pascal

program chowla;
const
    max = 37;

var
    j, res : integer;

function chowla(n: integer): integer;
var
    i, sum, rounded_half: integer;
begin
    sum := 0;
    rounded_half := round(n/2);
    for i := 2 to rounded_half do
    begin 
        if (n mod i = 0) then
            sum := sum + i
    end;
    chowla := sum;
end;

begin
    for j := 1 to max do
    begin
        write(chowla(j), ' ');
    end;
    writeln(' ');
end.

Output:

0 0 0 2 0 5 0 6 3 7 0 15 0 9 8 14 0 20 0 21 10 13 0 35 5 15 12 27 0 41 0 30 14 19 12 54 0

Chowla in D

import std.stdio;

int chowla(int n) {
    int sum = 0;
    for (int i = 2; i <= n-1; i++) {
        if (n % i == 0) {
            sum += i;
        }
    }
    return sum;
}
void main() {
    for (int n = 1; n <= 37; n++) {
        writef("%d ", chowla(n));
    }
    writeln("");
}

Output:

0 0 0 2 0 5 0 6 3 7 0 15 0 9 8 14 0 20 0 21 10 13 0 35 5 15 12 27 0 41 0 30 14 19 12 54 0

Chowla in Ruby

def chowla (n)
    sum = 0
    for i in 2..n/2
        if n % i == 0
            sum += i
        end
    end
    return sum;
end

max = 37
results = []
for n in 1..max 
    results[n-1] = chowla(n)
end
puts "The #{max} first Chowla numbers are:  #{results.join(" ")}"

Output:

The 37 first Chowla numbers are:  0 0 0 2 0 5 0 6 3 7 0 15 0 9 8 14 0 20 0 21 10 13 0 35 5 15 12 27 0 41 0 30 14 19 12 54 0

Task 2: Four Squares Puzzle

You are given four squares as below with numbers named a,b,c,d,e,f,g.

          (1)                    (3)
    ╔══════════════╗      ╔══════════════╗
    ║              ║      ║              ║
    ║      a       ║      ║      e       ║
    ║              ║ (2)  ║              ║  (4)
    ║          ┌───╫──────╫───┐      ┌───╫─────────┐
    ║          │   ║      ║   │      │   ║         │
    ║          │ b ║      ║ d │      │ f ║         │
    ║          │   ║      ║   │      │   ║         │
    ║          │   ║      ║   │      │   ║         │
    ╚══════════╪═══╝      ╚═══╪══════╪═══╝         │
               │       c      │      │      g      │
               │              │      │             │
               │              │      │             │
               └──────────────┘      └─────────────┘

Write a script to place the given unique numbers in the square box so that sum of numbers in each box is the same.

Example:

Input: 1,2,3,4,5,6,7

Output:

    a = 6
    b = 4
    c = 1
    d = 5
    e = 2
    f = 3
    g = 7

    Box 1: a + b = 6 + 4 = 10
    Box 2: b + c + d = 4 + 1 + 5 = 10
    Box 3: d + e + f = 5 + 2 + 3 = 10
    Box 4: f + g = 3 + 7 = 10

The example in the task description provides only one solution to the puzzle, but there may be several solutions (most solutions will have a symmetrical one, because of the symmetry of the figure with the squares). In my original implementation in Raku, I stopped the algorithm as soon as one solution was found, but I then changed my mind and decided to list all solutions.

If I were solving the puzzle by hand, I would first notice that, since all squares have the same sum, then, the sum a + 2b + c + 2d + e + 2f + g must be a multiple of 4. Since the sum of the input numbers in the example is 28, we can try to see how, when adding three of the input numbers, we can get to a multiple of 4. The possible total sums are therefore 36, 40 and 44, so that the individual square sums are 9, 10 or 11. We can then add equations to the story: for example, we must have a = c + d, b + c = e + f, and g = e + d. We also have a + b = b + c + c = d + e + f = f + g. And so on. From there, we can use substitutions and eliminations in these equations and eventually get to a fairly limited number of possibilities that we can then explore one by one. In other words, we are still likely to have to conduct some form of exhaustive search in the final phase.

This is one case where you probably don’t want to let your computer do it the same way a human being would do it. Since we probably need an exhaustive search in the end, let’s do everything with an exhaustive search, i.e. a brute force approach. After all, computers are much better than us, humans, at doing that. So, basically, we will examine all permutations of the seven input integers. There are 7! = 5040 such permutations, really no big deal for a computer. Some of the programs below run in less than 0.1 seconds. I had some performance optimizations in mind (like eliminating early entire sub-trees of permutations that could not lead to solutions), but it turns out that it isn’t even necessary.

Four Squares Puzzle in Raku

As explained above, we just use the built-in permutations method and test all permutations of the input numbers

use v6;

sub check-squares (@in) {
    my $flag = False;
    for @in.permutations -> @perm {
        my $sum1 = [+] @perm[0, 1];
        next if $sum1 != [+] @perm[1..3] or 
            $sum1 != [+] @perm[3..5] or
            $sum1 != [+] @perm[5, 6];
        say @perm and $flag = True
    }
    return $flag;
}
say "No solution" unless check-squares(1..7)

This leads to 8 solutions:

$ raku ./four-squares.raku
(3 7 2 1 5 4 6)
(4 5 3 1 6 2 7)
(4 7 1 3 2 6 5)
(5 6 2 3 1 7 4)
(6 4 1 5 2 3 7)
(6 4 5 1 2 7 3)
(7 2 6 1 3 5 4)
(7 3 2 5 1 4 6)

Each solution is the symmetry of another one (for example (3 7 2 1 5 4 6) is the symmetry of (6 4 5 1 2 7 3)), which reflects the symmetry of the figure with the four squares. Also notice that the individual square sums are 9, 10 and 11, which confirms the original manual analysis of the problem made above.

Note that we can make the check-squares subroutine slightly more concise and perhaps a bit simpler using chained numeric equality operators:

use v6;

sub check-squares (@in) {
    my $flag = False;
    for @in.permutations -> @p {
        say @p and $flag = True if 
            @p[0,1].sum == @p[1..3].sum ==
            @p[3..5].sum == @p[5, 6].sum;
    }
    return $flag;
}
say "No solution" unless check-squares(1..7)

This amended version displays the same output.

Four Squares Puzzle in Raku

Perl doesn’t have a built-in permutations subroutine. There are some CPAN modules, such as ntheory or Algorithm::Permute, providing a permutation functionality, but I explained above why I eschew using external libraries for a coding challenge. So, I’ll write my own little recursive permute subroutine:

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

sub add {
    my $sum = 0;
    $sum += $_ for @_;
    return $sum;
}
sub check_squares {
    my @in = @{$_[0]};
    my $sum = add @in[0, 1];
    return ($sum == add @in[1..3] and
            $sum == add @in[3..5] and
            $sum == add @in[5, 6] );
}
sub permute {
    my ($perm_ref, $inref) = @_;
    my @in = @$inref;
    if (scalar @in == 0) {
        say "@$perm_ref" if check_squares $perm_ref;
        return;
    }
    permute([@$perm_ref, $in[$_]], [ @in[0..$_-1, $_+1..$#in] ]) for 0..$#in;
}
my @input = 1..7;
permute [], \@input;

And we obtain the same output:

$ perl four-squares.pl
3 7 2 1 5 4 6
4 5 3 1 6 2 7
4 7 1 3 2 6 5
5 6 2 3 1 7 4
6 4 1 5 2 3 7
6 4 5 1 2 7 3
7 2 6 1 3 5 4
7 3 2 5 1 4 6

Four Squares Puzzle in Other Programming Languages

In some languages, we’ll use a built-in permutation routine, in others, we will roll out our own, either recursive or iterative, permutation function.

Four Squares in Scala

Scala has a built-in permutation method. So we generate all permutations and print out those satisfying the requirement:

object fourSquares extends App {
  val in = (1 to 7).toList
  for (perm <- in.permutations) {
    val sum = perm.slice(0, 2).sum;
        // In Scala, slice(0, 2) returns items 0 and 1
    if (
      perm.slice(1, 4).sum == sum &&
      perm.slice(3, 6).sum == sum &&
      perm.slice(5, 7).sum == sum
    ) {
      println(perm.mkString(" "))
    }
  }
}

Output:

3 7 2 1 5 4 6
4 5 3 1 6 2 7
4 7 1 3 2 6 5
5 6 2 3 1 7 4
6 4 1 5 2 3 7
6 4 5 1 2 7 3
7 2 6 1 3 5 4
7 3 2 5 1 4 6

Four Squares in Python

We use the permutations method provided by itertools core library. Our Python implementation can use chained equality operators, similarly to our second Raku implementation:

import itertools

input = range(1, 8)  # 1 to 7
for p in itertools.permutations(input):
    if sum(p[0:2]) == sum(p[1:4]) == sum(p[3:6]) == sum(p[5:7]):
        print (perm)

Output:

(3, 7, 2, 1, 5, 4, 6)
(4, 5, 3, 1, 6, 2, 7)
(4, 7, 1, 3, 2, 6, 5)
(5, 6, 2, 3, 1, 7, 4)
(6, 4, 1, 5, 2, 3, 7)
(6, 4, 5, 1, 2, 7, 3)
(7, 2, 6, 1, 3, 5, 4)
(7, 3, 2, 5, 1, 4, 6)

Four Squares in Julia

Julia has the Combinatorics external library that provides a permutations function, but, as mentioned above, I tend to avoid using external libraries for a coding challenge. So we will roll out our own permute function, based on this Wikipedia Page on Heap’s algorithm. Note that the algorithm described on Wikipedia is for zero-based array indices, I had to change the details significantly for Julia’s one-based array indices.

function check_squares(p)
    ∑ = p[1] + p[2]
    return (p[2] + p[3] + p[4] == ∑ &&
        p[4] + p[5] + p[6] == ∑ &&
        p[6] + p[7] == ∑)
end

function permute(k, in)  # Heap's algorithm
    if (k == 1)
        if (check_squares(in)) println(in) end
        # println(in)
    else
        permute(k - 1, in)
        for i = 1:(k-1)
            if (k % 2 == 0)
                in[i], in[k] = in[k], in[i]
            else
                in[1], in[k] = in[k], in[1]
            end
            permute(k - 1, in)
        end
    end
end

permute(7, [1, 2, 3, 4, 5, 6, 7])

Output:

$ julia four_squares.jl
[4, 5, 3, 1, 6, 2, 7]
[6, 4, 1, 5, 2, 3, 7]
[7, 2, 6, 1, 3, 5, 4]
[5, 6, 2, 3, 1, 7, 4]
[6, 4, 5, 1, 2, 7, 3]
[4, 7, 1, 3, 2, 6, 5]
[7, 3, 2, 5, 1, 4, 6]
[3, 7, 2, 1, 5, 4, 6]

Four Squares in C

C language is relatively low-level and, as you can imagine, doesn’t have a built-in permutation function. So it will be rolled out in the main function.

#include <stdio.h>

int check_squares (int p[]) {
    int sum = p[0] + p[1];
    return ( p[1] + p[2] + p[3] == sum &&
        p[3] + p[4] + p[5] == sum &&
        p[5] + p[6] == sum);
}

void swap (int a[], int m, int n) {
    int temp = a[m];
    a[m] = a[n];
    a[n] = temp;
}

int main() {
    int in[7] = {7, 6, 5, 4, 3, 2, 1}; # values must be in descending order
    int i, j;
    int fact = 5040;        //factorial 7
    while (fact--) {
        if (check_squares(in)) {
            for (int i = 0; i < 6; i++) printf("%d ", in[i]);
            printf("%d\n", in[6]);
        }
        i = 1;
        while (in[i] > in[i-1]) i++;
        j = 0;
        while (in[j] < in[i]) j++;
        swap(in, i, j);
        i--;
        for (j = 0; j < i; i--, j++) swap(in, i, j);
    }
}

Output:

6 4 5 1 2 7 3                                                                                                           
7 2 6 1 3 5 4                                                                                                           
5 6 2 3 1 7 4                                                                                                           
4 7 1 3 2 6 5                                                                                                           
7 3 2 5 1 4 6                                                                                                           
3 7 2 1 5 4 6                                                                                                           
4 5 3 1 6 2 7                                                                                                           
6 4 1 5 2 3 7

Four Squares in Lua

Lua doesn’t have a built-in permutation function (AFAIK), so we will roll out our own recursive permute function:

local function check_square (p)
    sum = p[1] + p[2]
    return p[2] + p[3] + p[4] == sum and 
        p[4] + p[5] + p[6] == sum and
        p[6] + p[7] == sum
end  

local function permute(perm, n)
    if n == 0  and check_square(perm) then
        print( table.concat(perm, ' ') ) 
    else
        for i = 1, n do
            perm[i], perm[n] = perm[n], perm[i]
            permute(perm, n - 1)
            perm[i], perm[n] = perm[n], perm[i]
        end
    end
end

permute({1,2,3,4,5,6,7}, 7)

Output:

6 4 5 1 2 7 3
5 6 2 3 1 7 4
7 2 6 1 3 5 4
4 7 1 3 2 6 5
7 3 2 5 1 4 6
3 7 2 1 5 4 6
4 5 3 1 6 2 7
6 4 1 5 2 3 7

Four Squares in D

The D programming language has a couple of permutation methods in its std.algorithm core library. We will use nextPermutation, which acts as an iterator:

bool check_squares (int [] p) {
    int sum = p[0] + p[1];
    return ( p[1] + p[2] + p[3] == sum &&
        p[3] + p[4] + p[5] == sum &&
        p[5] + p[6] == sum);
}

void main() {
    import std.stdio, std.algorithm;
    auto items = [1, 2, 3, 4, 5, 6, 7];
    do
        if (check_squares(items)) items.writeln;
    while (items.nextPermutation);
}

Output:

[3, 7, 2, 1, 5, 4, 6]
[4, 5, 3, 1, 6, 2, 7]
[4, 7, 1, 3, 2, 6, 5]
[5, 6, 2, 3, 1, 7, 4]
[6, 4, 1, 5, 2, 3, 7]
[6, 4, 5, 1, 2, 7, 3]
[7, 2, 6, 1, 3, 5, 4]
[7, 3, 2, 5, 1, 4, 6]

Four Squares in Nim

Remember that Nim supports indentation-based syntax like Python, except that it is possible to break a line after a binary operator (after the and in the code below). We use the nextPermutation method of the core algorithm library, which also acts as an iterator.

import algorithm

proc check_squares (p: array[0..6, int]) : bool =
    var sum = p[0] + p[1] 
    return ( p[1] + p[2] + p[3] == sum and 
      p[3] + p[4] + p[5] == sum and p[5] + p[6] == sum )


var input = [1, 2, 3, 4, 5, 6, 7] # List has to start sorted
while input.nextPermutation():
  if check_squares(input):
    echo input

Output:

[3, 7, 2, 1, 5, 4, 6]
[4, 5, 3, 1, 6, 2, 7]
[4, 7, 1, 3, 2, 6, 5]
[5, 6, 2, 3, 1, 7, 4]
[6, 4, 1, 5, 2, 3, 7]
[6, 4, 5, 1, 2, 7, 3]
[7, 2, 6, 1, 3, 5, 4]
[7, 3, 2, 5, 1, 4, 6]

Four Squares in Ruby

We use the built-in permutation method of Ruby and print out the permutations matching the requirements:

input = [1, 2, 3, 4, 5, 6, 7]
for p in input.permutation 
    sum = p[0] + p[1]
    if p[1] + p[2] + p[3] == sum and 
       p[3] + p[4] + p[5] == sum and    
       p[5] + p[6] == sum then
        puts p.join(" ")
    end
end

Output:

3 7 2 1 5 4 6
4 5 3 1 6 2 7
4 7 1 3 2 6 5
5 6 2 3 1 7 4
6 4 1 5 2 3 7
6 4 5 1 2 7 3
7 2 6 1 3 5 4
7 3 2 5 1 4 6

Four Squares in Kotlin

I did not write the permute function used in the program below, but found it on the Internet.

fun <T> permute(input: List<T>): List<List<T>> {
    if (input.size == 1) return listOf(input)
    val perms = mutableListOf<List<T>>()
    val toInsert = input[0]
    for (perm in permute(input.drop(1))) {
        for (i in 0..perm.size) {
            val newPerm = perm.toMutableList()
            newPerm.add(i, toInsert)
            perms.add(newPerm)
        }
    }
    return perms
}

fun check_squares(p: List<Int>): Boolean  {
    val sum = p[0] + p[1] 
    return ( p[1] + p[2] + p[3] == sum &&
             p[3] + p[4] + p[5] == sum &&
             p[5] + p[6] == sum )
}

fun main(args: Array<String>) {
    val input = listOf(1, 2, 3, 4, 5, 6, 7)
    val perms = permute(input)
    for (perm in perms) {
        if (check_squares(perm)) println(perm)
    }
}

Output:

[4, 5, 3, 1, 6, 2, 7]
[5, 6, 2, 3, 1, 7, 4]
[6, 4, 1, 5, 2, 3, 7]
[6, 4, 5, 1, 2, 7, 3]
[3, 7, 2, 1, 5, 4, 6]
[7, 3, 2, 5, 1, 4, 6]
[4, 7, 1, 3, 2, 6, 5]
[7, 2, 6, 1, 3, 5, 4]

Four Squares in Go

package main

import "fmt"

func check_squares ( p[] int) bool {
    var sum = p[0] + p[1]
    return ( p[1] + p[2] + p[3] == sum &&
        p[3] + p[4] + p[5] == sum &&
        p[5] + p[6] == sum)
}

func main() {
    var in = []int{1, 2, 3, 4, 5, 6, 7}
    var max = len(in) - 1
    var i, j int
    for c := 1; c < 5040; c++ { // 7! = 5040
        i = max - 1
        j = max
        for in[i] > in[i+1] {
            i--
        }
        for in[j] < in[i] {
            j--
        }
        in[i], in[j] = in[j], in[i]
        j = max
        i += 1
        for i < j {
            in[i], in[j] = in[j], in[i]
            i++
            j--
        }
        if check_squares(in) {
            fmt.Println(in)
        }
    }
}

Output:

[3 7 2 1 5 4 6]
[4 5 3 1 6 2 7]
[4 7 1 3 2 6 5]
[5 6 2 3 1 7 4]
[6 4 1 5 2 3 7]
[6 4 5 1 2 7 3]
[7 2 6 1 3 5 4]
[7 3 2 5 1 4 6]

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, May 2, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.

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

Spoiler Alert: This weekly challenge deadline is due in a few days (April 18, 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: Locate Memory

Write a script to declare a variable or constant and print it’s location in the memory.

Locate Memory in Raku

In languages such as Perl and C, it is a fairly common task to take a reference or a pointer to a variable, and a reference or a pointer are essentially the memory addresses of such a variable (for some definition of memory address). In Raku, using the memory address of a variable is almost never necessary (except possibly for low-level debugging purpose). Actually, I originally wasn’t even completely sure I was going to find a way of doing that in Raku. However, the Metaobject Protocol (MOP) offers some metamethods, which are introspective macros that provide information about objects (including variables). One such metamethod is WHERE, which returns an Int representing the memory address of the object. Once we know that, the task is very easy:

my $i = 42;
say $i.WHERE;

This small script displays the following output:

$ raku memory.raku
41688736

Locate Memory in Perl

As mentioned before, taking a reference to a variable is very common in Perl. And a reference is in effect a memory address. So the task is very easy in Perl:

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

my $i = 42;
say \$i;

This displays the following output:

$ perl memory.pl
SCALAR(0x600079020)

If we want to get rid of irrelevant information and print out only the memory address, we can just extract the address, for example with a regular expression:

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

my $i = 42;
my $ref = \$i;
my $addr = $1 if $ref =~ /\((0x\w+)/;
say $addr;

which prints only the memory address:

$ perl memory.pl
0x600079020

Locate Memory in Other Languages

Memory Address in the C Programming Language

In C, & is the “address-of” operator:

#include <stdio.h>

int main () {
    int val = 42;
    printf("Memory location of val is: %p", &val);
    return 0;
}

Output:

$ ./a.out
Memory location of val is: 0xffffcc1c

Memory Address in C++

Rather than copying almost verbatim the C program above, we’ll use the fact that C and C++ array names are actually pointers to memory locations:

#include <iostream>
using namespace std;

int main() {
  int array[4] = {42, 43, 44, 45};
  cout << "Memory address of the array is: " << array;
  return 0;
}

Output:

Memory address of the array is: 0x7ffc3775ad50

Memory Address in the D Programming Language

D pointers are similar to C’s. So we can do basically the same as in C:

import std.stdio;

void main () { 
   int val = 42; 
   writeln("Address of val is: ", &val);
}

Output:

Address of val is: 7FFD967574F8

Memory Address in Python

Python doesn’t really have pointers, but we can still retrieve the integer representation of the address of a Python object with the id built-in:

i = 42
print("Address of variable i is: ", id(i))

Output:

Address of variable i is:  9786208

Memory Address in Go

In Go, & is the “address-of” operator:

package main

import "fmt"

func main() {
    i := 42
    fmt.Println("Address of vaiable i is: ", &i)
}

Output:

Address of vaiable i is:  0xc000018050

Memory Address in Julia

In Julia, we’ll use an array. The pointer built-in function returns a pointer to the array:

arr = [1, 2, 3, 7]
p_arr = pointer(arr)
println("Memory address of arr is: ", p_arr)

Output:

Memory address of arr is: Ptr{Int64} @0x00007f70a29334d0

Memory Address in Rust

In Rust, & is the “address-of” operator as in C:

fn main() {
    let val: i32 = 42;
    println!("Memory locacion of variable val is: {:p}", &val);
}

Output:

Memory location of variable val is: 0x7fff4b32e2fc

Memory Address in Pascal

Last time I used Pascal was in the first year of my CS curriculum, back in 1990. As you might imagine, I don’t remember much of the syntax. It did not even remember that Pascal had pointers, except that, thinking about it, I remembered that we had to implement linked lists or trees, something that probably required some form of pointer. The big difference between now and then, of course, is that it wasn’t possible at the time to look up on the Internet. So you needed to buy books, as well as the software (a Turbo-Pascal compiler from Borland at the time). Pascal might not be the most modern language, but it has a clean and clear syntax, so that it turned out to be quite simple to write this little program. The only thing that seems to be missing from Niklaus Wirth’s brainchild programming language is a good harmless goto statement. ;-). But it’s OK, I did not need it.

program memAddress;
var
   value: integer;
   intPtr: ^integer;
   result: ^word;

begin
   value := 42;
   intPtr := @value;
   result := addr(intPtr);
   writeln('Memory address of value is: ', result^);
end.

Output:

Memory address of value is: 23008

Pascal lets you easily use pointers to access the data itself. But, if, for some reason, you want to work with the memory address itself, you need to store it in a word type variable (the result variable in the program above).

Task 2: Bell Numbers

Write a script to display top 10 Bell Numbers. Please refer to Wikipedia page for more informations.

Example:

B₀: 1 as you can only have one partition of zero element set B₁: 1 as you can only have one partition of one element set {a}. B₂: 2

{a}{b} {a,b}

B₃: 5

{a}{b}{c} {a,b}{c} {a}{b,c} {a,c}{b} {a,b,c}

B₄: 15

{a}{b}{c}{d} {a,b,c,d} {a,b}{c,d} {a,c}{b,d} {a,d}{b,c} {a,b}{c}{d} {a,c}{b}{d} {a,d}{b}{c} {b,c}{a}{d} {b,d}{a}{c} {c,d}{a}{b} {a}{b,c,d} {b}{a,c,d} {c}{a,b,d} {d}{a,b,c}

The Bell numbers count the possible partitions of a set. There are various ways to compute the Bell numbers, but one of the most common ones is to construct the Bell triangle, which may be displayed as follows:

                    1
                 1     2
              2     3     5
           5     7    10    15
       15    20    27    37    52
    52    67    87   114   151   203
203   255   322   409   523   674   877

The Bell triangle may be constructed by placing the number 1 in its first position. After that placement, the leftmost value in each row of the triangle is filled by copying the rightmost value in the previous row. The remaining positions in each row are filled by a rule very similar to that for Pascal’s triangle: they are the sum of the two values to the left and upper left of the position.

Thus, after the initial placement of the number 1 in the top row, it is the last position in its row and is copied to the leftmost position in the next row. The third value in the triangle, 2, is the sum of the two previous values above-left and left of it. As the last value in its row, the 2 is copied into the third row, and the process continues in the same way.

The first (and last) item on each row provides the individual Bell numbers:

1 1 2 5 15 52 203 877 ...

There may be faster ways to compute Bell numbers, but since we are requested to compute only the first 10 Bell numbers, this will be amply sufficient.

Bell Numbers in Raku

We just build the Bell triangle (the tr array of arrays) and extract the Bell numbers from it:

constant \MAX = 9;
my @tr;
@tr[0][0] = 1;
for 1..MAX -> $row {
    @tr[$row][0] = @tr[$row - 1][*-1];
    for 1..$row -> $i {
        @tr[$row][$i] = @tr[$row][$i-1] + @tr[$row - 1][$i-1];
    }
}
say join " ", map { @tr[$_][0] }, 0..@tr.end;

This script displays the first 10 Bell numbers:

$ raku bell.raku
1 1 2 5 15 52 203 877 4140 21147

Bell Numbers in Perl

As in Raku, we build the Bell triangle and extract the Bell numbers:

use strict;
use warnings;
use feature "say";
use constant MAX => 9;

my @tr;
$tr[0][0] = 1;
for my $row (1..MAX) {
    $tr[$row][0] = $tr[$row - 1][-1];
    for my $i (1..$row) {
        $tr[$row][$i] = $tr[$row][$i-1] + $tr[$row - 1][$i-1];
    }
}
say join " ", map { $tr[$_][0] } 0..$#tr;

And we obtain the same output as in Raku:

$ perl bell.pl
1 1 2 5 15 52 203 877 4140 21147

Bell Numbers in Other Languages

Bell numbers in Scala

This is essentially the same algorithm using the Bell triangle in Scala. The slight difference is that the Bell triangle is mapped on a square matrix, with only the items of the triangular area actually defined.

object bellNum extends App {
  val max = 10
  var tr = Array.ofDim[Int](max, max)
  tr(0)(0) = 1
  for (row <- 1 until max) {
    tr(row)(0) = tr(row - 1)(row - 1)
    for (i <- 1 until row + 1) {
      tr(row)(i) = tr(row)(i - 1) + tr(row - 1)(i - 1)
    }
  }
  val result = for (i <- 0 until max) yield tr(i)(0)
  println (s"Bell numbers: ${result.mkString(" ")}")
}

Output:

Bell numbers = 1 1 2 5 15 52 203 877 4140 21147

Bell numbers in Python

Same algorithm again. As in Scala, the Bell triangle is mapped on a square matrix, with only the items of the triangular area actually relevant (other positions are set to 0).

max = 10
tr = [[0] * max for i in range(max)]
tr[0][0] = 1
for row in range(1, max):
    tr[row][0] = tr[row - 1][row - 1]
    for i in range(1, row+1):
        tr[row][i] = tr[row][i-1] + tr[row - 1][i-1];

print( [row[0] for row in tr] )

Output:

[1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147]

Bell numbers in Julia

We also allocate a square matrix and populate it with 0’s. Only the items of the triangular area are relevant. A slight difference is that we populate a result array when we compute the first item of each row.

max = 10
tr = zeros(Int32, max, max)
tr[1, 1] = 1
results = ones(Int32, max)
for row = 2:max
    res = tr[row - 1, row - 1]
    tr[row, 1] = res
    results[row] = res
    for i = 2:row
        tr[row, i] = tr[row, i-1] + tr[row - 1, i-1]
    end
end
for n in results print("$n ") end

Output:

$ julia bell.jl
1 1 2 5 15 52 203 877 4140 21147

Bell Numbers in C

We also allocate a square matrix. Only the items of the triangular area are populated and relevant. We also populate a result array when we compute the first item of each row.

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

int main() {
    int tr[MAX][MAX];
    tr[0][0] = 1;
    int results[MAX] = {1};
    for (int row = 1; row < MAX; row++) {
        int res = tr[row - 1][row - 1];
        tr[row][0] = res;
        results[row] = res;
        for (int i = 1; i <= row; i++) {
            tr[row][i] = tr[row][i-1] + tr[row - 1][i-1];
        }
    }
    printf("The ten first Bell numbers are: %i ", (results[0]));
    for (int i = 1; i < MAX; i++) {
        printf("%d ", results[i]);
    }
    printf("\n");
    return 0;
}

Output:

$ ./a.out
The ten first Bell numbers are: 1 1 2 5 15 52 203 877 4140 21147

Bell Numbers in Awk

Just as in Julia and in C, we also allocate a square matrix. Only the items of the triangular area are populated and relevant. We also populate a result array when we compute the first item of each row.

BEGIN {
    max = 10
    tr[0, 0] = 1
    results[0] = 1
    for (row = 1; row < max; row++) {
        res = tr[row -1, row -1]
        tr[row, 0] = res
        results[row] = res
        for (i = 1; i <= row; i++) {
            tr[row, i] = tr[row, i-1] + tr[row - 1, i-1]
        }
    }
    printf("First Bell numbers are: %d ", results[0])
    for (i = 1; i < max; i++) printf ("%d ", results[i])
    printf("\n");
}

Output:

$ awk -f bell.awk
First Bell numbers are: 1 1 2 5 15 52 203 877 4140 21147

Bell Numbers in Ruby

I had some trouble getting the syntax right for declaring bi-dimensional arrays (and the error messages are less than awesome). But it eventually worked. Note that Ruby has this nice feature that you can use the #{ ... } to interpolate some code (e.g. the result of an expression) within a string.

max = 9
tr = Array.new(max+1){Array.new(max+1)}
tr[0][0] = 1
results = [1]
for row in 1..max
    tr[row][0] = tr[row - 1][row -1]
    results << tr[row][0]
    for i in 1..row
        tr[row][i] = tr[row][i-1] + tr[row - 1][i-1]
    end
end
puts "The #{max+1} first Bell numbers are: #{results.join(" ")}"

Output:

The 10 first Bell numbers are: 1 1 2 5 15 52 203 877 4140 21147

Note: I tried to initialize max to 15 in order to generate the first 16 Bell numbers and check the program’s correctness, and the output shows that Bell numbers are growing very rapidly (faster than a geometric progression):

The 16 first Bell numbers are: 1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 1382958545

Bell Numbers in Pascal

As mentioned above, I took up Pascal for the first time since 1990 for task # 1. So I thought I could implement tack # 2 also in Pascal and it turned out to be quite easy:

program bell;
const
    max = 9;

var
    tr: array [0..max, 0..max] of integer;
    row, i : integer;

begin
    tr[0, 0] := 1;
    for row := 1 to max do
        begin
            tr[row, 0] := tr[row - 1, row -1];
            for i := 1 to row do  
                tr[row, i] := tr[row, i-1] + tr[row - 1, i-1]; 
        end;
    write('The first Bell numbers are: ');
    for row :=0 to max do
        write(tr[row, 0], ' ');
    writeln;    
end.

Output:

The first Bell numbers are: 1 1 2 5 15 52 203 877 4140 21147

Bell Numbers in D

This program is quite similar to the C program, with only a few syntax variations:

import std.stdio;

void main() {
    enum MAX = 10;
    int tr[MAX][MAX];
    tr[0][0] = 1;
    int results[MAX] = 1;
    for (int row = 1; row < MAX; row++) {
        tr[row][0] = tr[row - 1][row - 1];
        results[row] = tr[row][0];
        for (int i = 1; i <= row; i++) {
            tr[row][i] = tr[row][i-1] + tr[row - 1][i-1];
        }
    }    
    writeln("The first 10 Bell numbers are: ", results);
}

Output:

The first 10 Bell numbers are: [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147]

Bell Numbers in Go

Except for small syntactic differences, the program is again quite similar to the C or D implementations.

package main

import "fmt"

func main() {
    const MAX int = 10
    var tr [MAX][MAX]int
    tr[0][0] = 1
    var results [MAX]int
    for row := 1; row < MAX; row++ {
        tr[row][0] = tr[row-1][row-1]
        results[row] = tr[row][0]
        for i := 1; i <= row; i++ {
            tr[row][i] = tr[row][i-1] + tr[row-1][i-1]
        }
    }
    fmt.Println("The first Bell numbers are: ", results)
}

Output:

The first Bell numbers are:  [0 1 2 5 15 52 203 877 4140 21147]

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 25, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.

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

Spoiler Alert: This weekly challenge deadline is due in a couple of days (April 11, 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.

Self-Descriptive Numbers

Write a script to display the first three self-descriptive numbers. As per Wikipedia, the definition of Self-descriptive Number is:

In mathematics, a self-descriptive number is an integer m that in a given base b is b digits long in which each digit d at position n (the most significant digit being at position 0 and the least significant at position b−1) counts how many instances of digit n are in m.

For example, 1210 is a four-digit self-descriptive number:

position 0 has value 1 i.e. there is only one 0 in the number
position 1 has value 2 i.e. there are two 1 in the number
position 2 has value 1 i.e. there is only one 2 in the number
position 3 has value 0 i.e. there is no 3 in the number

The process of computing self-descriptive numbers can become very slow as the base becomes large. Although this is not really necessary for computing only the first 3 self-descriptive numbers, we can include some simple performance optimization. The Wikipedia article states that a self-descriptive number in base b must be a multiple of that base (or equivalently, that the last digit of the self-descriptive number must be 0). So we can skip the check for any integer whose representation in a given base doesn’t end with 0. Also, all self-descriptive numbers have digit sums equal to their base. We can filter out those that don’t match these two conditions.

Some further optimizations (when the base is larger than or equal to 7) are possible as described in my blog post of Jan. 19, 2020 on the same subject. They are not needed here.

Self-Descriptive Numbers in Raku

We iterate on bases from 2 to infinity (and exit the loop when we reach the target number of self-descriptive numbers). Then, for a given base, we loop over all integers having a number of digits equal to the base. For each such integer, we filter out those not ending with 0 or whose digit sum is not equal to the base. For the integers not filtered out, we check that each digit d at position n counts how many instances of digit n are in such integer.

use v6;
constant MAX = 4;

my $*count = 0;
for 2..Inf -> $base {
    check-self-desc($base);
    last if $*count >= MAX;
}   

sub check-self-desc (Int $base) {
    my $found = False;
    for $base ** ($base -1) .. $base ** $base -1 -> $num {
        my $num-in-b = $num.base($base);
        next unless $num-in-b ~~ /0$/;
        my @digits = $num-in-b.comb;
        next if $base != [+] @digits;
        my $success = True;
        for 0..$base - 1 -> $rank {
            if (+ $num-in-b.indices($rank) != @digits[$rank]) {
                $success = False;
                last;
            }
        }
        if $success {
            say "Number in base $base: $num-in-b; decimal: $num";
            $*count++;
            $found = True;
            return if $*count >= MAX;
        }   
    }
    say "No self-descriptive number for base $base" unless $found;
}

This program displays the following output:

$ raku self-descr.raku
No self-descriptive number for base 2
No self-descriptive number for base 3
Number in base 4: 1210; decimal: 100
Number in base 4: 2020; decimal: 136
Number in base 5: 21200; decimal: 1425

I wanted to investigate a bit more and decided to change MAX to 4 and to measure the process duration:

$ time raku self-descr.raku
No self-descriptive number for base 2
No self-descriptive number for base 3
Number in base 4: 1210; decimal: 100
Number in base 4: 2020; decimal: 136
Number in base 5: 21200; decimal: 1425
No self-descriptive number for base 6
Number in base 7: 3211000; decimal: 389305

real    0m5,684s
user    0m0,031s
sys     0m0,030s

So it takes about 5.7 seconds. If we comment out the two performance optimizations described above, we get the following result:

$ time raku self-descr.raku
No self-descriptive number for base 2
No self-descriptive number for base 3
Number in base 4: 1210; decimal: 100
Number in base 4: 2020; decimal: 136
Number in base 5: 21200; decimal: 1425
No self-descriptive number for base 6
Number in base 7: 3211000; decimal: 389305

real    0m17,857s
user    0m0,015s
sys     0m0,031s

So, about 17.9 seconds without the performance enhancement, the optimizations are worth the effort.

Self-Descriptive Numbers in Perl

This is a port of the above Raku program to Perl. Since Perl doesn’t have any built-in function to convert numbers to a given base, we have to implement our own to_base_b subroutine.

use strict;
use warnings;
use feature qw /say/;
use constant DIGITS => ('0'..'9', 'A'..'Z');
use constant MAX => 3;
my $count = 0;

sub to_base_b { # Converts decimal number to base b string
    my($dec, $base) = @_;
    my @digits;
    while ($dec) {
        unshift @digits, (DIGITS)[$dec % $base];
        $dec = int($dec/$base);
    }
    return join "", @digits;
}

sub check_self_desc {
    my $base = shift;
    for my $num ($base ** ($base -1) .. $base ** $base -1) {
        my $num_in_b = to_base_b ($num, $base);
        next unless $num_in_b =~ /0$/;
        my @digits = split //, $num_in_b;
        my $sum = 0;
        $sum += $_ for split //, $num_in_b;
        next if $sum != $base;
        my $success = 1;
        for my $rank (0..$base - 1) {
            my $nb_digits = $digits[$rank];
            my $num_occ = $num_in_b =~ s/$rank/$rank/g;
            if ($num_occ != $nb_digits) {
                $success = 0;
                last;
            }
        }
        if ($success) {
            say "Number in base $base: $num_in_b; decimal: $num" ;
            $count++;
            return if $count >= MAX;
        }
    }
}

for my $base (2..10) {
    check_self_desc($base);
    last if $count >= MAX;
}

Output:

$ perl self-descr.pl
Number in base 4: 1210; decimal: 100
Number in base 4: 2020; decimal: 136
Number in base 5: 21200; decimal: 1425

Task 2: List Methods

Write a script to list methods of a package/class.

Example

package Calc;

use strict;
use warnings;

sub new { bless {}, shift; }
sub add { }
sub mul { }
sub div { }

1;

Output:

BEGIN
mul
div
new
add

The task is not entirely clear. Maybe we are asked to load a class and introspect the available methods, but I’ll consider it is more probable that we’re supposed to parse the file and list the methods defined in it. I’ll also suppose that we should look for methods in the programming language in which they are defined; in other words, we’ll be looking for Raku methods in Raku and Perl methods in Perl, although we could obviously perform cross-language searches (for example, use Raku to look for methods in a Perl module, or vice-versa).

List Methods in Raku

Raku methods are defined with the method keyword. Raku identifiers can contain alphanumeric characters, plus - dashes and ' single quotes. In addition we should avoid finding the method keyword somewhere in a comment. We’ll be looking for the method keyword as the first thing in a code line (except for possible space characters) and capture the identifier coming immediately after.

use v6;

sub MAIN (Str $file-name) {
     for $file-name.IO.lines -> $line {
        say ~$0 if $line ~~ /^\s* method \s+ (<[-'\w]>+)/;
    }
}

Example output:

$ ./raku find-methods.raku linked_list.raku
make-array
gist

List Methods in Perl

In Perl, methods use the sub keyword.

use strict;
use warnings;
use feature qw /say/;

while (<>) {
    say $1 if /^\s*sub\s+(\w+)/;
}

Output:

$ echo 'package Calc;
>
> use strict;
> use warnings;
>
> sub new { bless {}, shift; }
> sub add { }
> sub mul { }
>
sub div { }
>
> 1; '  |  perl  find-methods.pl
new
add
mul
div

Of course, this is so simple that a Perl one-liner would make sense:

$ echo 'package Calc;
>
> use strict;
> use warnings;
>
> sub new { bless {}, shift; }
> sub add { }
> sub mul { }
> sub div { }
>
> 1;'  |  perl -nE 'say $1 if /^\s*sub\s+(\w+)/;'
new
add
mul
div

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 18, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.

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.