[Purdue-pm] Perl Challenge 018

[Ward, Mark Daniel]

Dear Mark,

Aha!  I understand your motivation.  Thanks for sharing!

I wonder if you ever worked on the Project Euler problems?

https://projecteuler.net/

I think that these problems require "efficient" solutions, i.e., they 
will have some problems for which it is necessary to have small space 
requirements and/or fast execution time.  I think that there is a 
1-minute execution rule on the site.  This prevents some brute-force 
solutions, to some of the harder problems.

I'm guessing that you know about this site.... but just curious!

Warmest regards,

Mark


On 7/29/19 10:37 AM, Mark Senn wrote:
>> 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