The Tic Tac Toe Dictionary

17

3

A TicTacToe game can be represented by a string denoting the sequence of positions as the players make their move.

0 1 2
3 4 5
6 7 8

Assume X always plays first.

So a string of "012345678" denotes the game

X O X
O X O
X O X

Notice, the game is already won when Player X marks 6, at that point the game ends, granting a win to X. (ie, ignore the remaining moves once a player wins)

Your challenge (code) is to print all the games (sorted order) and its results.

The Format

<movesequence>:<result>\n

eg:

012345678:X
012345687:X
012345768:X
...

Denote X for the 1st player winning, O for the second player, and D for Draws.

There will be 9! (362880) games.

Here is some data to verify your results.

'X' Wins: 212256 
'O' Wins: 104544 
Draws : 46080 

This is a codegolf, and runtime should be within a minute. Have Fun!

EDIT: Removed excess details, and just print it on stdout. No need to create a file.

st0le

Posted 2011-02-19T14:09:50.393

Reputation: 2 002

1The Ruby answer isn't the shortest, so it should not be the accepted answer according to your scoring criteria (code-golf). – mbomb007 – 2015-04-13T16:27:50.703

2

I'm getting different numbers here: 212256 wins for X, 104544 wins for O and 46080 draws (and Wikipedia seems to agree with me).

– Ventero – 2011-02-19T15:04:34.763

@Ventero, I'll recheck, but I don't see any reference to those numbers on the page. – st0le – 2011-02-19T15:15:24.413

@Ventero, You're right, i'll edit that part. will post the md5sum soon. – st0le – 2011-02-19T15:17:39.203

Answers

3

Ruby 1.9, 201 characters

r=*[*l=0..8,0,3,6,1,4,7,2,5,8,0,4,8,2,4,6].each_slice(3)
w=->a{r.any?{|b|b&a==b}}
[*l].permutation(9){|a|u=[[],[]];i=-1
u[i%2]<<a[i+=1]while !((x=w[u[1]])||o=w[u[0]])&&i<8
puts a*""+":#{x ??X:o ??O:?D}"}

Slightly golfed so far. Takes about 45 seconds to complete here.

  • Edit: (268 -> 249) Write to stdout instead of a file
  • Edit: (249 -> 222) Don't pre-fill the array with each player's moves.
  • Edit: (222 -> 208) Shorter way to find out if a player won
  • Edit: (208 -> 213) Back to 213, the previous solution was too slow.
  • Edit: (213 -> 201) Some rearrangements, removed whitespace

Ventero

Posted 2011-02-19T14:09:50.393

Reputation: 9 842

I edited the question a bit, you don't need to create a file now, just print it. – st0le – 2011-02-19T16:08:38.753

4

J, 124 chars

((],~':',~1":[){&'DOX'@(</+2*>/)@:(<./"1)@:(((2{m/.@|.),(2{m/.),m"1,>./)"2)@(<:@(>:%2|]),:(%(2|>:)))@(3 3$]))"1((i.!9)A.i.9)

X win, O win and Draw counts check out.

Was a bit painful to debug though. :)

randomra

Posted 2011-02-19T14:09:50.393

Reputation: 19 909

3

Haskell, 224 222 characters

import Data.List
p=sort.permutations
a(e:_:z)=e:a z;a z=z
[c,d]%(e:z)|any((`elem`words"012 345 678 036 147 258 048 246").take 3).p.a.reverse$e=c|1<3=[d,c]%z;_%[]='D'
main=putStr$p['0'..'8']>>=(\s->s++':':"OX"%inits s:"\n")

Alas, the permutations function from Data.List doesn't produce permutations in lexographic order. So I had to expend 6 characters on the sort.

MtnViewMark

Posted 2011-02-19T14:09:50.393

Reputation: 4 779

2

APL (139)

This can probably be shortened more, but it was hard enough as it is. Believe it or not, it runs in about 45 seconds on my computer (excluding the time it takes to output everything, when output to the screen).

↑{⊃,/(,/⍕¨⍵-1),':',{1∊T←↑{∨/↑{⍵∘{⍵≡⍵∧⍺}¨↓⍉(9⍴2)⊤⎕UCS'㗀㐇㔤㑉㔑㑔'}¨↓(M∘.≥M)∧[2]M∊⍵}¨↓⍉5 2⍴0,⍨⍵:'XO'[1+</+/T]⋄'D'}⍵}¨↓{1≥⍴⍵:↑,↓⍵⋄↑⍪/⍵,∘∇¨⍵∘~¨⍵}M←⍳9

