Desafío
Dado un tablero de tres en raya en cualquier formato, determine si es válido o no. Si un tablero puede ser el resultado de un juego de tres en raya, entonces es válido. Por ejemplo, esta placa es válida:
XOX OXO XOXPor el contrario, este tablero no es válido:
XXX XXO OOO
Entrada
- Un tablero completo (9/9) de tic tac toe (el resultado, no el juego).
Reglas
- El formato de entrada debe poder representar las 512 tarjetas de entrada posibles. Debe especificarse, junto con las instrucciones para crearlo si es oscuro / poco claro. Sin embargo, debe indicar las marcas del tablero individualmente.
- Debe haber dos salidas posibles, una para validez y otra para invalidez.
- Puede suponer que el tablero no tiene espacios vacíos.
Casos de prueba
Válido:
XOX OXO XOX XOX XOX OXO XOO OOX OXX OXO XOX OXO
Inválido:
XXX XXX XXX OOO OOO OOO XXX OOO XXX OOO OOX XXX XXO OXO OOX
¿Un poco de ayuda?
Un tablero se considera válido (para este desafío) si y solo si se cumplen las dos condiciones siguientes:
- Hay 5 X y 4 O, o 4 X y 5 O. Por ejemplo,
XXX OXO XXX
se considera inválido, porque hay 7 Xs y 2 Os. - Solo el jugador con 5 puntos ha ganado, o ninguno de ellos ha ganado. Por ejemplo,
XXX OOO OOX
se considera inválido, ya que la fila deO
s o la fila deX
s se formarán primero. Los dos jugadores no pueden tener su turno simultáneamente.
El ganador actual es ...
... la respuesta Jelly de ais523 , ¡con la asombrosa cantidad de 26 bytes!
code-golf
decision-problem
tic-tac-toe
Erik el Outgolfer
fuente
fuente
O O O
X O X
X O X
, para mostrar que el mismo jugador puede tener tanto una fila horizontal como una vertical.Respuestas:
Jalea , 26 bytes
Pruébalo en línea!
El formato de entrada es un poco inusual; es una cadena que representa el tablero, pero con líneas nuevas de Windows (retorno de carro seguido de línea nueva). Por ejemplo,
XXO\r\nOXO\r\nOOX
. (En realidad, cualquier cadena de relleno de dos caracteres entre las líneas funciona, pero las nuevas líneas de Windows son mucho más defendibles que las otras opciones).La idea básica es que buscamos caracteres que aparecen 4 veces en la entrada, pero no tienen tres ocurrencias espaciadas uniformemente en la cadena original. Con dos o más caracteres de relleno entre las líneas de una cuadrícula de 3 × 3, todas las líneas horizontales, verticales y diagonales están espaciadas de manera uniforme, pero ninguna otra línea espaciada de manera uniforme puede tener tres elementos.
Explicación:
El
ð
yµ
s son separadores de cadena , que dividir el programa en múltiples partes que son cada uno independiente. Los he reemplazado con espacios a continuación, para aclarar las cosas un poco.En otras palabras, encontramos la lista de caracteres que aparecen exactamente cuatro veces en la entrada y hacemos una lista que consta de tres copias de cada uno de ellos; encontramos la lista de todas las subsecuencias que están espaciadas uniformemente en la cadena original; y si restamos el segundo del primero, queremos que el resultado tenga longitud 1 (es decir, un jugador jugó cuatro veces pero no ganó). Tenga en cuenta que como estamos en una cuadrícula de 3 × 3 y cada casilla está llena, es imposible que ambos jugadores hayan jugado cuatro veces. En Jelly, 1 es verdadero, 0 es falsey, por lo que no necesitamos hacer nada especial para convertir la lista resultante en booleana. (El
µL
se requiere, sin embargo, porque de lo contrario tanto“XXX”
y“OOO”
sería posibles valores de salida Truthy, y la cuestión requiere que todas las tarjetas válidas dan el mismo resultado.)fuente
JavaScript (ES6),
8887 bytesToma la entrada como una cadena de 9
0
y1
caracteres y devuelve1
para válido,0
para inválido. Ordenamos los personajes en orden. Si los tres caracteres del medio ahora son iguales, entonces el tablero no es válido ya que hay demasiados de una pieza. De lo contrario, convertimos la placa original en binario, volteando los bits si hay más0
s que1
s. En este punto, el tablero es válido si0
no tiene una línea de tres, por lo que simplemente probamos las ocho líneas a través de una matriz de máscaras de bits. Editar: guardado 1 byte gracias a @ETHproductions.fuente
Python 3,
13112712510096 bytesPara un enfoque algorítmico diferente (y uno que se adapte realmente a estos lenguajes de golf de varios bytes con compresión incorporada), en lugar de calcular si el tablero es válido, tengamos un número de 512 bits donde cada bit representa si un tablero en particular es válido o no, y pasa un valor binario que representa el tablero. Además, debido a la simetría, la segunda mitad de la tabla se puede eliminar, junto con un montón de ceros:
El valor de la prueba:
Se representa como el valor binario
0b111010111
y la función devuelve un valor distinto de cero si el tablero es válido.fuente
a&(1<<b)
que no necesita corchetes.if b>255:b=511-b
!if
.Lote, 140 bytes
Toma la entrada como nueve argumentos de línea de comandos y salidas separadas
1
para válido y0
para inválido. Funciona mediante el seguimiento de la cantidad de veces que ve unaO
y una línea ortogonal deOOO
oXXX
. Convenientemente, Batch nos permite realizar aritmética de enteros indirectamente, por lo que no estamos incrementando%%l
sino algunas variables (aunque solo nos interesan las tres variables mencionadas). Luego tenemos que comprobar queX
no ha ganado y que hay cincoO
segundos o queO
no ha ganado y hay cuatroO
segundos.fuente
Mathematica,
8275 bytes¡Gracias a Martin Ender por guardar 7 bytes!
Función sin nombre que toma una lista anidada 3x3 de 1s y 0s como entrada y salida
True
oFalse
.Utiliza cierta flexibilidad práctica de la
Total
función (aquí se ha desarrolladot
): dado un ejemplo de matrize = { {1,2,3} , {4,5,6} , {7,8,9} }
, el comandot[e]
suma los tres vectores (aquí se obtiene{12,15,18}
); el comandot/@e
suma cada sublista individualmente (aquí se obtiene{6,15,24}
); y el comandoe~t~2
suma los nueve elementos (aquí rendimos45
).Entonces, primero probamos, con
3<(b=#~t~2)<6
, si el número total de 1s es 4 o 5; si no salimos conFalse
. Si es así, usamosc=If[b>4,1-#,#]
para forzar que haya cuatro 1s, no cinco. Luego calculamos las sumas de columnast[c]
, las sumas de filast/@c
, la suma de la diagonal principalTr@c
y la suma de la diagonal opuestaTr@Reverse~c
, y usamos~FreeQ~3
para verificar que3
no aparece en ningún nivel en esas sumas calculadas.Nota al margen divertida: a diferencia de la mayoría de las apariencias en este sitio, aquí
Tr
no se usa para sumar una lista unidimensional, sino que se usa según lo diseñado, ¡para calcular el rastro de una matriz bidimensional!fuente
Pyth - 36 bytes
Incluyo diagas y utilizo dos terrarios en su lugar.
Banco de pruebas
fuente
JavaScript (ES6), 101 bytes
Toma la entrada como una máscara binaria de 9 bits donde
X = 1
yO = 0
(MSB = celda superior izquierda, LSB = celda inferior derecha).Casos de prueba
Mostrar fragmento de código
fuente
Python 2,
1581321099291 91123 bytesLa entrada es una lista / tupla de filas, cada una de tres tuplas de cadenas, por ejemplo:
[('X', 'O', 'X'), ('O', 'X', 'O'), ('X', 'O', 'X')]
Ahorré algunos bytes al ignorar las diagonales según la respuesta de @ Maltysen, que también acortó la siguiente expresión.Gracias @vaultah por guardar1718 bytes.Verificación de diagonales resulta ser necesario, lo que eliminó muchos de los ahorros anteriores.
Pruébalo aquí.
Explicación
f
es la entrada aplanada para cortar.w
contiene los personajes con secuencias ganadoras.Cuente las ocurrencias de cada personaje ganador, que será 0 si
w
está vacío o 5 silen(w)
es 1. La suma de 10 cuando ambos tienen una secuencia ganadora es imposible. El ganador que tiene 5 implica que el perdedor tiene 4. No puedes tener> 5 sin una secuencia ganadora.fuente
lambda b:len({x[0]for x in b+zip(*b)if len(set(x))==1})<2and set(map(
b.count,'XO'))=={4,5}
guarda algunos bytes....and{4,5}==set(map(
b.count,'XO'))
guarda un byte más.R,
8882 bytesTodas las combinaciones de tres enteros del 1 al 9 que suman 15 son las filas / columnas / diagonales del cuadrado que se muestra a continuación.
La función toma la entrada como un vector de booleanos, T para "X", F para "O", que es la representación aplanada de la placa. PERO, estos se reordenan para que su índice sea el mismo que el número en el cuadrado, en el orden (2,7,6,9,5,1,4,3,8). Ese orden podría lograrse al aplanar el tablero de la manera normal, y luego cortarlo por c (6,1,8,7,5,3,2,9,4). Así que esto
se representa como:
cual es:
La función primero determina si hay un jugador con exactamente cuatro marcas. Si es así, la función usa el hecho de las cosas que suman 15 para determinar si ese jugador tiene un tres en fila (el tablero no es válido si ese jugador lo tiene).
Si quisiera tomar una placa aplanada convencionalmente como entrada, el código se vería así en su lugar:
Soy nuevo en esto, se agradecería su consejo.
fuente
if()
en su lugar:f=function(x)
if(sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F)
. No se ha probado exhaustivamente. Backticks arruina el código, pero lo esbacktick if backtick(
.x=scan();
si(sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F)
e ingrese como1
y0
. 82 bytes.JavaScript (ES6),
145139131127 bytesIngrese como una cadena separada por espacios, como
"XOX OXO XOX"
. Salidas1
para una placa inválida,0
para una válida. Obviamente, esta no es la mejor técnica, al menos no con JavaScript ...Básicamente, esto verifica si se cumple lo siguiente:
O
s, YLa expresión regular es verificar si un juego ha sido decidido. Coincide con un tablero si hay series de longitud tres de un carácter con 0 (fila), 2 (diagonal inferior derecha), 3 (columna) o 4 caracteres (diagonal inferior izquierda) que separan cada par.
Fragmento de prueba
Mostrar fragmento de código
fuente
Ruby,
104 9991 bytesFormato de entrada: cadena binaria de 9 símbolos (0s y 1s) que representan el tablero, por ejemplo, el primer caso de prueba es
101010101
. Primero conviértalo a un número binario, verifique si popcount es 4 o 5, si es 5 invierta el número para que siempre tengamos 4. Verifique si tres de ellos están alineados (enmascaramiento horizontal, vertical, diagonal).TL; DR : Devuelve falso si el jugador con 4 puntos ganó, verdadero de lo contrario.
Gracias Jordan por los comentarios.
No puedo reproducir la cadena UTF-8 que ahorraría otro byte.
fuente
.select{...}[0]
con.find{...}
."8ǀĤITđ".unpack("U*")
(en caso de que algo se pierda en la traducción, la cadena es el resultado de llamarpack("U*")
a la matriz original; son 12 bytes).any?
lugar denone?
, voltear la salida y guardar un byte completo?Perl 6 ,
10399 bytesUna lambda que acepta una lista de listas como
(('X','O','X'), ('O','X','O'), ('X','O','X'))
, y devuelve un Bool.Funciona así:
c
. (Si no aparece ninguna marca exactamente 5 veces, esto contendrá un valor falso)c
es verdadero y cada línea ganadora es de tipoc
.fuente
PHP, 125 bytes
Yo tenía la misma idea que Arnauld : La tarjeta es válida si hay o bien 4 o 5 bits puestos y, o bien
X
oO
ni nadie tiene una vena (pero no ambos).Para generar una entrada desde el campo, reemplace
X
con1
yO
con0
, unir líneas y convertir binario a decimal, proporcionar como argumento de línea de comando.impresiones
1
válidas; salida vacía para inválido. Corre con-r
.Descompostura
fuente
Rápido, 178 bytes
fuente
ES6 (Javacript),
130,138117 bytesEDICIONES:
Un enfoque extremadamente directo. Probablemente se pueda jugar un poco más.
Acepta entradas como 9 argumentos separados, 1es y 0es
Argumentos: 1-3 - primera fila, 4-6 - segunda fila, 7-9 - tercera fila.
Golfed
"Cama de prueba" interactiva
fuente
[1,0,1,1,0,1,0,1,0]
(XOX XOX OXO
).a+b+c+d+e+f+g+H+i
lugar deF.reduce((r,c)=>r+=c*1)
(en ese momento no necesitaF
) b) escribir.includes(C)
(y pasar alC
valor en línea )?OOO XXX OXO
un fracaso?