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

[reply]
      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>

      [download]
      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.

[reply]
[d/l]

        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>

        [download]
        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;"

[reply]
[d/l]
        <table><tr><td bgcolor=#000000><font color=#000000> 
put text here and then 
</font><td></tr></table>

        [download]
        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

[reply]
[d/l]
        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!

[reply]

        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.

        <Reveal this spoiler or all in this thread>

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

[reply]
      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+)$/

      [download]
      "Ewww," Tom said sheepishly.

      $_="goto+F.print+chop;\n=yhpaj";F1:eval
[reply]
[d/l]
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

    [download]
    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";
  }
}

    [download]
[reply]
[d/l]
[select]
      This is better! 
      /^[01]$|^([01])[01]*?\1$/

      [download]
      ciao
[reply]
[d/l]
        What a bunch of monks
[reply]
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/

    [download]

    -- Randal L. Schwartz, Perl hacker

[reply]
[d/l]

Back to Meditations