tic-tac-toe regex golf

[barrachois]

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

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/
+;
}

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

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(...)*$)

Thanks to all for the suggestions.

[davido]

Original post: 49 keystrokes:

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

47 keystrokes:

^(...)*(X|O)\2\2|(X|O)(...?\3)\4|^..(X|O).\5.\5

If you can safely assume that "X" and "O" are the only "word" characters (alpha characters) found in the solution, you could save a few keystrokes like this (44 keystrokes):

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

Note: In my solutions I made no attempt to verify the suitability of your original regex. I simply modified your regex in ways that preserved identical functionality in fewer keystrokes.

[Roger]

A different approach - here's my generic solution to find out who is the winner of the tic-tac-toe. The basic idea is to list out the winning patterns, and then automatically generate regular expressions based on these patterns. This solution assumes that there is only one winner in the game.



#!/usr/local/bin/perl -w
use strict;
use re 'eval';

# A list of all winning patterns, could generate them
# with some sort of algorithm, but it's easier just
# to type them out.  ;-)

my @win = qw/
                XXX......
                X..X..X..
                ......XXX
                ..X..X..X
                ...XXX...
                .X..X..X.
                X...X...X
                ..X.X.X..
            /;

foreach (@win)  # dynamically generate regular expressions
{               # to look for matching winning patterns
    my $c = 0;
    s/X/!$c++?'([^-])':'(??{$1})'/ge;
}

while (my $game = <DATA>)
{
    my $winner = 'No body';
    foreach (@win) {
        $winner = $1, last if $game =~ /$_/;
    }
    print "$winner wins\n";
}

__DATA__
XO-OX--OX
OX-XO--XO
OOXOXOXOO
OX-XOOXOX

And the output is -

X wins
O wins
X wins
No body wins

[tye]

Your original fails in one case:

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

The parts above ^s are the problem. They require that, in a '.X..X..X.' type of solution that the two '..' parts be the same. So it won't match '-XO-X-OX-' even though it should.

[barrachois]

Yes, thank you.

That was just pointed out to me by someone else as well, and I've put an addendum and correction into the original post accordingly.

Following Dave's suggestion to use \w instead of X|O, the shortest I'm currently aware of is this 57 char regex which lists out the two .{2,3} cases explicitly.

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

[Anonymous Monk]

Sometimes it helps to anchor from the other side:

(\w)(..(\1|.\1.)..\1|.\1.\1..$|\1\1(...)*$)

This 43 also gets rid of all those ugly different digits, in favor of pleasing uniformity :)

[Roy Johnson]

The final alternation can be rewritten to save 2 keystrokes:

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

Then factor out the common leading dots and the trailing ..\4s to save another 6:

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

[Anonymous Monk]

The 2nd addendum answer doesn't work with all of the diagonals, "--X-X-X--" being an example.