Regex puzzle

Front page | perl.fwp | Postings from January 2002

Thread Next

From:

Robin Houston

Date:

January 19, 2002 06:52

Subject:

Regex puzzle

Message ID:

20020119145215.B5932@puffinry.freeserve.co.uk

Consider this subroutine:

sub shrinkable ($) {
    my $str = shift;
    for my $i (1..length($str)) {
        return 1 if substr($str, $i) . substr($str, 0, $i) lt $str;
    }
    return 0;
}

So "foo" is not shrinkable, "bar" is shrinkable and so on.
Intuitively, a string is shrinkable iff it can be split into
two pieces $A.$B so that ("$B$A" lt "$A$B"). "bar" is shrinkable
because you can split it into b,ar and ("arb" lt "bar").

Can you write a regex which matches only shrinkable strings?
No, you're not allowed to use embedded code constructs ;-)

You may find it easier to write a bit of code which constructs
such a regex -- that's fine.

(I'll post my solution in a few days in the unlikely event that none
of you has bettered it by then. It's a fun problem.)

 .robin.

Thread Next