2531

35
+39  Q:

## Code Golf: Tic Tac Toe

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.

+35  A:

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])
``````
Wow wtf, I have *no* idea how that works :P
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
Wow, now I see. That's quite clever.
Blame Donald A. Norman's "Things That Make Us Smart" for that trick: http://www.amazon.com/Things-That-Make-Smart-Attributes/dp/0201626950
+1 Fantastic approach!
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.
very clever... but doesn't match the requirements ;)
Put down that sudoku and get to work!
A:

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;}
``````
+8  A:

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.

+1 for the strategy, even if the code is a bit long.
A:

# 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
``````
Shouldn't that second 7 in your array be an 8?
@Jacob: Yes, it should, thanks!
+1  A:

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);}
}
``````

``````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);
}
}
``````
A:

## 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;
}
``````
var instead of int[] will save you 2 chars.
@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.
LOL, I forgot about the part after the equal sign. D'oh!
A:

## 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.

``````#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;
}
``````
+22  A:

# 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;
}
``````
Whoa! The `b-=48` bit is sneaky. And the `s|=...` is good too. My hat's off to you, sir!
How do you guarantee that the final `*++k` is evaluated after the preceding `*k`'s? Is there a sequence point I'm not seeing?
@Potatoswatter: I wonder the same when the gcc-generated binary doesn't give me errors on this. Looks like just an implementation detail.
Why not use a `\t` instead of a literal tab character?
@Alex why waste a character?
A:

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
``````
+3  A:

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

``````echo 0;
``````

7 chars

Good one... except that you can't assume the players will play properly ;)
It's code golf, you can assume whatever you want! :D
This doesn't answer the questions, because the question *does not* assume that the game has come to an end.
@dmckee if the game hasn't come to an end, then nobody has won, so this solution will output the correct answer.
+1  A:

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
``````
+2  A:

## 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]
``````
+6  A:

## 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.

A:

## 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 ;)

+1  A:

# 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)
``````
+9  A:

## 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.

This is a crazy regex.
Love the regex solution.
:), @mobrule Not as short as your similar approach without the regex, though. :(
My skull has cracked open and beams of light are shining through the cracks after reading this.
@mercator: looks like it could be shortened the parts or regex with \4 and \5 as very similar (just differ by number of dots).
@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. ;)
+2  A:

## (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.

Nice... we had similar ideas but you were much more clever.
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.
A:

# 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]]])
``````
+1  A:

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
``````
I think you can make it shorter if you remove the `ByVal` instruction.
(.NET) ide puts it back in again so i thought i should leave it there to be fair
I don't think you can chain comparisons together like that, even in VB.
+2  A:

## 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.

+12  A:

## 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")])
``````
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.
A:

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

</script>
</body>
</html>
``````
You don't need the `+0`, because `x["1"] == x[1]` in ECMAScript.
@KennyTM nice thanks
`0 == 0 == 1` is true.
ok check it out now :O
+4  A:

## 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.

A:

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;
}
``````
If it's `2 * 2 * 2`, shouldn't `n` be 8, rather than 6?
Yes, I posted in haste. Tidied up. Thanks.
A:

## 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.

C strings are always null-terminated so the `\0` can be removed (-2 chars). `'0' == 48` so you could use `*s++-48` (-1 char).
Thanks for the tips - knew the latter but blanked. Didn't know the former. Cheers!
+4  A:

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.

+1 for the 2.0801 :D
A:

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;
``````
+2  A:

# 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
}
``````
+9  A:

## J, 50 chars

``````w=:3 : '{.>:I.+./"1*./"1]1 2=/y{~2 4 6,0 4 8,i,|:i=.i.3 3'
``````
Wow! this is fantastic
A:

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
``````
A:

## 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!

+1  A:

## 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.

A:

## 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)))))
``````

``````(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)))))
``````
+1  A:

## 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?

+1  A:

# 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