Code Golf: Tic Tac Toe

Question

Post your shortest code, by character count, to check if a player has won, and if so, which.

Assume you have an integer array in a variable b (board), which holds the Tic Tac Toe board, and the moves of the players where:

• 0 = nothing set
• 1 = player 1 (X)
• 2 = player 2 (O)

So, given the array b = [ 1, 2, 1, 0, 1, 2, 1, 0, 2 ] would represent the board

X|O|X
-+-+-
 |X|O
-+-+-
X| |O

For that situation, your code should output 1 to indicate player 1 has won. If no-one has won you can output 0 or false.

My own (Ruby) solution will be up soon.

Edit: Sorry, forgot to mark it as community wiki. You can assume the input is well formed and does not have to be error checked.

---

Update: Please post your solution in the form of a function. Most people have done this already, but some haven't, which isn't entirely fair. The board is supplied to your function as the parameter. The result should be returned by the function. The function can have a name of your choosing.

Jadwiga

@Idan, in this case X already won. The game progressed like this: X center, O middle right, X top left, O bottom right, X top right, O middle top, X lower left. – Jadwiga

lol my bad, I completely missed the diagonal :) – Idel

@Aistina: Please see this: meta.stackexchange.com/questions/24242/… – Norven

@Jon, I'm reading the accepted answer there and I do not see a problem (except possibly point 8: "A good code golf should solve a class of problems rather than a single instance"). – Jadwiga

It would be easier with a different representation. -1 for X, 0 for blank, 1 for O – Wyant

Probably should specify that the solution is a function, and provide more test cases. Otherwise a decent code-golf. – Gamma

This is funny. About a week ago I started a little code golf round on another forum, and it was about tic-tac-toe win detection. I put the code up with a test suite at github.com/matchu/gofflesby-tictactoe – Sholokhov

Should that function return or print the results? And should it have a specific name? – Withhold

Maybe this could be done in APL, Conway's Game of Life can be done in 38 characters using APL: en.wikipedia.org/wiki/File:LifeInApl.gif – Reviel

What about impossible inputs like: [1, 1, 1, 0, 0, 0, 2, 2, 2] (impossible because the game necessarilly ended before reaching that position) ? – Hydrometer

@kriss, as stated in the question; "You can assume the input is well formed and does not have to be error checked." So you don't need to worry about such input. – Jadwiga

A much better encoding of the board would be -1 for X, 0 for space, 1 for O. This lets you detect a win by doing 8 sums... any -3 or 3 shows a win, and for who. – Wyant

Answer 1

C, 77 (83) characters

This is a variant of dmckee's solution, except that each pair of digits in the Compact Coding is now the base-9 digits of the ASCII characters.

The 77-char version, does not work on MSVC:

// "J)9\t8\r=,\0" == 82,45,63,10,62,14,67,48,00 in base 9.
char*k="J)9 8\r=,",c;f(int*b){return(c=*k++)?b[c/9]&b[c%9]&b[*k--%9]|f(b):0;}

This 83-char version, should work on every C compiler:

f(int*b){char*k="J)9    8\r=,",s=0,c;while(c=*k++)s|=b[c%9]&b[c/9]&b[*k%9];return s;}

(Note that the spaces between the 9 and 8 should be a tab. StackOverflow converts all tabs into spaces.)

---

Test case:

#include <stdio.h>  
void check(int* b) {
    int h0 = b[0]&b[1]&b[2];
    int h1 = b[3]&b[4]&b[5];
    int h2 = b[6]&b[7]&b[8];
    int h3 = b[0]&b[3]&b[6];
    int h4 = b[1]&b[4]&b[7];
    int h5 = b[2]&b[5]&b[8];
    int h6 = b[0]&b[4]&b[8];
    int h7 = b[2]&b[4]&b[6];
    int res = h0|h1|h2|h3|h4|h5|h6|h7;
    int value = f(b);
    if (value != res)
        printf("Assuming f({%d,%d,%d, %d,%d,%d, %d,%d,%d}) == %d; got %d instead.\n", 
            b[0],b[1],b[2], b[3],b[4],b[5], b[6],b[7],b[8], res, value);
}
#define MAKEFOR(i) for(b[(i)]=0;b[(i)]<=2;++b[(i)])

int main() {
    int b[9];

    MAKEFOR(0)
    MAKEFOR(1)
    MAKEFOR(2)
    MAKEFOR(3)
    MAKEFOR(4)
    MAKEFOR(5)
    MAKEFOR(6)
    MAKEFOR(7)
    MAKEFOR(8)
        check(b);

    return 0;
}

