[Purdue-pm] Perl Challenge 018

[Mark Senn]

> 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.

Hi Mark,

Yes, I suggested using a brute force solution to find the longest common
substring of "ABABC", "BABCA", and "ABCBA".  The challenge didn't say
anything about any space restraints, time constraints, or if the
solution would be usedd for bigger problemms.  The challenge used to
include the critieria of only use Perl 5 or Perl 6 but no extra modules
so I didn't use anything not built-in.  (I don't see that criteria
listed on the web page now.)  I was trying to get a solution that was
easy to understand and worked with as little time investment as
possible.  Human time is more expensive than computer time.  The
solution worked using Perl 6 stuff I already knew.  I agree with you, if
the problem was bigger and needed to be solved to be solved using less
computer time or space I should have used a different method.  (At a
recent Perl Mongers meeting I think Joe Kline may have used the phrase
"conserving a limitless resource" in connection with there is an
abundance of computer time and space to work on small problems.)

-mark