Ce tableau Tic-Tac-Toe est-il valide?

48

Défi

À partir d’un tableau de tic-tac-toe dans n’importe quel format, déterminez s’il est valide ou non. Si un tableau peut être le résultat d'un jeu de tic-tac-toe, il est alors valide. Par exemple, ce forum est valide:

XOX
OXO
XOX
Au contraire, ce forum est invalide:

XXX
XXO
OOO

Contribution

  • Un tableau complet (9/9) de tic tac toe (le résultat, pas le jeu).

Règles

  • Le format d’entrée doit pouvoir décrire les 512 cartes d’entrée possibles. Il doit être spécifié, avec les instructions pour le créer s'il est obscur / incertain. Cependant, vous devez indiquer les marques du tableau individuellement.
  • Il doit y avoir deux sorties possibles, une pour la validité et une pour la nullité.
  • Vous pouvez supposer que le tableau n'a pas de places vides.

Cas de test

Valide:

XOX
OXO
XOX

XOX
XOX
OXO

XOO
OOX
OXX

OXO
XOX
OXO

Invalide:

XXX
XXX
XXX

OOO
OOO
OOO

XXX
OOO
XXX

OOO
OOX
XXX

XXO
OXO
OOX

Un peu d'aide?

Un tableau est considéré comme valide (pour ce défi) si et seulement si les deux conditions suivantes sont remplies:

  • Il y a 5 X et 4 O, ou 4 X et 5 O. Par exemple,
    XXX
    OXO
    XXX
    est considéré comme invalide, car il y a 7 X et 2 Os.
  • Seul le joueur avec 5 points a gagné, ou aucun d'entre eux n'a gagné. Par exemple,
    XXX
    OOO
    OOX
    est considéré invalide, puisque la ligne de Os ou la ligne de Xs sera formée en premier. Les deux joueurs ne peuvent pas avoir leur tour simultanément.

Le gagnant actuel est ...

... La réponse de gelée d'ais523 , à un nombre incroyable de 26 octets!

Erik le golfeur
la source
2
Peut-être aussi ajouter un cas de test du genre O O O X O X X O X, pour montrer que le même joueur peut avoir une rangée horizontale et verticale.
smls
2
Cependant, vous devez indiquer les marques du tableau individuellement. Je ne suis pas sûr de comprendre cette partie. Pourriez-vous fournir un contre-exemple?
Arnauld
3
@ Tim X a 4 marques.
Martin Ender
2
@Sparr "Seul le joueur avec 5 marques a gagné ou aucun d'entre eux n'a gagné."
Martin Ender
2
@ Kevin (Réponse au 1er commentaire) Car aucune planche 9/9 ne sera complétée si le deuxième joueur (joueur avec 4 points) gagne.
Erik l'Outgolfer

Réponses:

11

Gelée , 26 octets

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

Essayez-le en ligne!

Le format de saisie est un peu inhabituel; c'est une chaîne représentant le tableau, mais avec les nouvelles lignes de Windows (retour chariot suivi de nouvelle ligne). Par exemple, XXO\r\nOXO\r\nOOX. (En réalité, toute chaîne de remplissage de deux caractères entre les lignes fonctionne, mais les nouvelles lignes de Windows sont beaucoup plus défendables que les autres options.)

L'idée de base est que nous recherchons des caractères qui apparaissent 4 fois dans l'entrée, sans que trois occurrences soient également espacées dans la chaîne d'origine. Si deux ou plusieurs caractères de remplissage sont insérés entre les lignes d'une grille 3 × 3, toutes les lignes horizontales, verticales et diagonales sont espacées de manière égale, mais aucune autre ligne également espacée ne peut comporter trois éléments.

Explication:

Les ðet µsont des séparateurs de chaîne , qui divisent le programme en plusieurs parties indépendantes. Je les ai remplacés par des espaces ci-dessous, pour rendre les choses un peu plus claires.

ṢŒ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 d’autres termes, nous trouvons la liste des caractères qui apparaissent exactement quatre fois dans l’entrée et nous faisons une liste composée de trois copies de chacune d’elles; nous trouvons la liste de toutes les sous-séquences régulièrement espacées dans la chaîne d'origine; et si nous soustrayons la seconde de la première, nous voulons que le résultat soit de longueur 1 (c'est-à-dire qu'un joueur a joué quatre fois mais n'a pas gagné). Notez que comme nous sommes sur une grille 3 × 3 et que chaque case est pleine, il est impossible que les deux joueurs aient joué quatre fois. Dans Jelly, 1 est la vérité, 0 est Falsey, nous n’avons donc rien à faire de spécial pour convertir la liste résultante en un booléen. (Le µLest nécessaire, cependant, parce que sinon les deux “XXX”et “OOO”seraient possibles des valeurs de sortie truthy, et la question exige que tous les conseils valides donnent la même sortie.)

