Kian-Meng Ang Weekly Review: Challenge - 008

Wednesday, May 22, 2019| Tags: Perl5

Follow up on this week review of the Perl Weekly Challenge #008 of answers submitted by all the participants. Read the full question list and the recap of the challenge to have an overview before we proceed with our review.


Challenge #1


Looking through all the submissions, there are several approaches used by these participants to calculate the first five perfect numbers which are 6, 28, 496, 8128, and 33550336. The first approach is to calculate by brute force (Adam Russell, Dave Jacoby, Gustavo Chaves, Ruben Westerberg, Laurent Rosenfeld, and Guillermo Ramos). Result was slow (took a few hours) as the bottleneck is on the calculation of fifth perfect number, a very large number, as in around 33 millions. This is a time complexity or O(n) problem where we have to iterate through all the numbers lesser than n. A better or optimized approach was to generate the series using algorithm through Euclid–Euler theorem (Alicia BielsaMaxim Nechaev, Athanasius, Daniel Mantovani, Laurent Rosenfeld, Jaldhar H. Vyas, Guillermo RamosJames Smith, and Yozen Hernandez). The shortest and Perl way answer using the Euclid-Euler theorem belongs to James Smith. Read his write-up on his approach to tackle this problem.

use feature qw(say);
use List::Util qw(notall);
my $q = 1;
foreach(1..7) {
  ($q<<=1)++; ## $q is a sequence of the form 2^n-1;
  redo if notall { $q%$_ } 2..($q-1); ## Only contine if $q is mersenne prime
  say $q*($q+1)/2;
}

One interesting observation while went through all these answers was how common the List::Util module being used and yet, in totally different manners. Even though the approach to solve the question was similar, different participants have different coding styles. Hence, we have seen sum, uniqnum, sum0, and notall functions being applied differently.


Challenge #2


This is a straightforward question and some participant should have already solved it in challenge #2 in Perl Weekly Challenge #003 to display Pascal’s triangle in tree or triangle form. To center a list of string, we need three steps. First, we need to find the longest length of the string from the list. If we don’t want to use external module, we can do it using the default language constructs. For example, Laurent Rosenfeld calculated the maximum length by simply looping through all the lines’ length.

my $max_size = 0;
for my $str (@_) {
    my $length = length $str;
    $max_size = $length if $length > $max_size;
}

While Ruben Westerberg used an one-liner approach.

my $max=0;
map { chomp; ($max < length($_ )) ? $max=length($_):();} @_;

And Guillermo Ramos used a more explicit map-reduce approach.

use List::Util qw(max reduce);
......
my $maxlen = reduce { max($a, length $b) } 0, @_;

Meanwhile, Adam Russell used an unorthodox approach by using eval and tr to calculate each line length.

foreach my $line (@words){
    $line_length{$i} = do{
        $line =~ tr/ [a-z][A-Z]//;
    };
    $max_length = $line_length{$i} if $line_length{$i} > $max_length;
    $i++;
}

Next, we find the number of space to prepend to the current line of string by calculating the difference of the longest string length and current line and divided it by 2. Almost all participants was using this formulae. The solution by Gustavo Chaves illustrates this succinctly.

sub center {
    my @lines = @_;
    my $max = max map {length} @lines;
    return map {' ' x (($max - length) / 2) . $_} @lines;
}

And off course, there will a relevant CPAN module, String::Pad, in this case, that have such functionality.


Challenge #3


Joelle Maslak is the only participant who took up this last and optional challenge. Nevertheless, the solution was featureful, comprehensive, and very well coded. Furthermore, it was also one of the earliest submissions and there were even two versions existed for Perl 5 and Perl 6. Hopefully, this solution can turned into a full featured Perl module or console app. There are a few things to take note from the reading the code of this script. It’s okay to use signatures feature or subroutine signature even though it’s still under experimental since it was first released in v5.20. If you’re developing for internal system and don’t release your code for external consumption, then it’s a good choice to use this. Subroutine signature did reduce the need for parameter assignment. The use of Perl6::Slurp module was a deliberated choice since the author have submitted solutions for both Perl 5 and 6 and want to maintain compability and minimize changes.

Related blog posts related to this week challenge.

1) Arne Sommer gave us a walk through on solving both problem in Perl 6 especially how long it took to calculate the fifth perfect numbers.

2) Adam Russel wrote about different approaches on optimizing the perfect numbers calculation from brute force, algorithmic, parallelization by threading, and delegation by integrating C++ and Perl with SWIG.

3) Dave Jacoby blogged about the difference about brute force and algorithmic approach.

4) Laurent Rosenfeld provided us with mathematical background on different algorithmic approaches in calculating Perfect numbers.

5) Francis Whittle wrote about Perl 6 solutions post on both challenges.

6) Simon Proctor also wrote another Perl 6 solution post.

SO WHAT DO YOU THINK ?

If you have any suggestions or ideas then please do share with us.

Contact with me