¿Es válido este tablero Tic-Tac-Toe?

48

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
XOX
Por 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 de Os o la fila de Xs 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!

Erik el Outgolfer
fuente
2
Quizás también agregue un caso de prueba como O O O X O X X O X, para mostrar que el mismo jugador puede tener tanto una fila horizontal como una vertical.
sonríe el
2
Sin embargo, debe indicar las marcas del tablero individualmente. No estoy seguro de entender esa parte. ¿Podría proporcionar un contraejemplo?
Arnauld
3
@Tim X tiene 4 marcas.
Martin Ender
2
@Sparr "Solo el jugador con 5 puntos ha ganado, o ninguno de ellos ha ganado".
Martin Ender
2
@Kevin (Respuesta al primer comentario) Porque nunca se completará un tablero 9/9 si gana el segundo jugador (jugador con 4 puntos).
Erik the Outgolfer

Respuestas:

11

Jalea , 26 bytes

ṢŒrṪ4=$$Ðfx3ðœ-µẆm€6R¤;/µL

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.

ṢŒrṪ4=$$Ðfx3 œ- Ẇm€6R¤;/ L
Ṣ                           sorted version of the input
 Œr                         run-length-encode it
        Ðf                  keep only elements where
   Ṫ                        delete the last element, and it was
    4=                      equal to 4
      $$                    parse Ṫ4= as a group
          x3                repeat each element three times

                Ẇ           all sublists of the input
                 m€         take every nth element of each (€) sublist
                   6R       for each n in 1..6
                     ¤      parse 6R as a group
                      ;/    flatten one level (m€ creates a nested structure)

             œ-             multiset difference
                         L  length of that difference

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 µLse 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.)

Greg Martin
fuente
3
Esto es totalmente legible.
pabrams
21

JavaScript (ES6), 88 87 bytes

s=>(a=[...s]).sort()[5]-a[3]&[7,56,73,84,146,273,292,448].every(j=>j&i,i=`0b`+s^~-a[4])

Toma la entrada como una cadena de 9 0y 1caracteres y devuelve 1para válido, 0para 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ás 0s que 1s. En este punto, el tablero es válido si 0no 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.

Neil
fuente
@ETHproductions Ah, por supuesto, el resultado solo será 0 o 1 de todos modos.
Neil
14

Python 3, 131 127 125 100 96 bytes

Para 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:

def z(b):return int('agqozfx67wwye6rxr508ch2i8qicekpreqkap0725pk',36)<<24&1<<b+(b>255)*(511-b-b)

El valor de la prueba:

X X X
O X O
X X X

Se representa como el valor binario 0b111010111y la función devuelve un valor distinto de cero si el tablero es válido.

Ken YN
fuente
Se eliminó la variable intermedia por 4 bytes menos
Ken YN
Dos bytes menos, ya a&(1<<b)que no necesita corchetes.
Ken YN
Eliminó 25 bytes usando simetría y uno más abreviando los 24 bits cero más bajos: ¡debe haber una forma más golfista de hacerlo if b>255:b=511-b!
Ken YN
Encontramos una forma más golfista de hacer if.
Ken YN
11

Lote, 140 bytes

@set/aXXX=OOO=O=0
@for %%l in (%* %1%2%3 %1%4%7 %1%5%9 %2%5%8 %3%5%7 %3%6%9 %4%5%6 %7%8%9)do @set/a%%l+=1
@cmd/cset/a!XXX*!(O-=5)+!OOO*!~O

Toma la entrada como nueve argumentos de línea de comandos y salidas separadas 1para válido y 0para inválido. Funciona mediante el seguimiento de la cantidad de veces que ve una Oy una línea ortogonal de OOOo XXX. Convenientemente, Batch nos permite realizar aritmética de enteros indirectamente, por lo que no estamos incrementando %%lsino algunas variables (aunque solo nos interesan las tres variables mencionadas). Luego tenemos que comprobar que Xno ha ganado y que hay cinco Osegundos o que Ono ha ganado y hay cuatro Osegundos.

