[Purdue-pm] Perl Challenge 018

[Mark Senn]

Dear Mark Daniel Ward,

I've heard of Project Euler but haven't worked on any problems there.

Damian Conway wrote in
http://blogs.perl.org/users/damian_conway/2019/07/chopping-substrings.html
    The “best practice” solution is a technique known as suffix trees, which
    requires some moderately complex coding. However, we can get very
    reasonable performance for strings up to hundreds of thousands of
    characters long using a much simpler approach.

Damian's entire Perl 6 program to find the longest common substring for
strings given on the command line is

sub MAIN (*@strings) {
    .say for
        max :all, :by{.chars},
            keys [∩] @strings».match(/.+/, :ex)».Str
}

He discusses larger problems there and lists code for an
O(N log N) algorithm.  (I have not tried that code.)

Perl Weekly Challenge - 020, Task #1 is
    Write a script to accept a string from command line and split it on
    change of character. For example, if the string is “ABBCDEEF”, then it
    should split like “A”, “BB”, “C”, “D”, “EE”, “F”.
I'm going to try and solve this in Perl 6 using the comb command.
I think that will make it easy---but I haven't tried it yet.

Regards, Mark Senn


>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
>_______________________________________________
>Purdue-pm mailing list
>Purdue-pm at pm.org
>https://mail.pm.org/mailman/listinfo/purdue-pm