Perl-Sensitive Sunglasses | |
PerlMonks |
(golf) Collapse repetitions within a stringby Corion (Patriarch) |
on Jun 25, 2003 at 11:55 UTC ( [id://268820]=perlmeditation: print w/replies, xml ) | Need Help?? |
Earlier in the CB, jepri asked about how to best collapse repetitive data within some input stream, and this turned into a nice display of intuitive and expensively backtracking regular expressions. I thought a bit more about the problem and made up some more restrictions : Given a line on STDIN, that line should have "some" repetitions removed, starting with the leftmost repeating sequence. Examples:
The output of a sequence must consist of the shortest sequence plus the repeat count. Example:
If there is stuff that fits in no sequence, it is to be output as well. Example:
The parts of the string are then to be output as they appear within the string. Example for input foofooofooo :
This method is not always optimal, as it does not always find the overal shortest decomposition into sequences and nonsequences in the case that a better match is overlapped by a sequence starting closer to the left - this comes from the specification and the nature of the Perl regular expression engine, which favours the leftmost match over the longest match. My try at this problem is at 124 chars (discounting whitespace and the command line invocation(11 chars)):
Back to
Meditations
|
|