Greg Martin
la source
3
C'est totalement lisible.
Pabrams
21

JavaScript (ES6), 88 87 octets

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

Accepte une entrée en tant que chaîne de 9 0et les 1caractères et les rendements 1pour valide, 0pour invalide. Nous trions les personnages dans l'ordre. Si les trois personnages du milieu sont maintenant identiques, le tableau est invalide car il y en a trop d'un seul morceau. Sinon, nous convertissons la carte d'origine en binaire, en retournant les bits s'il y a plus de 0s que de 1s. À ce stade, la carte est valide si elle 0n’a pas une ligne de trois, nous testons donc simplement les huit lignes via un tableau de masques de bits. Edit: 1 octet enregistré grâce à @ETHproductions.

Neil
la source
@ETHproductions Ah, bien sûr, le résultat ne sera de toute façon que 0 ou 1.
Neil
14

Python 3, 131 127 125 100 96 octets

Pour une approche algorithmique différente (et une qui conviendra vraiment à ces langages de golf multi-octets avec compression intégrée), au lieu de calculer si la carte est valide, établissons un nombre de 512 bits où chaque bit représente si oui ou non un conseil particulier est valide ou non, et transmet une valeur binaire représentant le conseil. De plus, pour des raisons de symétrie, la seconde moitié de la table peut être éliminée, ainsi que des zéros:

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

La valeur de test:

X X X
O X O
X X X

Est représentée sous forme de valeur binaire 0b111010111et la fonction renvoie une valeur non nulle si le tableau est valide.

Ken YN
la source
Suppression de la variable intermédiaire pour 4 octets de moins
Ken YN
Deux octets de moins, car ils a&(1<<b)n'ont pas besoin de crochets.
Ken YN
Supprimez 25 octets en utilisant la symétrie et un de plus en abrégeant les 24 bits nuls les plus bas - il doit y avoir un moyen plus golfeur de le faire if b>255:b=511-b!
Ken YN
J'ai trouvé un moyen plus facile de faire le if.
Ken YN
11

Lot, 140 octets

@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

