laurent_r

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

Spoiler Alert: This weekly challenge deadline is due in several days from now (September 1, 2019). This blog post offers some solutions to this challenge, please don't read on if you intend to complete the challenge on your own.

Challenge # 1: nth Order Difference Series

Create a script that prints nth order forward difference series. You should be a able to pass the list of numbers and order number as command line parameters. Let me show you with an example.

Suppose we have list (X) of numbers: 5, 9, 2, 8, 1, 6 and we would like to create 1st order forward difference series (Y). So using the formula Y(i) = X(i+1) - X(i), we get the following numbers: (9-5), (2-9), (8-2), (1-8), (6-1). In short, the final series would be: 4, -7, 6, -7, 5. If you noticed, it has one less number than the original series. Similarly you can carry on 2nd order forward difference series like: (-7-4), (6+7), (-7-6), (5+7) => -11, 13, -13, 12.

nth Order Difference Series in Perl 5

For this, we will write a simple fwd_diff subroutine to compute the first order difference series of the list of values passed as arguments to it. We do that with map on the indexes of the arguments list (starting at 1).

Then, we use a for loop to call this subroutine the number of times required by the first parameter (the order) passed to the script. Note that if the order is larger than the count of the other items passed to the script, then we cannot compute the result.

#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;

sub fwd_diff {
    return map $_[$_] - $_[$_ - 1], 1..$#_;
}

my ($order, @values) = @ARGV;
my $count = scalar @values;
if ($count <= $order) {
    die "Can't calculate ${order}th series of $count values";
}
my @result = @values;
for (1..$order) {
    @result = fwd_diff @result;
}
say "${order} forward diff of @values is: @result";

Testing with 6 values the forward difference series with orders 1 to 6 displays the following output:

$ perl  fwd_diff.pl 1 5 9 2 8 1 6
1th forward diff of 5 9 2 8 1 6 is: 4 -7 6 -7 5

$ perl  fwd_diff.pl 2 5 9 2 8 1 6
2th forward diff of 5 9 2 8 1 6 is: -11 13 -13 12

$ perl  fwd_diff.pl 3 5 9 2 8 1 6
3th forward diff of 5 9 2 8 1 6 is: 24 -26 25

$ perl  fwd_diff.pl 4 5 9 2 8 1 6
4th forward diff of 5 9 2 8 1 6 is: -50 51

$ perl  fwd_diff.pl 5 5 9 2 8 1 6
5th forward diff of 5 9 2 8 1 6 is: 101

$ perl  fwd_diff.pl 6 5 9 2 8 1 6
Can't calculate 6th series of 6 values at fwd_diff.pl line 13.

nth Order Difference Series in Perl 6

I would have liked to be able to use a pointy block syntax with two parameters, but that does not work because the loop will consume two values at each step, as shown under the REPL:

> for <5 9 2 8 1 6> -> $a, $b {say $b - $a}
4
6
5

So we would need to pre-process the input data in order to get twice all values except those at both ends of the input list.

We'll use the rotor built-in function

These are two examples using rotor under the REPL:

> <5 9 2 8 1 6>.rotor(1)
((5) (9) (2) (8) (1) (6))
> <5 9 2 8 1 6>.rotor(2)
((5 9) (2 8) (1 6))

In these examples, rotor groups the elements of the invocant into groups of 1 and 2 elements respectively.

The rotor method can take as parameter a key-value pair, whose value (the second item) specifies a gap between the various matches:

> (1..10).rotor(2 => 1)
((1 2) (4 5) (7 8))

As you can see, we obtain pairs of values, with a gap of 1 between the pairs (item 3, 6 and 9 are omitted from the list). Now, the gap can also be negative and, with a gap of -1, we get all successive pairs from the range:

> <5 9 2 8 1 6>.rotor(2 => -1)
((5 9) (9 2) (2 8) (8 1) (1 6))

This is exactly what we need: we can now subtract the first item from the second one in each sublist.

Continuing under the REPL, we can define the fwd-diff subroutine and use it as follows:

> sub fwd-diff (*@in) { map {$_[1] - $_[0]},  (@in).rotor(2 => -1)}
&fwd-diff
> say fwd-diff <5 9 2 8 1 6>
[4 -7 6 -7 5]
>

OK, enough experimenting with the REPL, we now know how to solve the challenge and can write our program:

use v6;

sub fwd-diff (*@in) { 
    map {$_[1] - $_[0]},  (@in).rotor(2 => -1)
}
sub MAIN (Int $order, *@values) {
    if @values.elems <= $order {
        die "Can't compute {$order}th series of {@values.elems} values";
    }
    my @result = @values;
    for 1 .. $order {
        @result = fwd-diff @result;
    }
    say "{$order}th forward diff of @values[] is: @result[]";
}

Testing with 6 values the forward difference series with orders 1 to 6 displays the following output:

$ fwd-diff.p6 1 5 9 2 8 1 6
1th forward diff of 5 9 2 8 1 6 is: 4 -7 6 -7 5

$ fwd-diff.p6 2 5 9 2 8 1 6
2th forward diff of 5 9 2 8 1 6 is: -11 13 -13 12

