Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

(golf) Collapse repetitions within a string

by Corion (Pope)
on Jun 25, 2003 at 11:55 UTC ( #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:

foofoofoo -> Sequence is foo 123456 -> no Sequence ooofoofoofoof -> First sequence is o

The output of a sequence must consist of the shortest sequence plus the repeat count. Example:

foofoofoofoo -> foo repeated 4 time(s) # correct foofoofoofoo -> foofoo repeated 2 time(s) # wrong

If there is stuff that fits in no sequence, it is to be output as well. Example:

123456 -> 123456

The parts of the string are then to be output as they appear within the string. Example for input foofooofooo :

foo repeated 2 time(s) o f o repeated 3 time(s)

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)):

perl -nle 'printf(defined $3 ? "%s\n" : "%s repeated %s time(s)\n", $1.$3, length($2)/length($1.$3)+1) while/(?:(\w+?)(\1+))|(?:(\w+?)(?!\3))/g'
__END__ perl -MHTTP::Daemon -MHTTP::Response -MLWP::Simple -e ' ; # The $d = new HTTP::Daemon and fork and getprint $d->url and exit;#spider ($c = $d->accept())->get_request(); $c->send_response( new #in the HTTP::Response(200,$_,$_,qq(Just another Perl hacker\n))); ' # web

Comment on (golf) Collapse repetitions within a string
Select or Download Code
Re: (golf) Collapse repetitions within a string
by kilinrax (Deacon) on Jun 25, 2003 at 13:57 UTC
    This comes in at 107 chars (not counting command line invocation):
    perl -Mstrict -wlne 'while(s/(\w+?)\1+//){print$`if$`;my@L=split"(?=$1 +)",$&;printf"%s repeated %i time%s\n",$1,$#L+1,$#L?"s":""}'
    Or, more readably:
    while(s/(\w+?)(\1+)//) { print $` if $`; my @L = split "(?=$1)", $&; printf "%s repeated %i time%s\n", $1, $#L+1, $#L ? 's' : '' }
    Note that this version is slightly more accurate to the spec you've given; by your own definitions 'foofooofooo' should give:
    foo repeated 2 time(s)
    o repeated 3 time(s)
    i.e. not separate stuff that fits no sequence into individual characters (like '123456').

    Update: as Corion points out, without the ternary op to add the optional 's', or the 'my', you can take this down to a mere 93 characters:
    perl -wlne 'while(s/(\w+?)\1+//){print$`if$`;@L=split"(?=$1)",$&;print +f"%s repeated %i times\n",$1,$#L+1}'
Re: (golf) Collapse repetitions within a string
by belg4mit (Prior) on Jun 25, 2003 at 15:54 UTC
    FYI this is just RLE, with very odd requirements for the output.

    UPDATE: Yes, Run Length Encoded.

    I'm not belgian but I play one on TV.

      Run Length Encoded?
Re: (golf) Collapse repetitions within a string
by Jasper (Chaplain) on Jun 26, 2003 at 12:08 UTC
    just golfing yours:
    perl -nle'print$1?("$1 repeated ",length($&)/length$1," times"):$&whil +e/(\w+?)\1+|./g'
    You don't need the brackets around the time(s), because any time it's less than two, you only print out one character. You were matching \w, so I didn't check for defined on $1, just $1, but it should give the same results.

    I think that's 75, not including switches.


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://268820]
Approved by broquaint
Front-paged by Courage
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (15)
As of 2014-07-30 14:26 GMT
Find Nodes?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:

    Results (234 votes), past polls