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.

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

回答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])

回答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")])

回答4:

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.

回答5:

J, 50 chars

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

回答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.

回答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.

回答8:

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.

回答9:

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.

回答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

回答11:

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:

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]

回答13:

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
}

回答14:

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

回答15:

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

回答16:

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

回答17:

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)

回答18:

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

回答19:

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>

回答20:

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.

回答21:

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?

回答22:

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

回答23:

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

回答24:

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

回答25:

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

回答26:

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

回答27:

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]]])

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

回答29:

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

回答30:

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.