$ fwd-diff.p6 3 5 9 2 8 1 6
3th forward diff of 5 9 2 8 1 6 is: 24 -26 25

$ fwd-diff.p6 4 5 9 2 8 1 6
4th forward diff of 5 9 2 8 1 6 is: -50 51

$ fwd-diff.p6 5 5 9 2 8 1 6
5th forward diff of 5 9 2 8 1 6 is: 101

$ fwd-diff.p6 6 5 9 2 8 1 6
Can't compute 6th series of 6 values
  in sub MAIN at fwd-diff.p6 line 9
  in block <unit> at fwd-diff.p6 line 1

Note that I was hoping to get rid of the if @values.elems <= $order test and related die block by using a constraint in the signature of the MAIN subroutine, for example something like this:

sub MAIN (Int $order, *@values where @values.elems > $order) { # ...

but that does not appear to work properly.

Prime Factorization

Create a script that prints Prime Decomposition of a given number. The prime decomposition of a number is defined as a list of prime numbers which when all multiplied together, are equal to that number. For example, the Prime decomposition of 228 is 2,2,3,19 as 228 = 2 * 2 * 3 * 19.

Prime Factorization in Perl 5

The simplest way to solve this challenge is called trial division, i.e. to divide the input number by successive integers until the result is 1. This may appear to be a silly brute force approach, but it turns out to be fairly fast even for the largest integers that Perl 5 can natively handle (there is nothing in the challenge specification that says that we should be able to handle very large numbers). The only performance enhancements that we'll do here is to test even division by 2 and then only by successive odd numbers, and exit the loop when $div becomes too large. I thought for a moment that it would be worth to test only prime numbers, but first finding prime numbers would take more time than what we are likely to win.

We store the prime factors in a hash, with the key being a factor and the value the number of times this factor is a divisor of the input number.

The fact that factors are taken out of the number $num in ascending order garantees the list will only contain primes.

#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;

my $num = shift;
my %factors;
while ($num % 2 == 0) {
    $factors{2} ++;
    $num /= 2;
}
my $div = 1;
while (1) {
    $div += 2;
    while ($num % $div == 0) {
        $factors{$div} ++;
        $num /= $div;
    }
    last if $num == 1;
    ++$factors{$div} and last if $div * 2  > $num;
}
for my $fact (sort { $a <=> $b } keys %factors) {
    say "$fact ** $factors{$fact}";
}

This is the output for some test values:

$ perl prime-fact.pl 12
2 ** 2
3 ** 1

$ perl prime-fact.pl 1200
2 ** 4
3 ** 1
5 ** 2

$ perl prime-fact.pl 1280
2 ** 8
5 ** 1

$ time perl prime-fact.pl 128089876
2 ** 2
463 ** 1
69163 ** 1

real    0m0,055s
user    0m0,015s
sys     0m0,030s


$ time perl prime-fact.pl 1280898769976
2 ** 3
7 ** 2
1783 ** 1
1832641 ** 1

real    0m0,118s
user    0m0,078s
sys     0m0,030s

As we can see on the last test, even for a number with 13 digits and one relatively large prime factor, the computation takes less than 0.2 second. With larger numbers having large prime factors, this might take a few seconds, but that's OK, I'm satisfied with that.

Prime Factorization in Perl 6

Perl 6 has a fast is-prime built-in routine that we can use to build a lazy infinite list of prime numbers, so that we can try even division by prime factors only.

use v6;

my @primes = grep {.is-prime}, 1..*;

sub MAIN (UInt $num is copy) {
    my %factors;
    for @primes -> $div {
        while ($num %% $div) {
            %factors{$div}++;
            $num div= $div;
        }
        last if $num == 1;
        ++%factors{$num} and last if $num.is-prime;
    }
    for sort {$^a <=> $^b}, keys %factors -> $fact {
        say "$fact ** %factors{$fact}";
    }
    say now - INIT now; # timings
}

Note that this line:

++%factors{$num} and last if $num.is-prime;

isn't really needed but brings a significant performance enhancement when the last factor to be found is very large, as it can be seen in the last three tests below (in such cases, Perl 6 runs significantly faster than Perl 5):

$ perl6 prime-fact.p6 12
2 ** 2
3 ** 1
0.0129253

$ perl6 prime-fact.p6 1200
2 ** 4
3 ** 1
5 ** 2
0.01692924

$ perl6 prime-fact.p6 1280
2 ** 8
5 ** 1
0.01294

$ perl6 prime-fact.p6 128089876
2 ** 2
463 ** 1
69163 ** 1
0.052831

$
$ perl6 prime-fact.p6 1280898769976
2 ** 3
7 ** 2
1783 ** 1
1832641 ** 1
0.1106868

$ perl6 prime-fact.p6 128089876997685
3 ** 1
5 ** 1
29 ** 1
37 ** 1
179 ** 1
44460137 ** 1
0.051871

perl6 prime-fact.p6 12808987699768576
2 ** 8
509 ** 1
98300801969 ** 1
0.0469033

Wrapping up

The next week Perl Weekly Challenge is due to 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, September, 8. And, please, also spread the word about the Perl Weekly Challenge if you can.