Herausforderung

Bestimmen Sie bei einem Tic-Tac-Toe-Board in einem beliebigen Format, ob es gültig ist oder nicht. Wenn ein Brett das Ergebnis eines Tic-Tac-Toe-Spiels sein kann, ist es gültig. Zum Beispiel ist diese Karte gültig:

XOX
OXO
XOX

XXX
XXO
OOO

Eingang

• Ein vollständiges (9/9) Tic Tac Toe Board (das Ergebnis, nicht das Spiel).

Regeln

• Das Eingabeformat muss alle 512 möglichen Eingabeplatinen abbilden können. Es muss zusammen mit den Anweisungen angegeben werden, um es zu erstellen, wenn es dunkel / unklar ist. Sie müssen die Zeichen der Tafel jedoch einzeln angeben.
• Es müssen zwei mögliche Ausgaben vorhanden sein, eine für die Gültigkeit und eine für die Ungültigkeit.
• Sie können davon ausgehen, dass das Board keine leeren Stellen hat.

Testfälle

Gültig:

XOX
OXO
XOX

XOX
XOX
OXO

XOO
OOX
OXX

OXO
XOX
OXO

Ungültig:

XXX
XXX
XXX

OOO
OOO
OOO

XXX
OOO
XXX

OOO
OOX
XXX

XXO
OXO
OOX

Eine kleine Hilfe?

Ein Brett wird (für diese Herausforderung) nur dann als gültig angesehen, wenn die folgenden beiden Bedingungen erfüllt sind:

• Es gibt 5 X und 4 O oder 4 X und 5 O. Zum Beispiel

  XXX
  OXO
  XXX

  wird als ungültig angesehen, da es 7 Xs und 2 Os gibt.
• Nur der Spieler mit 5 Punkten hat gewonnen, oder keiner von ihnen hat gewonnen. Zum Beispiel,

  XXX
  OOO
  OOX

  wird als ungültig angesehen, da entweder die Reihe von Os oder die Reihe von Xs zuerst gebildet wird. Die beiden Spieler können nicht gleichzeitig an der Reihe sein.

Der aktuelle Gewinner ist ...

... die Gelee-Antwort von ais523 mit erstaunlichen 26 Bytes!

Gelee , 26 Bytes

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

Probieren Sie es online!

Das Eingabeformat ist etwas ungewöhnlich. Es ist eine Zeichenfolge, die das Board darstellt, jedoch mit Windows-Zeilenumbrüchen (Wagenrücklauf gefolgt von Zeilenumbruch). Zum Beispiel XXO\r\nOXO\r\nOOX. (Tatsächlich funktioniert jede aus zwei Zeichen bestehende Auffüllzeichenfolge zwischen den Zeilen, aber Windows-Zeilenumbrüche sind weitaus vertretbarer als die anderen Optionen.)

Die Grundidee ist, dass wir nach Zeichen suchen, die viermal in der Eingabe vorkommen, aber in der ursprünglichen Zeichenfolge keine drei gleichmäßig verteilten Vorkommen haben. Bei zwei oder mehr Zeichen Abstand zwischen den Zeilen eines 3 × 3-Gitters sind alle horizontalen, vertikalen und diagonalen Linien gleichmäßig voneinander getrennt, aber keine andere gleichmäßig voneinander getrennte Linie kann drei Elemente enthalten.

Erläuterung:

Das ðund µs sind Kettentrennzeichen , die das Programm in mehrere Teile aufteilen, die jeweils unabhängig voneinander sind. Ich habe sie durch Leerzeichen unten ersetzt, um die Dinge etwas klarer zu machen.

ṢŒ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

