laurent_r

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

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on November 21, 2021 at 24:00). 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: JostSort

You are given a list of numbers.

Write a script to implement JortSort. It should return true/false depending if the given list of numbers are already sorted.

Example 1:

Input: @n = (1,2,3,4,5)
Output: 1

Since the array is sorted, it prints 1.

Example 2:

Input: @n = (1,3,2,4,5)
Output: 0

Since the array is NOT sorted, it prints 0.

I had never heard about JortSort before. It seems to be a sorting toolkit, which, assuming I understood correctly, appears to be rather inefficient. To check whether an array of values is correctly sorted, it appears to sort the array and to compare the sorted result with the original array. Sorting an array usually has an algorithmic complexity of at least O(n x log n) (where n is the size of the array), whereas comparing each item with the preceding (or next) one in a simple loop has a linear complexity of O(n) and can thus be significantly faster. We will use the later solution.

JortSort in Raku

The built-in Raku [] reduction metaoperator makes it possible to apply an operator to each pair of elements of a list. In our case, using it with the <= operator, it will return True if each element is smaller than or equal to the next element. Since this operator returns a Boolean value (True or False), and since the task is to print 0 or 1, we simply numify the Boolean value by applying the unary + operator to the result. This is quite simple:

use v6;

sub jortsort (@in) {
    + [<=] @in;  # + numifies the Boolean result
}

for (1,2,3,4,5), (1,3,2,4,5) -> @test {
    say "@test[] -> ", jortsort @test;
}

This script displays the following output:

$ raku ./jortsort.raku
1 2 3 4 5 -> 1
1 3 2 4 5 -> 0

Actually, this is so simple that we can easily make a very small Raku one-liner:

$ raku -e 'say + [<=] @*ARGS' 1 2 3 4 5
1

$ raku -e 'say + [<=] @*ARGS' 1 2 4 3 5
0

JortSort in Perl

Perl doesn’t have a reduction meta-operator, but it is almost as simple to use a for loop and compare each element with the previous one. We return 0 if any pair of elements fails the comparison test, and return 1 if the loop reaches the array last item:

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

sub jortsort {
    my @in = @_;
    for my $i (1..$#in) {
        return 0 if $in[$i - 1] > $in[$i];
    }
    return 1;
}

for my $a ([1,2,3,4,5], [1,3,2,4,5]) {
    say "@$a -> ", jortsort @$a;
}

This script displays the following output:

$ perl jortsort.pl
1 2 3 4 5 -> 1
1 3 2 4 5 -> 0

Task 2: Long Primes

Write a script to generate first 5 Long Primes.

A prime number (p) is called Long Prime if (1/p) has an infinite decimal expansion repeating every (p-1) digits.

Example:

7 is a long prime since 1/7 = 0.142857142857...
The repeating part (142857) size is 6 i.e. one less than the prime number 7.

Also 17 is a long prime since 1/17 = 0.05882352941176470588235294117647...
The repeating part (0588235294117647) size is 16 i.e. one less than the prime number 17.

Another example, 2 is not a long prime as 1/2 = 0.5.
There is no repeating part in this case.

Long Primes in Raku

Raku has a built-in method, base-repeating, provided by the role Rational, that splits a Rational into a base and a repeating pattern part. So we simply loop through an infinite lazy list of prime integers and return True is the repeating part is one less than the input prime, and we stop the loop when we have enough long primes.

my @primes = grep { .is-prime }, 1..Inf;
my $count = 0;

sub is-long-prime ( UInt $den) {
    my ($non-rep, $repeating) = (1 / $den).base-repeating;
    return True if $repeating.chars == $den - 1;
}
for @primes -> $candidate {
    say $candidate and ++$count if is-long-prime $candidate;
    last if $count >= 5
}

This script displays the following output:

$ raku ./long-primes.raku
7
17
19
23
29

Long Primes in Perl

In Perl, we implement a generate_primes subroutine to generate a list of prime numbers. We also implement an invert subroutine to compute the inverse 1/n of the input integer n; we do this because we need this inverse to have a relatively large number of significant decimal digits (more than what Perl arithmetic division can provide). Then we use a regular expression to find possible repeating sequences smaller than the input prime. The first 3 primes (2, 3, and 5) behave somewhat differently from the subsequent primes and are not long primes so, rather than implementing another test specifically for them, we really start our search at the fourth prime, 7. Frankly, I’m really not sure that my regex works correctly for moderately or very large input values, but it does work fine for values much larger than just the first five long primes.

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

my $count = 0;

sub generate_primes {  
    my @primes = (2, 3, 5, 7);
    my $current = 9;
    while (1) {
        my $prime = 1;   # True
        for my $i (@primes) {
            my $i_sq = $i * $i;
            last if $i_sq > $current;
            $prime = 0, last if $current % $i == 0;
        }
        push @primes, $current if $prime;;
        $current += 2;
        last if $current > MAX;
    }
    return @primes;
}

sub invert {
    my $n = shift;
    my $dividend = 1;
    my $result;
    my $max = 2 * $n;
    while (1) {
        $dividend *= 10;
        $result .= int($dividend / $n);
        return $result if length $result >= $n;
        my $remainder = $dividend % $n;
        $dividend = $remainder;
    }
    return $result;
}   

my @primes = generate_primes;
for my $candidate (@primes[3..30]) {

    my $decimals = invert $candidate;
    my $len = length $decimals;
    ++$count and say "$candidate  $decimals " unless $decimals =~  /(\d{3,$len})\1/;
    last if $count >= 5;
}

In this implementation, the program displays the long primes detected, as well as the decimal digit sequences for those primes, to help checking the results. The changes to be made to remove the decimal digit sequences should be obvious. As it is, this program displays the following output:

$ perl long-primes.pl
7  1428571
17  05882352941176470
19  0526315789473684210
23  04347826086956521739130
29  03448275862068965517241379310

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