Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

tic-tac-toe regex golf

by barrachois (Pilgrim)
on Nov 18, 2003 at 06:03 UTC ( #307918=perlquestion: print w/ replies, xml ) Need Help??
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
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.

Comment on tic-tac-toe regex golf
Select or Download Code
Re: tic-tac-toe regex golf
by davido (Archbishop) 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

    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.


    Dave


    "If I had my life to live over again, I'd be a plumber." -- Albert Einstein
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
    And the output is -
    X wins O wins X wins No body wins
Re: tic-tac-toe regex golf (bug)
by tye (Cardinal) 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/ # ^^^^^^ ^^
    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
      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
        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 :)
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)
    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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://307918]
Approved by Roger
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (6)
As of 2014-07-30 05:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (229 votes), past polls