Kian-Meng Ang Weekly Review: Challenge - 018

Saturday, Aug 3, 2019| Tags: Perl

Continues from previous week.

Feel free to submit a merge request or open a ticket if you found any issues with this post. We highly appreciate and welcome your feedback.

For a quick overview, go through the original tasks and recap of the weekly challenge.


Task #1


If you need to have a quick overview how to solve the challenge, read the submitted solutions by Mark Anderson, Jamie, and E. Choroba (read his detailed blog post on this). These solutions were short and easily understood due to the brevity and clarity of the code. Read Mark Senn’s post on different dimensions in coding.

There were a few strategies used by participants to tackle this longest common substring problem. No participant use this but String::LCSS and String::LCSS_XS are the CPAN modules that can be used to solve this.

The common approach was generating substrings, count, filter, and find the highest occurrences. The main difference was the implementation of these steps. For example, Athanasius stored the list of substrings as set using the Set::Scalar CPAN module. Likewise, Joelle Maslak solved it by finding the intersection of all substrings within an array.

Adam Russell, E. Choroba, Roger Bell West (inspired by the pseudocode) solved the task using the recommended suffix tree algorithm by building a generalized suffix tree. Adam Russell went a step further by implementing the suffix array data structure as an external Perl module. Ruben Westerberg’s solution was rather different and unique.


Task #2


If we remembered correctly, the first task where we have a clear defined problem. Basically, participant needs to fill up the implementation details of a list of method definitions. Even Duncan C. White agreed with that.

Now, for some submitted solutions that caught our attention for this task.

Instead of just plain hash to store and group the queue item by priority, Duane Powel opted for a nested hash references data structure. Adam Russell did something similar but with the help of Class::Struct CPAN module. There was another way, more abstract approach that use the List::Priority CPAN module as seen in Athanasiussolution. Jaldhar H. Vyas went a step further to create almost a CPAN module. He even wrote details documentation in POD in his answer!

Instead of creating a Perl module, Laurent Rosenfeld used anonymous subroutines to implement the interfaces in a functional programming manner. This was rather distinctive among all solutions. Lubos Kolouch did something similar, so was Andrezgz, but with a very comprehensive test coverage and cases. Another participant with good test coverage was Yozen Hernandez.

The most comprehensive solution submitted this week belongs to E. Choroba. There were two implementations either an array or a heap data structure, a benchmark (array is faster, see result below), and test coverage.

           Rate  heap array
    heap  120/s    --  -56%
    array 272/s  126%    --

Where Jaldhar H. Vyas used Moo, Joelle Maslak used Moose to create a Perl module. The used of Test2::V0 CPAN module was the first we seen so far in all challenges.


Task #3


Slow week but at least there were submissions to this task this time. For Perl 5, we have the usual Joelle Maslak and for Perl 6, Randy Lauen and Joelle Maslak.

After so many weeks of reviewing this optional Task #3, we observed that Perl 6 solutions were definitely more structure due to a consistent Object-Oriented (OO) support in Perl 6 and Cro::HTTP::Client module.

For those who haven’t try this tasks before, do give it a shot.


Blog Posts


Regular posts by some of the participants.

(1) Substrings and Queues with Perl 6 by Arne Sommer

The usual step-by-step walk through in Perl 6.

(2) Perl Weekly Challenge - 018 by Mark Senn

Mark Senn is back for this challenge and a good write-up on different coding dimensions. Recommended read.

(3) Perl Weekly Challenge 018 by Adam Russell

Read how he approached the challenge using Perl modules.

(4) Perl Weekly Challenge # 18: Longest Common Substrings, Priority Queues, and a Functional Object System by Laurent Rosenfeld

Very detailed notes on how he tackled the problems and why he picked functional approach. Recommended read.

(5) Perl Weekly Challenge 18 by Roger Bell West

Read how he translated the pseudocode for Task #1 into Perl and the problems encountered.

(6) Perl Weekly Challenge 018/1: Longest Common Substring by E. Choroba

He have outdid himself this time, especially the generating and visualizing the suffix tree. Recommended read.

(7) Perl Weekly Challenge 018/2: Priority Queue by E. Choroba

A discussion on binary heap for Task #2. Also another recommended read.

SO WHAT DO YOU THINK ?

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

Contact with me