Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Checking Tic-Tac-Toe Win conditions?

by BUU (Prior)
on Sep 25, 2004 at 10:06 UTC ( [id://393769] : perlquestion . print w/replies, xml ) Need Help??

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

I was hanging out on irc (freenode, #perl) this morning chatting about this and that, mostly about crappy programming languages and so forth. Someone entering the conversation mentioned that once he sat on a class of VB students who had to write a tic-tac-toe "gui" in VB, no AI, just checking for win conditions. He recounted that all of the students solved the problem by writing 16 or 20 or however many lines of code that looked like:
if( $board[0][0] eq 'x' and $board[0][1] eq 'x' and $board[0][2] eq 'x +' ) { #win! }
Or whatever the VB equivalent happened to be. Naturally, as a Perl programmer who strives to be as concise as possible (while still being clear and understandable of course), I was horrified by all the repeated code. But then when I stopped to think how I would do it, I had problems coming up with a way that was substantially better. So I pose the question to you: Given a datastructure, how do you check for a tic-tac-toe win condition?

Feel free to assume any data structure, I have arbitrarily decided the default datastructure will be a 2d array containing 'x's, 'o's and 'undefs', whose meaning should be obvious. Using a different one is perfectly acceptable, just make sure you describe said datastructure.

(And yes, I promise I'm not going to steal *anybody's* hard work and fraudently use it to gain a job. Not that I'm bitter. This "challenge" has nothing to do with anything in the real world and is merely the result of a late night conversation on IRC.)

Replies are listed 'Best First'.
Re: Checking Tic-Tac-Toe Win conditions?
by ambrus (Abbot) on Sep 25, 2004 at 10:51 UTC
Re: Checking Tic-Tac-Toe Win conditions?
by Chady (Priest) on Sep 25, 2004 at 11:06 UTC

    Okay, here's my take.

    • my board is some kind of a 2D array.
    • 'x' are 1.
    • 'o' are -1.
    • empty is 0.

    we look for an absolute 3. But I'm sure there is a more mathematical way for this:

    my @board; while (<DATA>) { chomp; push @board, [split / /]; } for my $i (0 .. 2) { my ($t1, $t2, $t3, $t4) = (0,0,0,0); for my $j ( 0 .. 2 ) { $t1 += $board[$i][$j]; $t2 += $board[$j][$i]; $t3 += $board[$j][$j]; $t4 += $board[2 - $j][$j]; } if (abs($t1) == 3 || abs($t2) == 3 || abs($t3) == 3 || abs($t4) == 3) { print "Win.\n"; last; } } __DATA__ 1 0 1 -1 1 -1 1 0 1

    He who asks will be a fool for five minutes, but he who doesn't ask will remain a fool for life.
    Chady | http://chady.net/
    Are you a Linux user in Lebanon? join the Lebanese Linux User Group.
Re: Checking Tic-Tac-Toe Win conditions?
by davido (Cardinal) on Sep 25, 2004 at 16:57 UTC

    If you take each 3x3 game grid and flatten it to a string of nine characters, this can be solved with a regexp. This particular method of solving it wasn't really touched upon in (Golf) Tic Tac Toe, but works great. The conversion of a 3x3 grid to a single flat string is trivial, so I'll just demonstrate the regexp portion of the solution.

    The regexp can be expressed in a way that tests for one of four conditions. I started out with a slightly more complex regexp, and then was able to see the forest through the trees, and found a way to boil it down to this common denominator.

    In the following snippet, I never placed any 'o's because I wanted to keep it visually clear what was going on. The hyphens could be replaced with x's and o's as though a real game were being played, and the regexp will discover whether X or O wins. I just wanted to show each of the winning possibilities, so I used hyphens to isolate X.

    Here's the code:

    use strict; use warnings; # Assume that the 3x3 AoA has been flattened to a single string. # Each string, therefore, equates to a single game. my @games = ( "x---x---x", # Diag from top left. 1 "--x-x-x--", # Diag from top right. 3 "x--x--x--", # Vert from top left. 2 "xxx------", # Horiz from top left. 4 "---xxx---", # Horiz from mid left. 4 "------xxx", # Horiz from bottom left. 4 "-x--x--x-", # Vert from top mid. 2 "--x--x--x" ); my $i; foreach my $game ( @games ) { print "Game ", ++$i, "\t"; if ( $game =~ m/ ([xo]) (?: (?:...\1){2} | (?:..\1){2} | (?:.\1){2} | \1{2}(?=(?:...){0,2}$) ) /ix ){ print "$1 wins.\n"; } else { print "no winner\n"; } }

    Update:
    Here's a golfier version that uses the same solution technique:

    print m/([xo])((...\1){2}|(..\1){2}|(.\1){2}|\1{2}(?=(...){0,2}$))/i? "$1 wins.\n":"No winner.\n" foreach qw/x---x---x --x-x-x-- x--x--x-- xxx------ ---xxx--- ------xxx -x--x--x- --x--x--x x---x-x--/;

    Update2: Fixed a problem that would allow misaligned 3-in-a-rows to win when they shouldn't.


    Dave

Re: Checking Tic-Tac-Toe Win conditions?
by TedPride (Priest) on Sep 26, 2004 at 05:16 UTC
    Board state is stored in $b in numeric values of 0 (nothing), 1 (one person) and 2 (other person). $m keeps track of whose move it currently is, and is multiplied by -1 each turn. The board check is as follows:
    for ($i = 0; $i < 3; $i++) { if ($b[$i][0] == $m && $b[$i][1] == $m && $b[$i][2] == $m) { &win( +$m); } if ($b[0][$i] == $m && $b[1][$i] == $m && $b[2][$i] == $m) { &win( +$m); } } if ($b[0][0] == $m && $b[1][1] == $m && $b[2][2] == $m) { &win($m); } if ($b[0][0] == $m && $b[1][1] == $m && $b[2][2] == $m) { &win($m); }
    It requires one loop and four check lines.
Re: Checking Tic-Tac-Toe Win conditions?
by TedPride (Priest) on Sep 26, 2004 at 05:48 UTC
    Or...
    @m = (0,1,2, 3,4,5, 6,7,8, 0,3,6, 1,4,7, 2,5,8, 0,4,8, 2,4,6); for ($i = 0; $i < 22; $i += 3) { &win($t) if @g[@m[$i]] == $t && @g[@m[$i+1]] == $t && @g[@m[$i+2 +]] == $t; }
    Where @m = win matches, $t = turn, @g = board setup.
Re: Checking Tic-Tac-Toe Win conditions?
by dragonchild (Archbishop) on Sep 26, 2004 at 16:53 UTC
    One alternative, similar to the regex, is to use bit-wise AND. So, you'd create a bitmap of your board using vec() and compare it to known win conditions (which can be pre-generated). This is a very C-ish way of doing it.

    ------
    We are the carpenters and bricklayers of the Information Age.

    Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

    I shouldn't have to say this, but any code, unless otherwise stated, is untested