tic-tac-toe regex golf

barrachois has asked for the wisdom of the Perl Monks concerning the following question:

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.

Comment on tic-tac-toe regex golf Select or Download Code

Replies are listed 'Best First'.
Re: tic-tac-toe regex golf by davido (Cardinal) on Nov 18, 2003 at 06:10 UTC
Original post: 49 keystrokes: `^(...)(X\|O)\2\2\|(X\|O)(.{2,3}\3)\4\|^..(X\|O).\5.\5`* [download] 47 keystrokes: `^(...)(X\|O)\2\2\|(X\|O)(...?\3)\4\|^..(X\|O).\5.\5` [download] 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` [download] 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. Dave "If I had my life to live over again, I'd be a plumber." -- Albert Einstein	[reply] [d/l] [select]
Re: tic-tac-toe regex golf by Roger (Parson) on Nov 18, 2003 at 06:40 UTC
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 [download] And the output is - `X wins O wins X wins No body wins` [download]	[reply] [d/l] [select]
Re: tic-tac-toe regex golf (bug) by tye (Sage) on Nov 18, 2003 at 16:47 UTC
Your original fails in one case: `/^(...)*(X\|O)\2\2\|(X\|O)(.{2,3}\3)\4\|^..(X\|O).\5.\5/ # ^^^^^^ ^^` [download] 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. - tye	[reply] [d/l] [select]
Re: Re: tic-tac-toe regex golf (bug) by barrachois (Pilgrim) on Nov 18, 2003 at 17:11 UTC
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` [download]	[reply] [d/l]
Re: Re: Re: tic-tac-toe regex golf (bug) by Anonymous Monk on Nov 20, 2003 at 00:41 UTC
Sometimes it helps to anchor from the other side: `(\w)(..(\1\|.\1.)..\1\|.\1.\1..$\|\1\1(...)*$)` [download] This 43 also gets rid of all those ugly different digits, in favor of pleasing uniformity :)	[reply] [d/l]
Re: tic-tac-toe regex golf by Roy Johnson (Monsignor) on Nov 18, 2003 at 18:42 UTC
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)` [download] 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` [download]	[reply] [d/l] [select]
Re: tic-tac-toe regex golf by Anonymous Monk on Dec 16, 2016 at 00:04 UTC
The 2nd addendum answer doesn't work with all of the diagonals, "--X-X-X--" being an example.	[reply]