[Purdue-pm] Perl Challenge 018

[Ward, Mark Daniel]

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