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.
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_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.
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 Athanasius’ solution. 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% --
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
For those who haven’t try this tasks before, do give it a shot.
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.
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.