Prend les entrées sous forme de neuf arguments et sorties de ligne de commande distincts 1pour valide et 0non valide. Fonctionne en suivant le nombre de fois où il voit un Oet une ligne orthogonale de OOOou XXX. De manière pratique, Batch nous permet d'effectuer indirectement des calculs arithmétiques en nombres entiers; nous n'incrémentons donc pas, %%lmais plutôt une variable (bien que nous ne nous intéressions qu'aux trois variables mentionnées). Nous devons ensuite vérifier si la Xvictoire n’a pas été gagnée et il y en a cinq Oou bien Oquatre O.

Neil
la source
10

Mathematica, 82 à 75 octets

Merci à Martin Ender d'avoir économisé 7 octets!

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

Fonction sans nom prenant une liste imbriquée 3x3 de 1 et de 0 en entrée et en sortie Trueou False.

Utilise une certaine souplesse pratique de la Totalfonction (ici mise au golf t): en donnant un exemple de tableau e = { {1,2,3} , {4,5,6} , {7,8,9} }, la commande t[e]additionne les trois vecteurs (ici la production {12,15,18}); la commande t/@eadditionne chaque sous-liste individuellement (cédant ici {6,15,24}); et la commande e~t~2additionne les neuf éléments (cédant ici 45).

Nous vérifions donc d’abord 3<(b=#~t~2)<6si le nombre total de 1 est 4 ou 5; sinon on sort avec False. Si tel est le cas, nous avons l'habitude de c=If[b>4,1-#,#]faire en sorte qu'il y ait quatre 1, pas cinq. Ensuite, nous calculons les sommes de colonne t[c], les lignes t/@c, la somme de la diagonale principale Tr@cet la somme de la diagonale opposée Tr@Reverse~c, et ~FreeQ~3vérifions qu’il 3n’apparaît à aucun niveau dans ces sommes calculées.

Note de côté amusante: contrairement à la plupart des apparences sur ce site, il Trn’est pas utilisé ici pour résumer une liste unidimensionnelle, mais est utilisé comme prévu: pour calculer la trace d’une matrice à deux dimensions!

Greg Martin
la source
6

Pyth - 36 octets

J'inclus les diagas et utilise plutôt deux ternaires.

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

Suite de tests

Maltysen
la source
5

JavaScript (ES6), 101 octets

Prend les entrées sous forme de masque binaire de 9 bits où X = 1et O = 0((MSB = cellule en haut à gauche, LSB = en bas à droite)).

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)

Cas de test

Arnauld
la source
Je savais qu'il devait y avoir une solution (un peu) simple au niveau des bits. Beau travail
ETHproductions
5

Python 2, 158 132 109 92 91 123 octets

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

L'entrée est une liste / un tuple de lignes, chacune trois un tuple de chaînes, par exemple:
[('X', 'O', 'X'), ('O', 'X', 'O'), ('X', 'O', 'X')]

Sauvegardé quelques octets en ignorant les diagonales dans la réponse de @ Maltysen, ce qui a également raccourci l'expression suivante.

Merci @vaultah pour avoir économisé 17 18 octets.

Vérifier les diagonales s’est avéré nécessaire, ce qui a permis de supprimer une grande partie des économies réalisées ci-dessus.

Essayez-le ici.

Explication

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

fest l'entrée aplatie pour le découpage en tranches.
wcontient les personnages avec les séquences gagnantes.
Comptez le nombre d'occurrences de chaque personnage gagnant, qui sera soit 0 si west vide, soit 5 si len(w)est égal à 1. La somme 10 lorsque les deux ont une séquence gagnante est impossible. Le gagnant ayant 5 implique le perdant ayant 4. Vous ne pouvez pas avoir> 5 sans séquence gagnante.

Jake Cobb
la source
lambda b:len({x[0]for x in b+zip(*b)if len(set(x))==1})<2and set(map(b .count,'XO'))=={4,5}enregistre quelques octets.
vaultah
et je viens de remarquer que ...and{4,5}==set(map(b .count,'XO'))enregistre un octet supplémentaire.
vaultah
Je pense que cela considère à tort le dernier exemple "Invalid" de la question comme valide, car il ne garantit pas que le gagnant est le joueur avec 5 points.
smls
@smls Vous avez raison. En vérifiant que cette condition coûte beaucoup d’octets, vous pourrez peut-être jouer au golf plus loin.
Jake Cobb
5

R, 88 82 octets

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

Toutes les combinaisons de trois nombres entiers de 1 à 9 qui totalisent 15 sont les lignes / colonnes / diagonales du carré indiqué ci-dessous.

2 7 6
9 5 1
4 3 8

La fonction prend en entrée un vecteur de booléens, T pour "X", F pour "O", qui est la représentation aplatie du tableau. MAIS, ceux-ci sont réorganisés pour que leur index soit le même que le nombre dans le carré, dans l'ordre (2,7,6,9,5,1,4,3,8). Cet ordre pourrait être obtenu en aplatissant le tableau de la manière habituelle, puis en découpant par c (6,1,8,7,5,3,2,9,4). Donc ça

X O X
O X O
X O X

est représenté comme:

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

lequel est:

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

La fonction détermine d'abord s'il y a un joueur avec exactement quatre marques. Si tel est le cas, la fonction utilise les faits qui ajoutent jusqu'à 15 pour déterminer si ce joueur a trois joueurs de suite (le tableau est invalide si ce joueur en possède).

Si vous voulez utiliser un tableau aplati de manière conventionnelle, le code ressemblerait à ceci:

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)

Je suis nouveau à cela, des conseils seraient appréciés.

