21
\$\begingroup\$

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.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ I'm getting different numbers here: 212256 wins for X, 104544 wins for O and 46080 draws (and Wikipedia seems to agree with me). \$\endgroup\$
    – Ventero
    Feb 19, 2011 at 15:04
  • \$\begingroup\$ @Ventero, I'll recheck, but I don't see any reference to those numbers on the page. \$\endgroup\$
    – st0le
    Feb 19, 2011 at 15:15
  • \$\begingroup\$ @Ventero, You're right, i'll edit that part. will post the md5sum soon. \$\endgroup\$
    – st0le
    Feb 19, 2011 at 15:17
  • 1
    \$\begingroup\$ The Ruby answer isn't the shortest, so it should not be the accepted answer according to your scoring criteria (code-golf). \$\endgroup\$
    – mbomb007
    Apr 13, 2015 at 16:27

7 Answers 7

4
\$\begingroup\$

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. :)

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ I edited the question a bit, you don't need to create a file now, just print it. \$\endgroup\$
    – st0le
    Feb 19, 2011 at 16:08
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

JavaScript (V8), 174 bytes

f=(j,w,p,x,o)=>(A=[-1,7,56,73,84,146,273,292,448],g=n=>!A.every(q=>q&n^q),w=w||g(x)|2*g(o),x+o)^511?A.map((_,i)=>x+o>>i&1||f(!j,w,[p]+i,x|!j<<i,o|j<<i)):print(p+':','DXO'[w])

Try it online!

Or see the statistics

How?

We use 8 bit-masks stored in the array \$A\$ to identify all possible winning patterns. There's a dummy leading \$-1\$ in \$A\$ (which will always cause the test to fail) so that we have 9 entries. This allows us to re-use \$A\$ to iterate on all squares of the grid.

The bit-masks for X and O are stored in the variables \$x\$ and \$o\$ respectively. The variable \$j\$ is a flag telling which turn it is (false or undefined for X, true for O). The variable \$w\$ holds the winner (\$0\$ for draw, \$1\$ for X, \$2\$ for O) and may not be changed anymore once it's non-zero. The variable \$p\$ is the permutation of moves as a string.

\$\endgroup\$
0
\$\begingroup\$

Python 3 + golfing-shortcuts, 211 bytes

from s import*
for Z in Im('012345678'):
 K,F=0,[9]*9
 for H in Z:
    F[int(H)]=K=1-K
    if a(s(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
 p(sj('',Z)+':','OXD'[K])

A port of Daniel's answer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.