Mit anderen Worten, wir finden die Liste der Zeichen, die genau viermal in der Eingabe vorkommen, und erstellen eine Liste, die jeweils aus drei Kopien besteht. wir finden die Liste aller Teilfolgen, die in der ursprünglichen Zeichenfolge gleichmäßig verteilt sind; und wenn wir die Sekunde von der ersten abziehen, wollen wir, dass das Ergebnis die Länge 1 hat (dh ein Spieler hat vier Mal gespielt, aber nicht gewonnen). Beachten Sie, dass es unmöglich ist, dass beide Spieler vier Mal gespielt haben , da wir auf einem 3 × 3-Raster sind und jedes Feld voll ist . In Jelly ist 1 wahr, 0 ist falsch, daher müssen wir nichts Besonderes tun, um die resultierende Liste in einen Booleschen Wert umzuwandeln. ( Dies µList jedoch erforderlich, da andernfalls beide “XXX”und “OOO”möglicherweise wahrheitsgemäße Ausgabewerte vorliegen und die Frage erfordert, dass alle gültigen Karten dieselbe Ausgabe liefern.)

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

Übernimmt die Eingabe als Zeichenfolge aus 9 0und 1Zeichen und gibt 1für gültig, 0für ungültig zurück. Wir sortieren die Zeichen in der Reihenfolge. Wenn die mittleren drei Zeichen jetzt gleich sind, ist die Tafel ungültig, da zu viele Teile vorhanden sind. Andernfalls konvertieren wir die ursprüngliche Karte in eine Binärdatei und spiegeln die Bits, wenn mehr 0s als 1s vorhanden sind. Zu diesem Zeitpunkt ist die 0Karte gültig, wenn sie keine drei Zeilen enthält. Wir testen daher einfach alle acht Zeilen über ein Array von Bitmasken. Bearbeiten: 1 Byte dank @ETHproductions gespeichert.

Python 3, 131 127 125 100 96 Bytes

Für einen anderen algorithmischen Ansatz (und einen, der wirklich für diese Multi-Byte-Golfsprachen mit integrierter Komprimierung geeignet ist), anstatt zu berechnen, ob die Karte gültig ist, geben wir eine 512-Bit-Zahl an, bei der jedes Bit angibt, ob oder nicht Eine bestimmte Karte ist gültig oder nicht und übergibt einen Binärwert, der die Karte darstellt. Außerdem kann aufgrund der Symmetrie die zweite Tabellenhälfte zusammen mit einer Reihe von Nullen eliminiert werden:

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

Der Testwert:

X X X
O X O
X X X

Wird als Binärwert dargestellt 0b111010111und die Funktion gibt einen Wert ungleich Null zurück, wenn die Karte gültig ist.

Batch, 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

Nimmt Eingaben als neun separate Befehlszeilenargumente und -ausgaben 1für gültig und 0ungültig an. Verfolgt, wie oft eine Ound eine orthogonale Linie von OOOoder angezeigt wird XXX. Praktischerweise können wir mit Batch eine Ganzzahlarithmetik indirekt ausführen, sodass wir nicht inkrementieren, %%lsondern stattdessen eine Variable (obwohl wir nur an den drei genannten Variablen interessiert sind). Wir müssen dann testen, ob entweder Xnicht gewonnen hat und es fünf OSekunden gibt oder ob Onicht gewonnen hat und es vier OSekunden gibt.

Mathematica, 82-75 Bytes

Vielen Dank an Martin Ender für die Einsparung von 7 Bytes!

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

Unbenannte Funktion, die eine 3x3 verschachtelte Liste von Einsen und Nullen als Eingabe und Ausgabe verwendet Trueoder False.

Verwendet eine handliche Flexibilität der TotalFunktion (hier golfen t): Bei einem gegebenen Beispiel-Array summiert der e = { {1,2,3} , {4,5,6} , {7,8,9} }Befehl t[e]die drei Vektoren (hier ergibt sich {12,15,18}); der Befehl t/@esummiert jede Unterliste einzeln (hier ergibt sich {6,15,24}); und der Befehl e~t~2summiert alle neun Elemente (hier ergeben 45).

