[Purdue-pm] Perl Challenge 018
Ward, Mark Daniel
mdw at purdue.edu
Tue Jul 30 05:05:11 PDT 2019
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
More information about the Purdue-pm
mailing list