Monodic

Whoa! The b-=48 bit is sneaky. And the s|=... is good too. My hat's off to you, sir! – Gamma

How do you guarantee that the final *++k is evaluated after the preceding *k's? Is there a sequence point I'm not seeing? – Dogtooth

@Potatoswatter: I wonder the same when the gcc-generated binary doesn't give me errors on this. Looks like just an implementation detail. – Monodic

Why not use a \t instead of a literal tab character? – Submaxillary

Answer 2

Crazy Python solution - 79 characters

max([b[x] for x in range(9) for y in range(x) for z in range(y)
    if x+y+z==12 and b[x]==b[y]==b[z]] + [0])

However, this assumes a different order for the board positions in b:

 5 | 0 | 7
---+---+---
 6 | 4 | 2
---+---+---
 1 | 8 | 3

That is, b[5] represents the top-left corner, and so on.

To minimize the above:

r=range
max([b[x]for x in r(9)for y in r(x)for z in r(y)if x+y+z==12and b[x]==b[y]==b[z]]+[0])

93 characters and a newline.

Update: Down to 79 characters and a newline using the bitwise AND trick:

r=range
max([b[x]&b[y]&b[z]for x in r(9)for y in r(x)for z in r(y)if x+y+z==12])

Wobble

The numbers are placed in order to have all working (interesting) sums equals to 12. so he does a loop and when the sum is equals to 12, compare the content of the three cases – Conti

Wow, now I see. That's quite clever. – Jadwiga

Blame Donald A. Norman's "Things That Make Us Smart" for that trick: amazon.com/Things-That-Make-Smart-Attributes/dp/0201626950 – Wobble

I learned this trick from one of Martin Gardner's columns back in the 70s, but I think it dates back to Henry Dudeney in the 1800s, or maybe further. – Crazed

very clever... but doesn't match the requirements ;) – Honewort

clever approach but does not solve the problem. you'll need to add translation for that and it becomes 105 chars: x=5,0,7,6,4,2,1,8,3;r=range;max(b[x[i]]&b[x[j]]&b[x[12-i-j]]for i in r(9)for j in r((14-i)/2,i)if i+j<13) – Taxation

Answer 3

Python 80 (69) char

Not the shortest Python solution, but I like how it introduces "DICE" into a game of tic-tac-toe:

W=lambda b:max([b[c/5-9]&b[c/5+c%5-9]&b[c/5-c%5-9]for c in map(ord,"DICE>3BQ")])

69 chars for the simpler expression:

max([b[c/5-9]&b[c/5+c%5-9]&b[c/5-c%5-9]for c in map(ord,"DICE>3BQ")])

Ody

Your '>' should be a '?' off by 1 error, as is it will fail to detect a win of (0,3,6) instead it gets (3,5,1). Nonetheless very nice. – Rolland

Answer 4

J, 50 chars

w=:3 : '{.>:I.+./"1*./"1]1 2=/y{~2 4 6,0 4 8,i,|:i=.i.3 3'

Confide

Answer 5

Perl, 87 85 characters

A function that returns 0, 1 or 2, using a regular expression, of course (the newline's only there to avoid the scrollbar):

sub V{$"='';$x='(1|2)';"@_"=~
/^(...)*$x\2\2|^..$x.\3.\3|$x..\4..\4|$x...\5...\5/?$^N:0}

It can be called as V(@b), for example.

Withhold

:), @mobrule Not as short as your similar approach without the regex, though. :( – Withhold

My skull has cracked open and beams of light are shining through the cracks after reading this. – Volcanology

@mercator: looks like it could be shortened the parts or regex with \4 and \5 as very similar (just differ by number of dots). – Hydrometer

@kriss: I did try that, but all my attempts at generating it in a loop in some way ended up being much longer... Feel free to try it yourself. ;) – Withhold

Answer 6

I'm not happy with repeating myself (horizontal/vertical, and the diagonals), but I think it's a fair start.

C# w/LINQ:

public static int GetVictor(int[] b)
{
    var r = Enumerable.Range(0, 3);
    return r.Select(i => r.Aggregate(3, (s, j) => s & b[i * 3 + j])).Concat(
        r.Select(i => r.Aggregate(3, (s, j) => s & b[j * 3 + i]))).Aggregate(
        r.Aggregate(3, (s, i) => s & b[i * 3 + i]) | r.Aggregate(3, (s, i) => s & b[i * 3 + (2 - i)]),
        (s, i) => s | i);
}

Strategy: Bitwise AND each element of a row/column/diagonal with the other elements (with 3 as a seed) to obtain a victor for that subset, and OR them all together at the end.