Also testen wir zuerst mit 3<(b=#~t~2)<6, ob die Gesamtzahl von 1s 4 oder 5 ist; wenn nicht, verlassen wir mit False. In diesem c=If[b>4,1-#,#]Fall erzwingen wir vier Einsen, nicht fünf. Dann berechnen wir die Spaltensummen t[c], die Zeilensummen t/@c, die Summe der Hauptdiagonale Tr@cund die Summe der entgegengesetzten Diagonale Tr@Reverse~cund verwenden ~FreeQ~3, um zu überprüfen, ob 3dies auf keiner Ebene in diesen berechneten Summen auftritt.

Amüsante Randnotiz: Im Gegensatz zu den meisten Erscheinungen auf dieser Website wird hier Trkeine eindimensionale Liste zusammengefasst, sondern tatsächlich wie geplant verwendet - um die Spur einer zweidimensionalen Matrix zu berechnen!

Pyth - 36 Bytes

Ich schließe Diagas ein und benutze stattdessen zwei Ternaries.

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

Test Suite

JavaScript (ES6), 101 Byte

Übernimmt die Eingabe als 9-Bit-Binärmaske, wobei X = 1und O = 0(MSB = obere linke Zelle, LSB = untere rechte Zelle).

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)

Testfälle

let f =

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)

// valid
console.log(f(0b101010101));
console.log(f(0b101101010));
console.log(f(0b100001011));
console.log(f(0b010101010));

// invalid
console.log(f(0b111111111));
console.log(f(0b000000000));
console.log(f(0b111000111));
console.log(f(0b000001111));
console.log(f(0b110010001));

Python 2, 158 132 109 92 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

Die Eingabe ist eine Liste / ein Tupel von Zeilen, von denen jede aus drei Tupeln von Zeichenfolgen besteht, z.
[('X', 'O', 'X'), ('O', 'X', 'O'), ('X', 'O', 'X')]

Durch Ignorieren der Diagonalen pro @ Maltysen-Antwort wurden einige Bytes gespart, was auch den folgenden Ausdruck verkürzte.

Danke @vaultah fürs Speichern 17 18 Bytes.

Es erweist sich als notwendig, die Diagonalen zu überprüfen, was einen Großteil der obigen Einsparungen beseitigt hat.

Probieren Sie es hier aus.

Erläuterung

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

fist die abgeflachte Eingabe für das Schneiden.
wenthält die Zeichen mit Gewinnsequenzen.
Zählen Sie die Vorkommen der einzelnen Gewinncharaktere, die entweder 0 sind, wenn sie wleer sind, oder 5, wenn sie len(w)1 sind. Die 10-Summe, wenn beide eine Gewinnsequenz haben, ist unmöglich. Der Gewinner mit 5 impliziert, dass der Verlierer 4 hat. Sie können nicht> 5 ohne eine Gewinnsequenz haben.

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)

Alle Kombinationen von drei ganzen Zahlen von 1 bis 9, die sich zu 15 summieren, sind die Zeilen / Spalten / Diagonalen des unten gezeigten Quadrats.

2 7 6
9 5 1
4 3 8

Die Funktion nimmt Eingaben als Vektor von Booleschen Werten an, T für "X", F für "O", was die abgeflachte Darstellung der Karte ist. ABER diese werden neu angeordnet, so dass ihr Index mit der Zahl im Quadrat in der Reihenfolge (2,7,6,9,5,1,4,3,8) übereinstimmt. Diese Reihenfolge kann erreicht werden, indem die Platte auf normale Weise abgeflacht und dann mit c (6,1,8,7,5,3,2,9,4) geschnitten wird. Also das

X O X
O X O
X O X

wird dargestellt als:

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

welches ist:

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

Die Funktion ermittelt zunächst, ob es einen Spieler mit genau vier Markierungen gibt. In diesem Fall verwendet die Funktion die Tatsache, dass sich die Summe zu 15 addiert, um zu bestimmen, ob dieser Spieler einen Drei-in-einer-Reihe hat (das Brett ist ungültig, wenn dieser Spieler dies tut).

Wenn Sie eine konventionell abgeflachte Karte als Eingabe verwenden möchten, sieht der Code stattdessen folgendermaßen aus:

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)

Ich bin neu in diesem Bereich, würde gerne beraten.

JavaScript (ES6), 145 139 131 127 Byte

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

