Perl Weekly Challenge: Week 139

Challenge 1:

JortSort

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.

My daughter Shailaja is studying Computer Science in university and taking Data Structures and Algorithms at the moment. When I said I was going to implement JortSort, her reaction having recently implemented sorts of the bubble, quick, merge, radix was to groan "oh no not another one!" Which I confess was my initial reaction too. Happily for both of us, it is just a joke and can be implemented quite easily. As a one-liner in Raku as a matter of fact.

say @*ARGS ~~ @*ARGS.sort({ $^a <=> $^b }) ?? 1 !! 0'

(Full code on Github.)

This takes the list of numbers as command line arguments and compares it to a sorted version of the same list. If the two are equivalent as specified by the ~~ ("smartmatch") operatior 1 is printed out or else 0. There is also an eqv operator I could have used for the same purpose but smartmatch is more versatile and easier for me to remember.

"But wait a minute" you might say. Doesn't sorting the list defeat the whole point of JortSort which is supposed to tell if the list has already been sorted? Well, how could you tell if the list has already been sorted? You would have to compare each number with its successor and determine that the successor is greater. I figure that .sort() is already doing that behind the scenes and is optimized enough to do nothing more than that if the list is already in the right order.

I figured that the Perl version would be nothing more than a copy of Raku modulo a few syntax changes but in fact there were a couple of hurdles. For instance Perl has smartmatch but it is still considered experimental and you will be warned about that. You have to specifically:

use experimental 'smartmatch';

...in order to supress the warning it. On the command line you can use the -M switch like this:

perl -Mexperimental=smartmatch

Another problem is that the ~~ did not work on arrays although the perlop perldoc suggests that it should. Atleast I was printing nothing instead of 1 or 0. Unfortunately I do not have time to look into why that is. For now I just made the arrays into array references and that works:

say [@ARGV] ~~ [sort { $a <=> $b } @ARGV] ? 1 : 0;

(Full code on Github.)

Challenge 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.

I thought I had an ingeneous solution for this.

Subtract one from a number p.
Multiply this number by 2 and find that many digits of decimal expansion for 1/p This requires arbitrary size rational numbers but both Raku and Perl have modules for that.
Compare the first half of the expansion to the second half. If they are the same, you have found a long prime.

This method works; it will find 7 and 17 for instance. But it will give you too many false positives. For instance the reciprocal for 3 would be 0.3333 which repeats every digit not every 2 digits. or 13 would would give 0.076923076923076923076923 which repeats every 6 digits not the 12 we want.

Going back to the drawing board I discovered there is a method for detecting the exact length of the period of a repeating decimal and this page gave the algorithm for it in C++. It was easy to convert it into Raku.

sub period(Int $n) {
    my $remainder = 1;
    my $i = 1;
    my %position;

    loop {
        $remainder = (10 * $remainder) % $n;
        if %position{$remainder}:exists {
            return $i - %position{$remainder};
        }
        %position{$remainder} = $i;
        $i++;
    }
}

Now we just start counting from 2 onwards (because we only want to consider odd primes, the first number to test is actually 3.)

    my $p = 2;
    my @longPrimes;

    while (@longPrimes.elems < 5) {
        $n++;

If the number is not a prime, it is definitely not a long prime so we can move on to the next number.

        unless $p.is-prime {
            next;
        }

If the period of the number is one less than p, we have a long prime so we add it to our list. if period($p) == $p - 1 { @longPrimes.push($p); }

...and so on until we have five long primes.

Then we can print them out.

    @longPrimes.join(q{, }).say;

(Full code on Github.)

For Perl we need a way to detect prime numbers. Fortunately, I have an isPrime() function I've used in previous challenges.

The rest of the code looks like this.

sub period {
    my ($n) = @_;
    my $remainder = 1;
    my $i = 1;
    my %position;

    while (1) {
        $remainder = (10 * $remainder) % $n;
        if (exists $position{$remainder}) {
            return $i - $position{$remainder};
        }
        $position{$remainder} = $i;
        $i++;
    }
}

my $p = 2;
my @longPrimes;

while (scalar @longPrimes < 5) {
    $n++;

    unless (isPrime($p)) {
        next;
    }

    if (period($p) == $p - 1) {
        push @longPrimes, $p;
    }
}

say join q{, }, @longPrimes;

(Full code on Github.)

The first five long primes are: 7, 17, 19, 23 and 29.