ixodesbeta
la source
1
Sauvegardez 2 octets si vous utilisez if()plutôt: f=function(x)if (sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F). Pas complètement testé l'esprit. Les Backticks ruinent le code, mais c'est backtick if backtick(.
Jonathan Carroll
1
Mieux encore; x=scan();si (sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F)et entrée comme 1et 0. 82 octets.
Jonathan Carroll
3

JavaScript (ES6), 145 139 131 127 octets

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

Entrée sous forme de chaîne séparée par des espaces, telle que "XOX OXO XOX". Sorties 1pour une carte invalide, 0pour une carte valide. Ce n'est évidemment pas la meilleure technique, du moins pas avec JavaScript ...

Ceci vérifie fondamentalement si les deux suivants tiennent:

  • Il y a exactement 4 ou 5 Os, ET
  • il y a au moins une pièce parmi les 5 instances qui crée un jeu indécis lorsqu'elle est supprimée.

Le regex est de vérifier si un jeu a été décidé. Il correspond à un tableau si tant qu'il y a des longueurs de longueur trois d'un caractère avec 0 (rangée), 2 (diagonale en bas à droite), 3 (colonne) ou 4 caractères (diagonale en bas à gauche) séparant chaque paire.

Extrait de test

ETHproductions
la source
2

Ruby, 104 99 91 octets

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

Format de saisie: chaîne binaire de 9 symboles (0 et 1) représentant la carte, par exemple le premier cas de test 101010101. Convertissez-le d'abord en un nombre binaire, vérifiez si popcount est égal à 4 ou 5, si 5 inversez le nombre pour obtenir toujours 4. Vérifiez si trois d'entre eux sont alignés (masquage horizontal, vertical, diagonal).

TL; DR : Renvoie faux si le joueur avec 4 marques a gagné, vrai sinon.

Merci Jordan pour les commentaires,

Je ne peux pas reproduire la chaîne UTF-8, ce qui économiserait un autre octet.

GB
la source
Vous pouvez remplacer .select{...}[0]avec .find{...}.
Jordanie
Et vous pouvez sauvegarder un octet supplémentaire en remplaçant le tableau de nombres par "8ǀĤITđ".unpack("U*")(au cas où quelque chose serait perdu dans la traduction, la chaîne est le résultat de l'appel pack("U*")du tableau d'origine; elle est de 12 octets).
Jordanie
Pourriez-vous utiliser any?au lieu de none?, retourner la sortie et sauvegarder un octet entier?
Alexis Andersen
J'ai essayé avec un? au lieu de rien? mais alors j'ai besoin d'un! retourner la sortie.
GB
1

Perl 6 , 103 99 octets

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

Un lambda qui accepte une liste de listes comme (('X','O','X'), ('O','X','O'), ('X','O','X')), et retourne un Bool.

Cela fonctionne comme ceci:

  1. Vérifiez quelle marque apparaît exactement 5 fois et stockez-la dans c. (Si aucune marque n'apparaît exactement 5 fois, cela contiendra une valeur de fausseté)
  2. Parcourez toutes les diagonales, les lignes et les colonnes et filtrez celles qui sont "gagnantes" (c'est-à-dire celles où les trois lettres sont égales) .
  3. Vérifiez si cest la vérité, et chaque ligne gagnante est de type c.
smls
la source
1

PHP, 125 octets

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;

J'ai eu la même idée que Arnauld : Le conseil est valable s'il y a 4 ou 5 bits fixés et soit Xou Oou personne n'a une série (mais pas les deux).

Pour générer une entrée à partir de champ, remplacez Xpar 1et Oavec 0, joignez des lignes et convertissez des données binaires en décimales, en tant qu'argument de ligne de commande.

impressions 1pour valables; sortie vide pour invalide. Courez avec -r.

panne

// 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
la source
1

Rapide, 178 octets

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
la source
0

ES6 (Javacript), 130, 138, 117 octets

EDITS:

  • 21 octets grâce aux excellents conseils de @Neil!
  • La version initiale était sujette à un bogue, qui devrait maintenant être corrigé au coût de +8 octets. (Merci @ETHproductions pour l'avoir signalé)

Une approche extrêmement directe. Peut probablement être joué au golf un peu plus loin.

Accepte les entrées sous la forme de 9 arguments, 1 et 0 séparés

  • 1 est pour X
  • 0 est pour O

Arguments: 1-3 - première rangée, 4-6 - deuxième rangée, 7-9 - troisième rangée.

Golfé

(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])

"Banc d'essai" interactif

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>

Zeppelin
la source
Je peux me tromper, mais il semble que cela ne fait que vérifier s’il ya un gagnant. Un conseil valide ne peut avoir aucun gagnant; par exemple, [1,0,1,1,0,1,0,1,0]( XOX XOX OXO).
ETHproductions
Oui, j'ai perdu la négation en jouant au golf. Il est supposé vérifier qu'un côté opposé n'est pas le gagnant. Devrait être corrigé maintenant. Merci !
Zeppelin
(J'ai commencé à commenter avant la dernière modification) Pouvez-vous a) écrire a+b+c+d+e+f+g+H+iau lieu de F.reduce((r,c)=>r+=c*1)(à quel moment vous n’avez pas besoin F) b) écrire .includes(C)(et passer à Cla valeur de inline )?
Neil
@ Neil, cela fonctionnera probablement, je vais essayer demain. Merci !
Zeppelin
Est-ce OOO XXX OXOun échec?
Ismael Miguel