Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Fun Regex Exercise

by japhy (Canon)
on Oct 25, 2000 at 16:08 UTC ( [id://38339]=perlmeditation: print w/replies, xml ) Need Help??

I must truly be obsessed with regexes, but nevermind.

If anyone's interested in a fun regex challenge, here are the specs:
Construct a SINGLE regular expression that uses only anchoring (^ and $), reptition modifiers (* and +), alternation (|), and grouping ( ( and )) that will determine whether a string consists of only 0's and 1's AND that there are the SAME number of occurrences of the substring '01' as there are '10'.

Examples:
  • '101' succeeds, because it has ONE '10' and ONE '01'.
  • '1001' succeeds, because it has ONE '10' and ONE '01'.
  • '1010' fails, because it has TWO '10's and only ONE '01'.
  • '10101' succeeds, because it has TWO '10's and TWO '01's.
This is a fun exercise, really. Before you start tackling it in the regex sense, though, try to explain how a match works in English (or whatever language you speak).

$_="goto+F.print+chop;\n=yhpaj";F1:eval

Replies are listed 'Best First'.
RE: Fun Regex Exercise
by dchetlin (Friar) on Oct 25, 2000 at 16:31 UTC
    /me tries to figure out how to do a spoiler in web-space...

    Spoiler follows!...


     
     
     

    /^(1[01]*1|0[01]*0)$/

    or, if I can use backreferences (wasn't clear if grouping meant _only_ grouping):

    /^([01])[01]*\1$/

    -dlc

      Actually HTML has a wonderful way to do spoilers, an example is below. Highlight it if you actually need an explanation of the trick.

      Spoiler

      The trick is that you write a table with the font and the background color the same. When someone highlight's it they can read the spoiler, but otherwise they cannot.

      In this case I did it like this:

      <table><tr><td bgcolor=#000000><font color=#000000> put text here and then </font><td></tr></table>
      Unfortunately links show through because the rules for the HTML here don't include (that I saw at least) a way to control the color of an HREF. Which is why the link is down there and not in here. :-)

      Wish I could claim it was my idea, but one of the folks at IWETHEY (namely CRConrad) came up with it.

        I am the ultimate spoiler

        The trick for including links of different color, aside from changing body attributes is to do the following:
        <a href="/index.pl?node_id=10277"> <font color="#000000"> slick </FONT> </a>
        I'm a slick one ain't i?

         
        ___crazyinsomniac_______________________________________
        Disclaimer: Don't blame. It came from inside the void
        perl -e "$q=$_;map({chr unpack qq;H*;,$_}split(q;;,q*H*));print;$q/$q;"

        <table><tr><td bgcolor=#000000><font color=#000000> put text here and then </font><td></tr></table>
        If you're gonna do that, at least make it legal HTML by putting the needed quotes around the attributes!

        -- Randal L. Schwartz, Perl hacker

        You can solve the problem with the colour of the hyperlinks by using Cascading Style Sheets.

        I've changed the colours on my homepage and also removed the underline from the links.

        Update: Putting underlines for links is sooo ugly! :)

        Cheers!

        Just so folks know should they stumble on this node there is now support for <spoiler> tags in PM. They can be configured to render just like this too. :-) IOW, please DONT follow the advice here from tilly, just use the correct tags.

        ---
        $world=~s/war/peace/g

      Bravo (or brava, depending...). My solution was different, but could (and should) have been optimized into yours. Mine uses the notion that any matching string looks like a series of strings like "11..1100..00" concatenated, with a string of 1's at the end. (Or vice-versa, with 0's...) But yours is far simpler -- in fact, it states the very fact: if there's a 1 (or 0) at both ends, the string will succeed. Oh, and no backreferences, but that's ok.

      Here's mine. It seems like even more of a behemoth now...
      /^((1+0+)*1+|(0+1+)*0+)$/
      "Ewww," Tom said sheepishly.

      $_="goto+F.print+chop;\n=yhpaj";F1:eval
RE: Fun Regex Exercise
by quidity (Pilgrim) on Oct 25, 2000 at 18:04 UTC

    Nice Challenge

    Basically you need to check for any string which begins and ends with the same character, any sequence of 0s or 1s inside this will match the '10|01' criteria. You also need to account for '1', '0', '11' and '00' as these also meet the '01|10' constraint.

    / ^(0|1)$ # simple cases of 1 or 0, with zero 01|10 | ^1(0|1)*1$ # 1 .. anything .. 1 | ^0(0|1)*0$ # 0 .. anything .. 0 /x
    my @tests = qw( 0 1 01 10 00 11 000 111 001 011 101 010 100 110 1001 1101 0101 1010 ); foreach (@tests) { print "$_ "; if (/^(0|1)$|^1(0|1)*1$|^0(0|1)*0$/) { print "passed\n"; } else { print "failed\n"; } }
      This is better!
      /^[01]$|^([01])[01]*?\1$/
      ciao
        What a bunch of monks
RE: Fun Regex Exercise
by merlyn (Sage) on Oct 25, 2000 at 17:37 UTC
    spoiler
    Well, in english, it'd have to be a string that if non-empty, began with a 0 or 1, and then either stops there or has zero or 0's or 1's followed by what the string started with. That seems to fit the description.

    So as a regex would be:

    /^(([01])([01]*\2)?\z/

    -- Randal L. Schwartz, Perl hacker

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://38339]
Approved by root
Front-paged by cazz
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others rifling through the Monastery: (3)
As of 2024-11-12 06:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    chatterbot is...






    Results (39 votes). Check out past polls.