Explanation:

  • M←⍳9: Store in M the numbers from 1 to 9. Internally, this program uses 1..9 instead of 0..8.
  • {...}: a function to get all permutations:
    • 1≥⍴⍵:↑,↓⍵: if the length is smaller or equal to 1, return the argument as a matrix.
    • ⋄↑⍪/⍵,∘∇¨⍵∘~¨⍵: otherwise, remove each character in from , get the permutations of that, and add the character back in.
  • ¨↓: for each permutation...
  • {...}: a function that gives the winner for that permutation:
    • ⊃,/(,/⍕¨⍵-1),':',{...}⍵: get the permutation as a string, with all the numbers decreased by 1 (to get the required 0..8 output instead of 1..9), followed by a colon, followed by the character denoting the winner:
      • ⍉5 2⍴0,⍨⍵: separate the moves by X from the moves by O. Because O has one move less than X, that space is filled by 0, which is unused and so does not influence the result.
      • {...}¨↓: for both the X board and the O board, run the following function which determines whether there is a win in one of the nine timesteps:
        • (M∘.≥M)∧[2]M∊⍵: Generate a bitboard from the move numbers, and and this bitboard with the bitstrings 100000000, 110000000 ... 111111111 to get the state of the board at each of the nine moments in time.
        • {...}¨↓: for each of these, run the following function:
          • ⍉(9⍴2)⊤⎕UCS'㗀㐇㔤㑉㔑㑔': get the bitboards for each possible winning situation
          • ⍵∘{⍵≡⍵∧⍺}¨↓: and each winning state with the current bitboard and check if said winning state is still there
        • ∨/↑: or these together, giving whether there is a win on this bitboard
      • 1∊T←↑: make a 9x2 matrix, with the 9 X-timesteps on the first row and the 9 O-timesteps on the second row. Store this in T. If there is a 1 in this matrix, someone has won.
      • :'XO'[1+</+/T]: If someone has won, give 'X' or 'O' depending on whose 1 was first.
      • ⋄'D': If nobody has won, give 'D'.
  • : make a matrix out of these so that they are each displayed on a separate row.

marinus

Posted 2011-02-19T14:09:50.393

Reputation: 30 224

1

Python Ungolfed

from itertools import*
r=range
W=[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
def c(B):
    for i in r(8):
                if B[W[i][0]]==B[W[i][1]]==B[W[i][2]]:
                        return 1
        return 0

for i in permutations('012345678',9):
    B=[]
    for j in r(9):
        B.append(-(j+1))
    k=0
    F=1
    for j in r(9):
        k=[1,0][k]
        B[int(i[j])]=k
        if c(B):
            F=0
            break
    print "".join(i),':',[['0','X'][k],'D'][F]

fR0DDY

Posted 2011-02-19T14:09:50.393

Reputation: 4 337

3Please golf your program. – mbomb007 – 2015-04-13T16:25:13.150

you don't need the second param in permutations – st0le – 2011-02-20T05:23:31.087

1

C++ Ungolfed

#include<iostream>
using namespace std;
#include<algorithm>

int check(int B[])
{
        for (int i=0;i<3;i++)
                if ((B[3*i]==B[3*i+1]&&B[3*i]==B[3*i+2]) || (B[i]==B[i+3]&&B[i]==B[i+6]))
                        return 1;
        if ((B[2]==B[4]&&B[2]==B[6]) || (B[0]==B[4]&&B[0]==B[8]))
                return 1;
        return 0;               
}
int main()
{
        char c[11]="012345678";
        int B[9],i,j;
        do{
                for (i=0;i<9;i++)B[i]=-(i+1);
                for (i=0,j=1;i<9;i++,j=j?0:1)
                {
                        B[c[i]-'0']=j;
                        if (check(B))
                                break;
                }
                printf("%s:%c\n",c,i<9?j?'X':'O':'D');
        }while (next_permutation(c,c+9));
}

fR0DDY

Posted 2011-02-19T14:09:50.393

Reputation: 4 337

4Please golf your program. – mbomb007 – 2015-04-13T16:25:41.430

1

Python 2.7 (237)

from itertools import*
for z in permutations('012345678'):
 k,F=0,[9]*9
 for h in z:
    F[int(h)]=k=1-k
    if any(sum(a)in(0,3)for a in(F[:3],F[3:6],F[6:],F[::3],F[1::3],F[2::3],F[::4],F[2:8:2])):break
 else:k=2
 print"".join(z)+':','OXD'[k]

Daniel

Posted 2011-02-19T14:09:50.393

Reputation: 1 801