I have a question from a friend on finding the shortest regular expression that will identify a winning position in Tic Tac Toe. So for those of you who like perl golf (fewest keystrokes wins), I'd appreciate hearing if you see ways to do this in a shorter regex than I've found, which is 49 characters:

    ^(...)*(X|O)\2\2|(X|O)(.{2,3}\3)\4|^..(X|O).\5.\5

[download]
Our Tic Tac Toe board is a string of nine characters, "X", "O", or "-" for an empty space. Winning positions are a horizontal, vertical, or diagonal lines of three X's or O's. Code that tests a regex on the complete list of winning patterns and a few non-winning patterns is given below.

The winning patterns all have three X's (or O's) followed by zero, one, two, or three dots. Somehow that makes me think that there may be a shorter regex than the one I've found.

- barrachois 

#!/usr/bin/perl -w
# Test regular expression on Tic Tac Toe boards.
my @X_wins = ( 
              'XXX......' ,
              '...XXX...' ,
              '......XXX' ,
              'X..X..X..' ,
              '.X..X..X.' ,
              '..X..X..X' ,
              'X...X...X' ,
              '..X.X.X..' ,
             );
my @O_wins = @X_wins;
s/X/O/g for @O_wins;
my @noone_wins = (
             'XO-------' ,
             'XX-XOO---' ,
             '-XX-XX-O-' ,
             'OXO--XXO-' ,
             'OOXXXO---' ,
             'OXXX-XOO-' ,
             'OOXXX----' ,
             'XOOOXOOO-' ,
             'OXOXOX---' ,
                 );

foreach my $board (@X_wins, @O_wins, @noone_wins){
  print "$board " . ( is_win($board) ? "is" : "is not") . " a win.\n";
}       
sub is_win {
  return shift =~ m/^(...)*(X|O)\2\2|(X|O)(.{2,3}\3)\4|^..(X|O).\5.\5/
+;
}

[download]
1st Addendum and Correction :
My 49 character regex is incorrect; it fails to see that 'XO--X-O-X' is a win. The part of my original regex which was supposed to see this as a winning string is /(X|O)(.{2,3}\1)\2/ which is supposed to be match three X's with two or three arbitrary chars between them. However, using the match \2 requires that the intervening charcters be the same. Oops. So I guess I need to list those two cases explicitly.

Given Dave's suggestion of \w for X|O, the best I see so far is 57 characters.

 ^(...)*(\w)\2\2|^..(\w).\3.\3|(\w)..\4..\4|(\w)...\5...\5

[download]
2nd Addendum
The shortest as of Nov 19, contributed anonymously, is this 43 character solution. Very nice. 
  (\w)(..(\1|.\1.)..\1|.\1.\1..$|\1\1(...)*$)

[download]
Thanks to all for the suggestions.

In reply to tic-tac-toe regex golf by barrachois

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.