Scheffler

Answer 7

Ruby, 115 chars

Oops: Somehow I miscounted by a lot. This is actually 115 characters, not 79.

def t(b)[1,2].find{|p|[448,56,7,292,146,73,273,84].any?{|k|(k^b.inject(0){|m,i|m*2+((i==p)?1:0)})&k==0}}||false end

# Usage:
b = [ 1, 2, 1,
      0, 1, 2,
      1, 0, 2 ]
t(b) # => 1

b = [ 1, 1, 0,
      2, 2, 2,
      0, 2, 1 ]
t(b) # => 2

b = [ 0, 0, 1,
      2, 2, 0,
      0, 1, 1 ]
t(b) # => false

And the expanded code, for educational purposes:

def tic(board)
  # all the winning board positions for a player as bitmasks
  wins = [ 0b111_000_000,  # 448
           0b000_111_000,  #  56
           0b000_000_111,  #   7
           0b100_100_100,  # 292
           0b010_010_010,  # 146
           0b001_001_001,  #  73
           0b100_010_001,  # 273
           0b001_010_100 ] #  84

  [1, 2].find do |player| # find the player who's won
    # for the winning player, one of the win positions will be true for :
    wins.any? do |win|
      # make a bitmask from the current player's moves
      moves = board.inject(0) { |acc, square|
        # shift it to the left and add one if this square matches the player number
        (acc * 2) + ((square == player) ? 1 : 0)
      }
      # some logic evaluates to 0 if the moves match the win mask
      (win ^ moves) & win == 0
    end
  end || false # return false if the find returns nil (no winner)
end

I'm sure this could be shortened, especially the big array and possibly the code for getting a bitmask of the players's moves--that ternary bugs me--but I think this is pretty good for now.

Lull

Answer 8

Octave/Matlab, 97 characters, including spaces and newlines. Outputs 0 if no winner, 1 if player 1 won, 2 if player 2 won, and 2.0801 if both players "won":