Eingabe als durch Leerzeichen getrennte Zeichenfolge, z "XOX OXO XOX". Ausgänge 1für eine ungültige Karte, 0für eine gültige. Dies ist offensichtlich nicht die beste Technik, zumindest nicht mit JavaScript ...

Dies überprüft grundsätzlich, ob beide der folgenden Aussagen zutreffen:

• Es gibt genau 4 oder 5 Os UND
• Es gibt mindestens eines der 5-Instanzen-Teile, das beim Entfernen ein unentschiedenes Spiel erzeugt.

Der reguläre Ausdruck ist zu prüfen, ob ein Spiel entschieden wurde. Es passt zu einer Tafel, wenn es Läufe der Länge 3 eines Zeichens gibt, wobei 0 (Zeile), 2 (Diagonale rechts unten), 3 (Spalte) oder 4 (Diagonale links unten) jedes Paar trennen.

Testschnipsel

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

g=s=>console.log(f(s))

// Valid boards (outputs 0)
g("XOX OXO XOX")
g("XOX XOX OXO")
g("XOO OOX OXX")
g("OXO XOX OXO")

// Invalid boards (outputs 1)
g("XXX XXX XXX")
g("OOO OOO OOO")
g("XXX OOO XXX")
g("OOO OOX XXX")
g("XXO OXO OOX")

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

Eingabeformat: Binäre Zeichenfolge mit 9 Symbolen (0s und 1s), die die Karte darstellt, z. B. der erste Testfall 101010101. Wandle es zuerst in eine Binärzahl um, überprüfe ob popcount 4 oder 5 ist, wenn es 5 ist, invertiere die Zahl, so dass wir immer 4 haben. Überprüfe, ob drei von ihnen ausgerichtet sind (Maskierung mit horizontal, vertikal, diagonal).

TL; DR : Gibt false zurück, wenn der Spieler mit 4 Punkten gewonnen hat, andernfalls true.

Danke Jordan für die Kommentare,

Ich kann den UTF-8-String nicht reproduzieren, der ein weiteres Byte speichern würde.

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

Ein Lambda, das eine Liste von Listen wie annimmt (('X','O','X'), ('O','X','O'), ('X','O','X'))und einen Bool zurückgibt.

Das funktioniert so:

1. Überprüfen Sie, welche Markierung genau fünfmal erscheint, und speichern Sie sie in c. (Wenn keine Markierung genau fünfmal erscheint, enthält dies einen falschen Wert.)
2. Durchlaufen Sie alle Diagonalen, Zeilen und Spalten und filtern Sie die "gewinnenden" heraus (dh diejenigen, bei denen alle drei Buchstaben gleich sind) .
3. Überprüfen Sie, ob cdie Wahrheit stimmt und jede Gewinnlinie vom Typ ist c.

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;

Ich hatte die gleiche Idee wie Arnauld : Die Karte ist gültig, wenn entweder 4 oder 5 Bits gesetzt sind und entweder Xoder Ooder niemand eine Streifen hat (aber nicht beide).

Um eine Eingabe aus dem Feld zu generieren, ersetzen Sie Xmit 1und Omit 0, verbinden Sie die Zeilen und konvertieren Sie die Binärzahl in eine Dezimalzahl. Geben Sie als Befehlszeilenargument an.

druckt 1für gültig; leere Ausgabe für ungültig. Laufen Sie mit -r.

Nervenzusammenbruch

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

Schnell, 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"))}

ES6 (Javacript), 130, 138117 Bytes

EDITS:

• 21 Bytes weniger dank exzellenter Ratschläge von @Neil!
• Die ursprüngliche Version war anfällig für einen Fehler, der nun zu einem Preis von +8 Byte behoben werden sollte. (Danke @ETHproductions für den Hinweis)

Ein extrem geradliniger Ansatz. Kann wohl etwas weiter golfen werden.

Akzeptiert Eingaben als 9 separate Argumente, 1es und 0es

• 1 ist für X
• 0 steht für O

Argumente: 1-3 - erste Reihe, 4-6 - zweite Reihe, 7-9 - dritte Reihe.

Golf gespielt

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

Interaktiver "Prüfstand"

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>