Neil
fuente
10

Mathematica, 82 75 bytes

¡Gracias a Martin Ender por guardar 7 bytes!

t=Total;3<(b=#~t~2)<6&&{t[c=If[b>4,1-#,#]],t/@c,Tr@c,Tr@Reverse@c}~FreeQ~3&

Función sin nombre que toma una lista anidada 3x3 de 1s y 0s como entrada y salida Trueo False.

Utiliza cierta flexibilidad práctica de la Totalfunción (aquí se ha desarrollado t): dado un ejemplo de matriz e = { {1,2,3} , {4,5,6} , {7,8,9} }, el comando t[e]suma los tres vectores (aquí se obtiene {12,15,18}); el comando t/@esuma cada sublista individualmente (aquí se obtiene {6,15,24}); y el comando e~t~2suma los nueve elementos (aquí rendimos 45).

Entonces, primero probamos, con 3<(b=#~t~2)<6, si el número total de 1s es 4 o 5; si no salimos con False. Si es así, usamos c=If[b>4,1-#,#]para forzar que haya cuatro 1s, no cinco. Luego calculamos las sumas de columnas t[c], las sumas de filas t/@c, la suma de la diagonal principal Tr@cy la suma de la diagonal opuesta Tr@Reverse~c, y usamos ~FreeQ~3para verificar que 3no 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í Trno se usa para sumar una lista unidimensional, sino que se usa según lo diseñado, ¡para calcular el rastro de una matriz bidimensional!

Greg Martin
fuente
6

Pyth - 36 bytes

Incluyo diagas y utilizo dos terrarios en su lugar.

JsM+sCBQm@VdU3_BQ?q5KssQ*FJ?qK4!}3JZ

Banco de pruebas

Maltysen
fuente
5

JavaScript (ES6), 101 bytes

Toma la entrada como una máscara binaria de 9 bits donde X = 1y O = 0(MSB = celda superior izquierda, LSB = celda inferior derecha).

n=>[7,56,73,84,146,273,292,448,o=x=0].map((m,i)=>(c-=n>>i&1,m&n^m?m&n||o++:m&&x++),c=4)&&!(c|x&&~c|o)

Casos de prueba

Arnauld
fuente
Sabía que tenía que haber una solución bit a bit (algo) simple. Buen trabajo
ETHproductions
5

Python 2, 158 132 109 92 91 91 123 bytes

def v(b):f=sum(b,());w={x[0]for x in b+zip(*b)+[f[::4],f[-3:1:-2]]if len(set(x))==1};return sum(map(`b`.count,w))==len(w)*5

La 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 guardar 17 18 bytes.

Verificación de diagonales resulta ser necesario, lo que eliminó muchos de los ahorros anteriores.

Pruébalo aquí.

Explicación

def v(b):
  f=sum(b,())
  w={x[0]for x in b+zip(*b)+[f[::4],f[-3:1:-2]]if len(set(x))==1}
  return sum(map(`b`.count,w))==len(w)*5

fes la entrada aplanada para cortar.
wcontiene los personajes con secuencias ganadoras.
Cuente las ocurrencias de cada personaje ganador, que será 0 si westá vacío o 5 si len(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.

Jake Cobb
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.
vaultah
y acabo de notar que ...and{4,5}==set(map(b .count,'XO'))guarda un byte más.
vaultah
Creo que esto considera incorrectamente el último ejemplo "Inválido" de la pregunta como válido, porque no garantiza que el ganador sea el jugador con 5 puntos.
sonríe el
@smls Tienes razón. Verificar esa condición cuesta muchos bytes, tal vez se pueda jugar más.
Jake Cobb
5

R, 88 82 bytes

x=scan();`if`(sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F)

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

2 7 6
9 5 1
4 3 8

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

X O X
O X O
X O X

se representa como:

c(T, F, T, F, T, F, T, F, T)[c(6,1,8,7,5,3,2,9,4)]

cual es:

c(F, T, F, T, T, T, F, T, F)

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:

f=function(x)ifelse(sum(x)%in%4:5,all(apply(combn(c(2,7,6,9,5,1,4,3,8)[which(x==(sum(x)<5))],3),2,sum)!=15),F)

Soy nuevo en esto, se agradecería su consejo.

ixodesbeta
fuente
1
Ahorre 2 bytes si usa 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 es backtick if backtick(.
Jonathan Carroll
1
Mejor todavía; x=scan();si (sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F)e ingrese como 1y 0. 82 bytes.
Jonathan Carroll
3

JavaScript (ES6), 145 139 131 127 bytes

s=>!(q="XO"[s.split`O`.length-5])|![...s].some((c,i)=>c==q&!/(.)(\1|..(\1|.(\1|.\1.).)..)\1/.test(s.slice(0,i)+0+s.slice(i+1)))

Ingrese como una cadena separada por espacios, como "XOX OXO XOX". Salidas 1para una placa inválida, 0para 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:

  • Hay exactamente 4 o 5 Os, Y
  • hay al menos una de las piezas de 5 instancias que crea un juego indeciso cuando se elimina.

La 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

ETHproducciones
fuente
2

Ruby, 104 99 91 bytes

->x{[7,56,448,292,146,73,84,273].none?{|y|b=x.to_i 2;((a=x.count'1')==4?b:a==5?~b:7)&y==y}}

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

GB
fuente
Se puede reemplazar .select{...}[0]con .find{...}.
Jordania
Y puede guardar un byte más reemplazando la matriz de números con "8ǀĤITđ".unpack("U*")(en caso de que algo se pierda en la traducción, la cadena es el resultado de llamar pack("U*")a la matriz original; son 12 bytes).
Jordania
¿podría usar en any?lugar de none?, voltear la salida y guardar un byte completo?
Alexis Andersen
¿Intenté con uno? en lugar de ninguno? pero luego necesito un! para voltear la salida.
GB
1

Perl 6 , 103 99 bytes

{my \c=%(.flat.Bag.invert)<5>;?all c,|(.[0]===c if [eq] $_ for |.flat[<0 4 8>,<2 4 6>],|$_,|.&zip)}

Una lambda que acepta una lista de listas como (('X','O','X'), ('O','X','O'), ('X','O','X')), y devuelve un Bool.

Funciona así:

  1. Compruebe qué marca aparece exactamente 5 veces y guárdela c. (Si no aparece ninguna marca exactamente 5 veces, esto contendrá un valor falso)
  2. Itere sobre todas las diagonales, filas y columnas, y filtre las "ganadoras" (es decir, aquellas en las que las tres letras son iguales) .
  3. Verifique si ces verdadero y cada línea ganadora es de tipo c.
smls
fuente
1

PHP, 125 bytes

for($p=$n=$argv[1];$p;$p/=2)$i+=$p&1;foreach([7,56,448,73,146,292,273,84]as$m)$n&$m^$m?$n&$m||$o++:$x++;echo!$x|!$o&&2>$i^=4;

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 Xo Oni nadie tiene una vena (pero no ambos).

Para generar una entrada desde el campo, reemplace Xcon 1y Ocon 0, unir líneas y convertir binario a decimal, proporcionar como argumento de línea de comando.

impresiones 1válidas; salida vacía para inválido. Corre con -r.

Descompostura

// count set bits
for($p=$n=$argv[1];$p;$p/=2)$i+=$p&1;
    /* ($p/=2 takes longer than $p>>=1, but eventually
       $p will come close enough to 0 for the loop to finish */
// count streaks for X and O
foreach([7,56,448,73,146,292,273,84]as$m)
    $n&$m^$m            // ($n masked with streak)!=streak <=> no streak for X
        ?$n&$m||$o++    // true: O has a streak if ($n masked with streak) is empty
        :$x++;          // false: X has a streak
echo!$x|!$o&&2>$i^=4;   // valid if not both have a streak
                        // AND $i is 4 or 5 (toggle 4 -> result 0 or 1)
Titus
fuente
1

Rápido, 178 bytes

func t(i:String)->Bool{let r=i.characters.filter({$0=="X"}).count;let g=i.characters.split(separator:"\n").map(String.init).contains;return(r==5||r==4)&&(!g("XXX") && !g("OOO"))}
Caleb Kleveter
fuente
0

ES6 (Javacript), 130, 138117 bytes

EDICIONES:

  • ¡21 bytes de descuento gracias a los excelentes consejos de @Neil!
  • La versión inicial era propensa a un error, que ahora debería corregirse a un costo de +8 bytes. (Gracias @ETHproductions por señalarlo)

Un enfoque extremadamente directo. Probablemente se pueda jugar un poco más.

Acepta entradas como 9 argumentos separados, 1es y 0es

  • 1 es para X
  • 0 es para O

Argumentos: 1-3 - primera fila, 4-6 - segunda fila, 7-9 - tercera fila.

Golfed

(a,b,c,d,e,f,g,h,j)=>![a+b+c,d+e+f,g+h+j,a+d+g,b+e+h,c+f+j,a+e+j,g+e+c,7].some(x=>x=="7777307777"[a+b+c+d+e+f+g+h+j])

"Cama de prueba" interactiva

var a=b=c=d=e=f=g=h=j=0;

T=(a,b,c,d,e,f,g,h,j)=>![a+b+c,d+e+f,g+h+j,a+d+g,b+e+h,c+f+j,a+e+j,g+e+c,7].some(x=>x=="7777307777"[a+b+c+d+e+f+g+h+j]);

function test() {
  if(T(a,b,c,d,e,f,g,h,j)) {
     grid.style.backgroundColor='green';
     msg.innerHTML="GOOD"
  } else {
     grid.style.backgroundColor='red';
     msg.innerHTML="BAD"
  }
}
<table id=grid style="background: red">
<thead>
  <tr>
     <td id=msg align="center" colspan="3">BAD</td>
    </tr>
  </thead>
  <tr>
      <td><input type="checkbox" onchange="a=this.checked*1;test();" id="ca"/></td>
      <td><input type="checkbox" onchange="b=this.checked*1;test();" id="cb"/></td>
      <td><input type="checkbox" onchange="c=this.checked*1;test();" id="cc"/></td>
    </tr>
    <tr>
      <td><input type="checkbox" onchange="d=this.checked*1;test();" id="cd"/></td>
      <td><input type="checkbox" onchange="e=this.checked*1;test();" id="ce"/></td>
      <td><input type="checkbox" onchange="f=this.checked*1;test();" id="cf"/></td>
    </tr>
    <tr>
      <td><input type="checkbox" onchange="g=this.checked*1;test();" id="cg"/></td>
      <td><input type="checkbox" onchange="h=this.checked*1;test();" id="ch"/></td>
      <td><input type="checkbox" onchange="j=this.checked*1;test();" id="cj"/></td>
    </tr>
 </table>

zepelín
fuente
Puedo estar equivocado, pero parece que esto solo verifica si hay un ganador. Un tablero válido no puede tener un ganador; por ejemplo, [1,0,1,1,0,1,0,1,0]( XOX XOX OXO).
ETHproductions
Sí, he perdido la negación mientras jugaba golf. Se supone que debe verificar que un lado opuesto no sea el ganador. Debería arreglarse ahora. Gracias !
zeppelin
(Comencé a comentar antes de la última edición) ¿Puede a) escribir en a+b+c+d+e+f+g+H+ilugar de F.reduce((r,c)=>r+=c*1)(en ese momento no necesita F) b) escribir .includes(C)(y pasar al Cvalor en línea )?
Neil
@Neil, esto probablemente funcionará, lo intentaré mañana. Gracias !
zeppelin
Es OOO XXX OXOun fracaso?
Ismael Miguel