function r=d(b)
a=reshape(b,3,3)
s=prod([diag(a) diag(fliplr(a)) a a'])
r=sum(s(s==1|s==8))^(1/3)

If we change the specification and pass in b as a 3x3 matrix from the start, we can remove the reshape line, getting it down to 80 characters.

Pruett

Answer 9

Perl, 76 char

sub W{$n=$u=0;map{$n++;$u|=$_[$_-$n]&$_[$_]&$_[$_+$n]for/./g}147,4,345,4;$u}

There are three ways to win horizontally:

0,1,2   ==>   1-1, 1, 1+1
3,4,5   ==>   4-1, 4, 4+1
6,7,8   ==>   7-1, 7, 7+1

One way to win diagonally from lower left to upper right:

2,4,6   ==>   4-2, 4, 4+2

Three ways to win vertically:

0,3,6   ==>   3-3, 3, 3+3
1,4,7   ==>   4-3, 4, 4+3
2,5,8   ==>   5-3, 5, 5+3

One way to win diagonally from upper left to lower right:

0,4,8   ==>   4-4, 4, 4+4

Read the middle columns to get the magic numbers.

Ody

Answer 10

because nobody wins at tictactoe when properly played i think this is the shortest code

echo 0; 

7 chars

Update: A better entry for bash would be this:

86 characters or 81 excluding function definition(win()).

win()for q in 1 28 55 3 12 21 4 20;{ [[ 3*w -eq B[f=q/8]+B[g=q%8]+B[g+g-f] ]]&&break;}

But, This is code from by tic-tac-toe program in bash so it does not quite meet specification.

# player is passed in caller's w variable. I use O=0 and X=2 and empty=8 or 9
# if a winner is found, last result is true (and loop halts) else false
# since biggest test position is 7 I'll use base 8. could use 9 as well but 10 adds 2 characters to code length
# test cases are integers made from first 2 positions of each row
# eg. first row (0 1 2) is 0*8+1 = 1
# eg. diagonal (2 4 6) is 2*8+4 = 20
# to convert test cases to board positions use X/8, X%8, and X%8+(X%8-X/8)
# for each test case, test that sum of each tuplet is 3*player value

Cabana

Good one... except that you can't assume the players will play properly ;) – Honewort

This doesn't answer the questions, because the question does not assume that the game has come to an end. – Gamma

@dmckee if the game hasn't come to an end, then nobody has won, so this solution will output the correct answer. – Autolithography

Answer 11

C, 99 chars

Not a winner, but maybe there's room for improvement. Never did this before. Original concept, first draft.

#define l w|=*b&b[s]&b[2*s];b+=3/s;s
f(int*b){int s=4,w=0;l=3;l;l;l=2;--b;l=1;b-=3;l;l;return l;}

Thanks to KennyTM for a few ideas and the test harness.

The "development version":

#define l w|=*b&b[s]&b[2*s];b+=3/s;s // check one possible win
f( int *b ) {
        int s=4,w=0; // s = stride, w = winner
        l=3;     // check stride 4 and set to 3
        l;l;l=2; // check stride 3, set to 2
        --b;l=1; // check stride 2, set to 1
        b-=3;l;l; return l; // check stride 1
}

Dogtooth

Answer 12

Ruby, 85 char

def X(b)
u=0
[2,6,7,8,9,13,21,-9].each do|c|u|=b[n=c/5+3]&b[n+c%5]&b[n-c%5]end
u
end

If the input has both players winning, e.g.

     X | O | X
    ---+---+---
     X | O | O
    ---+---+---
     X | O | X

then the output is 3.

Ody

Answer 13

(Iron)python, 75 characters

75 characters for a full function

T=lambda a:max(a[b/6]&a[b/6+b%6]&a[b/6+b%6*2]for b in[1,3,4,9,14,15,19,37])

66 characters if you leave out the function definition like some others have done

r=max(a[b/6]&a[b/6+b%6]&a[b/6+b%6*2]for b in[1,3,4,9,14,15,19,37])

The 8 different directions are represented by starting value + incrementor, compressed into a single number that can be extracted using division and modula. For example 2,5,8 = 2*6 + 3 = 15.

Checking that a row contains three equal values is done using the & operator. (which results in zero if they aren't equal). max is used to find the possible winner.

Schramke

Nice... we had similar ideas but you were much more clever. – Leto

If it's not a function, you may as well leave off the "r=" as well, since you can type the rest at the prompt to get a printed result. – Oxbow

Answer 14

Haskell, Assuming the magic squares above. 77 Characters

77 excludes imports and defining b.

import Data.Bits
import Data.Array

b = listArray (0,8) [2,1,0,1,1,1,2,2,0]
w b = maximum[b!x.&.b!y.&.b!z|x<-[0..8],y<-[x+1..8],z<-[12-x-y],z<8,z>=0,z/=y]

Or 82 assuming the normal ordering:

{-# LANGUAGE NoMonomorphismRestriction #-}
import Data.Bits
import Data.Array

b = listArray (0,8) [1,2,1,0,1,2,1,0,2]
w b = maximum[b!x.&.b!y.&.b!z|x<-[0..8],d<-[1..4],y<-[x+d],z<-[y+d],d/=2||x==2,z<9]

Prog

Answer 15

Python, 285 bytes

b,p,q,r=["."]*9,"1","2",range
while"."in b:
 w=[b[i*3:i*3+3]for i in r(3)]+[b[i::3]for i in r(3)]+[b[::4],b[2:8:2]]
 for i in w[:3]:print i
 if["o"]*3 in w or["x"]*3 in w:exit(q)
 while 1:
  m=map(lambda x:x%3-x+x%3+7,r(9)).index(input())
  if"."==b[m]:b[m]=".xo"[int(p)];p,q=q,p;break

...Oh, this wasn't what you meant when you said "Code Golf: Tic Tac Toe"? ;) (enter numpad numbers to place x's or o's, i.e. 7 is north-west)

Long Version

board = ["."]*9   # the board
currentname = "1" # the current player
othername = "2"   # the other player

numpad_dict = {7:0, 8:1, 9:2, # the lambda function really does this!
               4:3, 5:4, 6:5,
               1:6, 2:7, 3:8}

while "." in board:
    # Create an array of possible wins: horizontal, vertical, diagonal
    wins = [board[i*3:i*3+3] for i in range(3)] + \ # horizontal
           [board[i::3]      for i in range(3)] + \ # vertical
           [board[::4], board[2:8:2]]               # diagonal

    for i in wins[:3]: # wins contains the horizontals first,
        print i        # so we use it to print the current board

    if ["o"]*3 in wins or ["x"]*3 in wins: # somebody won!
        exit(othername)                    # print the name of the winner
                                           # (we changed player), and exit
    while True: # wait for the player to make a valid move
        position = numpad_dict[input()] 
        if board[position] == ".": # still empty -> change board
            if currentname == "1":
                board[position] = "x"
            else:
                board[position] = "o"
            currentname, othername = othername, currentname # swap values

Beggar

Haha, nice! I don't know Python so it's hard to follow what's going on, but still, impressive. – Jadwiga

Answer 16

Python - 75 chars (64)

I came up with 2 expressions, each 64chars:

max(a[c/8]&a[c/8+c%8]&a[c/8-c%8]for c in map(ord,'\t\33$#"!+9'))

and

max(a[c/5]&a[c/5+c%5]&a[c/5+c%5*2]for c in[1,3,4,8,12,13,16,31])

When you add "W=lambda b:" to make it a function, that makes 75chars. Shortest Python so far?

Taxation

Answer 17

J, 97 characters.

1+1 i.~,+./"2>>(0 4 8,2 4 6,(],|:)3 3$i.9)&(e.~)&.>&.>(]<@:#"1~[:#:[:i.2^#)&.>(I.@(1&=);I.@(2&=))

I was planning to post an explanation of how this works, but that was yesterday and now I can't read this code.

The idea is we create a list of all possible winning triples (048,246,012,345,678,036,147,258), then make the powerset of the squares each player has and then intersect the two lists. If there's a match, that's the winner.

Elison

Answer 18

JavaScript - function "w" below is 114 characters

<html>   
<body>
<script type="text/javascript">

var t = [0,0,2,0,2,0,2,0,0];

function w(b){
    i = '012345678036147258048642';
    for (l=0;l<=21;l+=3){
        v = b[i[l]];
        if (v == b[i[l+1]]) if (v == b[i[l+2]]) return v;   
    }
}

alert(w(t));

</script>
</body>
</html>

Scolopendrid

You don't need the +0, because x["1"] == x[1] in ECMAScript. – Monodic

With var t = [0,0,0,2,2,2,0,0,0]; as the board state, your function would return 0, whereas it should return 2. (as clearly player 2 is winning.) – Cholera

Answer 19

Visual Basic 275 254 (with loose typing) characters

 Function W(ByVal b())

    Dim r

    For p = 1 To 2

            If b(0) = b(1) = b(2) = p Then r = p
            If b(3) = b(4) = b(5) = p Then r = p
            If b(6) = b(7) = b(8) = p Then r = p
            If b(0) = b(3) = b(6) = p Then r = p
            If b(1) = b(4) = b(7) = p Then r = p
            If b(2) = b(5) = b(8) = p Then r = p
            If b(0) = b(4) = b(8) = p Then r = p
            If b(6) = b(4) = b(2) = p Then r = p

    Next

    Return r

End Function

Scolopendrid

I think you can make it shorter if you remove the ByVal instruction. – Demolish

(.NET) ide puts it back in again so i thought i should leave it there to be fair – Photoconduction

I don't think you can chain comparisons together like that, even in VB. – Acervate

Answer 20

Lua, 130 characters

The 130 characters is the function size only. The function returns nothing if no match is found, which in Lua is similar to returning false.

function f(t)z={7,1,4,1,1,3,2,3,3}for b=1,#z-1 do
i=z[b]x=t[i]n=z[b+1]if 0<x and x==t[i+n]and x==t[i+n+n]then
return x end end end

assert(f{1,2,1,0,1,2,1,0,2}==1)
assert(f{1,2,1,0,0,2,1,0,2}==nil)
assert(f{1,1,2,0,1,2,1,0,2}==2)
assert(f{2,1,2,1,2,1,2,1,2}==2)
assert(f{2,1,2,1,0,2,2,2,1}==nil)
assert(f{1,2,0,1,2,0,1,2,0}~=nil)
assert(f{0,2,0,0,2,0,0,2,0}==2)
assert(f{0,2,2,0,0,0,0,2,0}==nil)

assert(f{0,0,0,0,0,0,0,0,0}==nil)
assert(f{1,1,1,0,0,0,0,0,0}==1)
assert(f{0,0,0,1,1,1,0,0,0}==1)
assert(f{0,0,0,0,0,0,1,1,1}==1)
assert(f{1,0,0,1,0,0,1,0,0}==1)
assert(f{0,1,0,0,1,0,0,1,0}==1)
assert(f{0,0,1,0,0,1,0,0,1}==1)
assert(f{1,0,0,0,1,0,0,0,1}==1)
assert(f{0,0,1,0,1,0,1,0,0}==1)

Olsson

Answer 21

Python, 102 characters

Since you didn't really specify how to get input and output, this is the "raw" version that would perhaps have to be wrapped into a function. b is the input list; r is the output (0, 1 or 2).

r=0
for a,c in zip("03601202","11133342"):s=set(b[int(a):9:int(c)][:3]);q=s.pop();r=r if s or r else q

Tribunal

Answer 22

A solution in C (162 Characters):

This makes use of the fact that player one value (1) and player two value (2) have independent bits set. Therefore, you can bitwise AND the values of the three test boxes together-- if the value is nonzero, then all three values must be identical. In addition, the resulting value == the player that won.

Not the shortest solution so far, but the best I could do:

void fn(){
    int L[]={1,0,1,3,1,6,3,0,3,1,3,2,4,0,2,2,0};
    int s,t,p,j,i=0;
    while (s=L[i++]){
        p=L[i++],t=3;
        for(j=0;j<3;p+=s,j++)t&=b[p];
        if(t)putc(t+'0',stdout);}
}

A more readable version:

void fn2(void)
{
    // Lines[] defines the 8 lines that must be tested
    //  The first value is the "Skip Count" for forming the line
    //  The second value is the starting position for the line
    int Lines[] = { 1,0, 1,3, 1,6, 3,0, 3,1, 3,2, 4,0, 2,2, 0 };

    int Skip, Test, Pos, j, i = 0;
    while (Skip = Lines[i++])
    {
        Pos = Lines[i++];   // get starting position
        Test = 3;           // pre-set to 0x03 (player 1 & 2 values bitwise OR'd together)

        // search each of the three boxes in this line
        for (j = 0; j < 3; Pos+= Skip, j++)
        {
            // Bitwise AND the square with the previous value
            //  We make use of the fact that player 1 is 0x01 and 2 is 0x02
            //  Therefore, if any bits are set in the result, it must be all 1's or all 2's
            Test &= b[Pos];
        }

        // All three squares same (and non-zero)?
        if (Test)
            putc(Test+'0',stdout);
    }
}

Lob

Answer 23

Common Lisp, 171 characters

Golf mode:

(defun x(b)(find-if-not 'null(mapcar(lambda(r)(let((v(mapcar(lambda(c)(elt b c))r)))(if(apply '= v)(car v))))'((0 1 2)(3 4 5)(6 7 8)(0 3 6)(1 4 7)(2 5 8)(0 4 8)(2 4 6)))))

Readable mode:

(defun ttt-winner (board)
  (find-if-not 'null
          (mapcar (lambda (row)
                    (let ((vals (mapcar (lambda (cell) (elt board cell)) row)))
                      (if (apply '= vals) (car vals))))
              '((0 1 2) (3 4 5) (6 7 8) (0 3 6) (1 4 7) (2 5 8) (0 4 8) (2 4 6)))))

Edric

Answer 24

Java, 155 chars

After much toil on my first code golf, I was able to pare down the function to 155 chars (Curse you array brackets!). With some math tricks I was able to generalize the three-cell-check for horizontals, verticals, and diagonals. Also, I independently discovered what I see Eric Pi also noted, about testing triplet equivalence with bitwise ands. My method:

int i=-1,j,w=0;int[]a={0,0,2,0,9,3,3,1,3,1,1,1,1,3,2,4};while(++i<4)for(j=a[i];j<a[i+4];j+=a[i+8])if((g[j]&g[j+a[i+12]]&g[j+2*a[i+12]])>0)w=g[j];return w;

Also, I made a class to generate all valid boards for testing (not quite as simple as it sounds). For those of you interested in trying to best 155 in Java, here's my testing class:

public class TicTacToe
{
public static void main(String[] args)
{
    int[][] boards = generateBoards();

    for(int i = 0; i < boards.length; ++i)
    {
        int winner = getWinner(boards[i]);

        System.out.println(winner + "  " + boards[i][0] + " " + boards[i][1] + " " + boards[i][2]);
        System.out.println(        "   " + boards[i][3] + " " + boards[i][4] + " " + boards[i][5]);
        System.out.println(        "   " + boards[i][6] + " " + boards[i][7] + " " + boards[i][8]);
        System.out.println();
    }
}

public static int getWinner(int[] g)
{
    int i=-1,j,w=0;int[]a={0,0,2,0,9,3,3,1,3,1,1,1,1,3,2,4};while(++i<4)for(j=a[i];j<a[i+4];j+=a[i+8])if((g[j]&g[j+a[i+12]]&g[j+2*a[i+12]])>0)w=g[j];return w;
}

public static boolean isValid(int[] board)
{
    // O = 0 : X = 1
    int counts[] = new int[2];

    // Count the number of Xs and Os
    for(int i = 0; i < 9; ++i)
        if(board[i] > 0)
            ++counts[board[i] - 1];

    // Make sure the counts make sense. If not return "no"
    if(!(counts[1] == counts[0] || counts[1] == counts[0] + 1))
        return false;

    // Now we're going to total the number of horizontal/vertical wins
    int wins[] = new int[2];

    // Check rows
    if(board[0] != 0 && board[0] == board[1] && board[1] == board[2]) ++wins[board[0] - 1];
    if(board[3] != 0 && board[3] == board[4] && board[4] == board[5]) ++wins[board[3] - 1];
    if(board[6] != 0 && board[6] == board[7] && board[7] == board[8]) ++wins[board[6] - 1];

    // Check columns
    if(board[0] != 0 && board[0] == board[3] && board[3] == board[6]) ++wins[board[0] - 1];
    if(board[1] != 0 && board[1] == board[4] && board[4] == board[7]) ++wins[board[1] - 1];
    if(board[2] != 0 && board[2] == board[5] && board[5] == board[8]) ++wins[board[2] - 1];

    // Make sure the win counts make sense
    if(wins[0] > 1 && wins[1] > 1)
        return false;

    // Hmmmm... I guess it's a valid board
    return true;
}

public static int[][] generateBoards()
{
    int boardSize = 9;
    int permutationCount = (int)Math.pow(4, 9);
    int[][] boards = new int[permutationCount][boardSize];
    int actualIndex = 0;

    for(int i = 0; i < permutationCount; ++i)
    {
        boolean isUnique = true;

        for(int j = 0; j < boardSize; ++j)
        {
            int x = (i >>> j) & 3;

            if(x == 3)
                isUnique = false;

            boards[actualIndex][j] = x;
        }

        if(isUnique && isValid(boards[actualIndex]))
            ++actualIndex;
    }

    return Arrays.copyOf(boards, actualIndex);
}
}

Not bad I suppose for simple java without any exotic function calls. Enjoy!

Eolithic

Answer 25

LinQ 236

Could probably get less in C# without the function declaration ;)

Function P(ByVal b())
    Dim s() = "012.048.036.147.258.345.678".Split(".")
    If (From x In s Where b(Val(x(0))) & b(Val(x(1))) & b(Val(x(2))) = "111").Any Then Return 1
    If (From x In s Where b(Val(x(0))) & b(Val(x(1))) & b(Val(x(2))) = "222").Any Then Return 2
    Return 0
End Function

Donald

Answer 26

C#, 148 I think.

 int[] m={0,1,3,1,6,1,0,3,1,3,2,3,0,4,2,2};int i,s,w,r=0,o;for(i=0;i<16;i+=2){s=m[i];w=m[i+1];o=v[s];if((o==v[w+s])&&(o==v[s+(w*2)])){r=o;}}return r;

Twicetold

Answer 27

C, 113 characters

f(int*b){char*s="012345678036147258048264\0";int r=0;while(!r&&*s){int q=r=3;while(q--)r&=b[*s++-'0'];}return r;}

I think it works? My first code golf, be gentle.

Every 3 digits encodes 3 cells that need to match. The inner while checks a triad. The outer while checks all 8.

Ascot

C strings are always null-terminated so the \0 can be removed (-2 chars). '0' == 48 so you could use *s++-48 (-1 char). – Monodic

Thanks for the tips - knew the latter but blanked. Didn't know the former. Cheers! – Ascot

Answer 28

C# Solution.

Multiply the values in each row, col & diagonal. If result == 1, X wins. If result == 8, O wins.

int v(int[] b)
{
    var i = new[] { new[]{0,1,2}, new[]{3,4,5}, new[]{6,7,8}, new[]{0,3,6}, new[]{1,4,7}, new[]{2,5,8}, new[]{0,4,8}, new[]{2,4,6} };
    foreach(var a in i)
    {
        var n = b[a[0]] * b[a[1]] * b[a[2]];
        if(n==1) return 1;
        if(n==8) return 2;
    }
    return 0;
}

Alphabetize

If it's 2 * 2 * 2, shouldn't n be 8, rather than 6? – Jadwiga

Answer 29

Python, 140 chars

My first code golf, weighing in at a hefty 140 chars (import statement, I deny you!):

import operator as o

def c(t):return({1:1,8:2}.get(reduce(o.mul,t[:3]),0))
def g(t):return max([c(t[x::y]) for x,y in zip((0,0,0,1,2,2,3,6),(1,3,4,3,3,2,1,1))])

Slightly less obscure g:

def g(t):return max([c(t[x::y]) for x,y in [[0,1],[0,3],[0,4],[1,3],[2,3],[2,2],[3,1],[6,1]]])

Leto

Answer 30

C#, 180 characters :

var s=new[]{0,0,0,1,2,2,3,6};
var t=new[]{1,3,4,3,2,3,1,1};
return(s.Select((p,i)=>new[]{g[p],g[p+t[i]],g[p+2*t[i]]}).FirstOrDefault(l=>l.Distinct().Count()==1)??new[]{0}).First();

(g being the grid)

Could probably be improved... I'm still working on it ;)

Honewort

Answer 31

Probably could be made better, but I'm not feeling particularly clever right now. This is just to make sure Haskell gets represented...

Assuming that b already exists, this will put the result in w.

import List
a l=2*minimum l-maximum l
z=take 3$unfoldr(Just .splitAt 3)b
w=maximum$0:map a(z++transpose z++[map(b!!)[0,4,8],map(b!!)[2,4,6]])

Assuming input from stdin and output to stdout,

import List
a l=2*minimum l-maximum l
w b=maximum$0:map a(z++transpose z++[map(b!!)[0,4,8],map(b!!)[2,4,6]])where
 z=take 3$unfoldr(Just .splitAt 3)b
main=interact$show.w.read

Asteria

Answer 32

c -- 144 characters

Minified:

#define A(x) a[b[x%16]]
int c,b[]={4,8,0,1,2,4,6,0,3,4,5,2,8,6,7,2};int
T(int*a){for(c=0;c<16;c+=2)if(A(c)&A(c+1)&A(c+2))return A(c);return 0;}

Both returns count (one necessary and the other would need replacing with a space).

The array codes for the eight ways to win in triplets starting from even positions and taken mod 16.

Bitwise and trick stolen from Eric Pi.

---

More readable form:

#define A(x) a[b[x%16]]

// Compact coding of the ways to win.
//
// Each possible was starts a position N*2 and runs through N*2+2 all
// taken mod 16
int c,b[]={4,8,0,1,2,4,6,0,3,4,5,2,8,6,7,2};

int T(int*a){
  // Loop over the ways to win
  for(c=0;c<16;c+=2)
    // Test for a win
    if(A(c)&A(c+1)&A(c+2))return A(c);
  return 0;
}

Testing scaffold:

#include <stdlib.h>
#include <stdio.h>

int T(int*);

int main(int argc, char**argv){
  int input[9]={0};
  int i, j;
  for (i=1; i<argc; ++i){
    input[i-1] = atoi(argv[i]);
  };
  for (i=0;i<3;++i){
    printf("%1i  %1i  %1i\n",input[3*i+0],input[3*i+1],input[3*i+2]);
  };
  if (i = T(input)){
    printf("%c wins!\n",(i==1)?'X':'O');
  } else {
    printf("No winner.\n");
  }
  return 0;
}

Bui

Answer 33

C#, 154 163 170 177 characters

Borrowing a couple of techniques from other submissions. (didn't know C# let you init arrays like that)

static int V(int[] b)
{
   int[] a={0,1,3,1,6,1,0,3,1,3,2,3,0,4,2,2};
   int r=0,i=-2;
   while((i+=2)<16&&(r|=b[a[i]]&b[a[i]+a[i+1]]&b[a[i]+a[i+1]*2])==0){}
   return r;
}

Palatable

var instead of int[] will save you 2 chars. – Romanesque

@Judah: var a=new[]{0,1,3,1,6,1,0,3,1,3,2,3,0,4,2,2}; is three characters longer than the original. – Belgium

LOL, I forgot about the part after the equal sign. D'oh! – Romanesque

Answer 34

Ruby, 149 characters

def s(b)(0..8).to_a+[0,3,6,1,4,7,2,5,8,0,4,8,2,4,6].each_slice(3){|m|if b.values_at(*m).uniq.length<2&&b[m[0]]!=0;return b[m[0]];end}return false;end

It's a reasonably straightforward solution, I'm sure I'll be able to reduce it some more. Here is a readable version:

def someone_won(b)
    helper = (0..8).to_a + [ 0, 3, 6, 1, 4, 7, 2, 5, 8, 0, 4, 8, 2, 4, 6]
    helper.each_slice(3) { |m|
        if b.values_at(*m).uniq.length < 2 && b[m[0]] != 0
            return b[m[0]]
        end
    }

    return false
end

Jadwiga

Shouldn't that second 7 in your array be an 8? – Palatable

Answer 35

I'm sure there's a shorter way to do this but... Perl, 141 characters (134 inside the function)

sub t{$r=0;@b=@_;@w=map{[split//]}split/,/,"012,345,678,036,147,258,048,246";for(@w){@z=map{$b[$_]}@$_;$r=$z[0]if!grep{!$_||$_!=$z[0]}@z;}$r;}

Vertebral