El diccionario de Tic Tac Toe

17

Un TicTacToejuego puede ser representado por una cadena que denota la secuencia de posiciones a medida que los jugadores hacen su movimiento.

0 1 2
3 4 5
6 7 8

Suponga que Xsiempre juega primero.

Entonces una cadena de "012345678" denota el juego

XOX
OXO
XOX

Tenga en cuenta que el juego ya está ganado cuando el jugador Xmarca 6, en ese punto el juego termina, otorgando una victoria a X. (es decir, ignorar los movimientos restantes una vez que un jugador gana)

Su desafío (código) es imprimir todos los juegos (orden ordenado) y sus resultados.

El formato

<movesequence>:<result>\n

p.ej:

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

Denota Xpara el primer jugador ganador, Opara el segundo jugador y Dpara los sorteos.

Habrá 9!(362880) juegos.

Aquí hay algunos datos para verificar sus resultados.

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

Este es un codegolf, y el tiempo de ejecución debe ser dentro de un minuto. ¡Que te diviertas!

EDITAR: eliminó el exceso de detalles e imprímalo stdout. No es necesario crear un archivo.

code-golf kolmogorov-complexity tic-tac-toe st0le
fuente
2
Aquí obtengo diferentes números: 212256 victorias para X, 104544 victorias para O y 46080 sorteos (y Wikipedia parece estar de acuerdo conmigo ).
Ventero
@Ventero, volveré a verificar, pero no veo ninguna referencia a esos números en la página.
st0le
@Ventero, tienes razón, editaré esa parte. publicará el md5sum pronto.
st0le
1
La respuesta de Ruby no es la más corta, por lo que no debe ser la respuesta aceptada de acuerdo con sus criterios de puntuación (código de golf).
mbomb007

Respuestas:

3

Ruby 1.9, 201 caracteres

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

Ligeramente golf hasta ahora. Tarda unos 45 segundos en completarse aquí.

  • Editar: (268 -> 249) Escribir en stdout en lugar de un archivo
  • Editar: (249 -> 222) No rellene previamente la matriz con los movimientos de cada jugador.
  • Editar: (222 -> 208) Forma más corta de averiguar si un jugador ganó
  • Editar: (208 -> 213) Volver a 213, la solución anterior era demasiado lenta.
  • Editar: (213 -> 201) Algunas reorganizaciones, espacios en blanco eliminados
Ventero
fuente
Edité la pregunta un poco, no necesita crear un archivo ahora, solo imprímalo.
st0le
4

J, 124 caracteres

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

X gana, O gana y el sorteo cuenta.

Sin embargo, fue un poco doloroso de depurar. :)

randomra
fuente
3

Haskell, 224 222 caracteres

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

Por desgracia, la permutationsfunción de Data.Listno produce permutaciones en orden lexográfico. Así que tuve que gastar 6 personajes en el género.

MtnViewMark
fuente
2

APL (139)

Esto probablemente se puede acortar más, pero ya es bastante difícil. Lo creas o no, se ejecuta en aproximadamente 45 segundos en mi computadora (excluyendo el tiempo que toma enviar todo, cuando sale a la pantalla).

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

Explicación:

  • M←⍳9: Almacene en M los números del 1 al 9. Internamente, este programa usa 1..9 en lugar de 0..8.
  • {... }: una función para obtener todas las permutaciones:
    • 1≥⍴⍵:↑,↓⍵: si la longitud es menor o igual a 1, devuelve el argumento como una matriz.
    • ⋄↑⍪/⍵,∘∇¨⍵∘~¨⍵: de lo contrario, elimine cada carácter ⍵de ⍵, obtenga las permutaciones de eso y agregue el carácter nuevamente.
  • ¨↓: para cada permutación ...
  • {... }: una función que le da al ganador esa permutación:
    • ⊃,/(,/⍕¨⍵-1),':',{... }⍵: obtenga la permutación como una cadena, con todos los números disminuidos en 1 (para obtener la salida requerida de 0..8 en lugar de 1..9), seguido de dos puntos, seguido del carácter que indica el ganador:
      • ⍉5 2⍴0,⍨⍵: separa los movimientos de X de los movimientos de O. Debido a que O tiene un movimiento menor que X, ese espacio se llena con lo 0que no se utiliza y, por lo tanto, no influye en el resultado.
      • {... }¨↓: tanto para el tablero X como para el tablero O, ejecute la siguiente función que determina si hay una victoria en uno de los nueve pasos:
        • (M∘.≥M)∧[2]M∊⍵: Genere un bitboard a partir de los números de movimiento, y andeste bitboard con las cadenas de bits 100000000, 110000000...111111111 para obtener el estado del tablero en cada uno de los nueve momentos en el tiempo.
        • {...}¨↓ : para cada uno de estos, ejecute la siguiente función:
          • ⍉(9⍴2)⊤⎕UCS'㗀㐇㔤㑉㔑㑔': obtener los bitboards para cada posible situación ganadora
          • ⍵∘{⍵≡⍵∧⍺}¨↓: andcada estado ganador con el bitboard actual y verifique si dicho estado ganador todavía está allí
        • ∨/↑: orestos juntos, dando si hay una victoria en este bitboard
      • 1∊T←↑: haga una matriz de 9x2, con los 9 pasos X en la primera fila y los 9 pasos O en la segunda fila. Almacene esto en T. Si hay un 1 en esta matriz, alguien ha ganado.
      • :'XO'[1+</+/T]: Si alguien ha ganado, dé 'X' u 'O' dependiendo de quién 1fue primero.
      • ⋄'D': Si nadie ha ganado, dé 'D'.
  • ↑: haga una matriz de estos para que se muestren en una fila separada.
marinus
fuente
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
fuente
no necesitas el segundo parampermutations
st0le
3
Por favor golf su programa.
mbomb007
1

C ++ sin golf

#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
fuente
44
Por favor golf su programa.
mbomb007
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
fuente