[Purdue-pm] Perl Challenge 018

Ward, Mark Daniel mdw at purdue.edu
Mon Jul 29 02:29:20 PDT 2019


Dear Mark,

I think I did write something stupid last night, namely, I think I wrote that the brute force solution is exponential, but it might only be quadratic.  Still a lot worse than linear!

Warmest regards,

Mark

> On Jul 28, 2019, at 9:54 PM, Ward, Mark Daniel <mdw at purdue.edu> wrote:
> 
> Dear Mark,
> 
> I might be misreading your email, but I think you are suggesting in Task #1 to use a brute force solution.  If you touch all substrings for a word, then you will take a length of time that is exponential in the length of the word.  In contrast, however, there is actually a solution that is linear in terms of the length of the words.
> 
> https://en.wikipedia.org/wiki/Longest_common_substring_problem
> 
> The suffix tree solution -- which yields this optimal solution -- is really beautiful in its own right, and it doesn't need to be a bunch of complicated code.  It can be done easily, especially if you have a library with a suffix tree included.  I don't think this is over-engineering.  I think it gets to the heart of the solution.
> 
> So I find it hard to get excited about your suggestion to "put all substrings for word[i] in set[i]" because this will take an exponential number of steps, in terms of the length of the word, and that is entirely inefficient.
> 
> Am I saying something stupid?  Maybe!  That is the danger of writing an email late at night.  Well, it's only 10 PM here (not midnight) since I'm in Denver at the moment, but that is still relatively late for me.
> 
> Warmest regards,
> 
> Mark
> 
> 
>> On 7/28/19 11:33 PM, Mark Senn wrote:
>> My blog about Perl Weekly Challenge - 018 is at
>>     https://engineering.purdue.edu/~mark/pwc-018.pdf
>> 
>> It contains the two task descriptions and my Perl 6 (Perl 5 completely
>> redesigned and rewritten from the ground up, even code as simple as
>> $array[1] = 1 doesn't work now---but it is worth it---Perl 6 is a
>> much better language) code to solve the problems.
>> 
>> I quote Jeff Atwood's "The Best Code is No Code At All" and Randall
>> Munroe's xkcd comic strip because many of the solutions to the
>> challenges are way over-engineered.
>> 
>> Task #1: print the longest common substring in two or more substrings.
>> Answer highlights: Put all substrings for word[i] in set[i] and use
>> Perl 6's set intersection hyperoperator to find the longest substring.
>> 
>> Task #2: implement priority queues.  Answer doesn't use classes or
>> methods I had to write.  Just two parallel arrays.
>> 
>> First get it working and if needed, then make it better.  And because
>> the specs for the problems don't give any info about space or time
>> constraints there is no need to make it better.
>> 
>> -mark
>> _______________________________________________
>> Purdue-pm mailing list
>> Purdue-pm at pm.org
>> https://mail.pm.org/mailman/listinfo/purdue-pm


More information about the Purdue-pm mailing list