Das Tic Tac Toe Wörterbuch

17

Ein TicTacToeSpiel kann durch eine Zeichenfolge dargestellt werden, die die Reihenfolge der Positionen angibt, an denen sich die Spieler bewegen.

0 1 2
3 4 5
6 7 8

Angenommen, es wird Ximmer zuerst gespielt.

So bezeichnet eine Zeichenfolge von "012345678" das Spiel

XOX
OXO
XOX

Beachten Sie, dass das Spiel bereits gewonnen ist, wenn der Spieler das Spiel zu diesem Zeitpunkt als beendet Xmarkiert 6und einen Gewinn für gewährt X. (dh ignoriere die verbleibenden Züge, sobald ein Spieler gewinnt)

Ihre Herausforderung (Code) besteht darin, alle Spiele (sortierte Reihenfolge) und ihre Ergebnisse zu drucken.

Das Format

<movesequence>:<result>\n

z.B:

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

Bezeichnen Sie Xfür den ersten Spieler, der gewinnt, Ofür den zweiten Spieler und Dfür Unentschieden.

Es wird 9!(362880) Spiele geben.

Hier sind einige Daten, um Ihre Ergebnisse zu überprüfen.

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

Dies ist ein Codegolf und die Laufzeit sollte innerhalb einer Minute liegen. Habe Spaß!

BEARBEITEN: Entfernte überschüssige Details und drucke sie einfach auf stdout. Keine Notwendigkeit, eine Datei zu erstellen.

st0le
quelle
2
Ich erhalte hier unterschiedliche Zahlen: 212256 Siege für X, 104544 Siege für O und 46080 Unentschieden (und Wikipedia scheint mir zuzustimmen ).
Ventero
@Ventero, ich werde es noch einmal überprüfen, aber ich sehe keinen Hinweis auf diese Nummern auf der Seite.
st0le
@Ventero, Sie haben Recht, ich werde diesen Teil bearbeiten. werde demnächst die md5sum posten.
st0le
1
Die Ruby-Antwort ist nicht die kürzeste, daher sollte sie nicht die akzeptierte Antwort gemäß Ihren Bewertungskriterien sein (Code-Golf).
mbomb007

Antworten:

3

Ruby 1.9, 201 Zeichen

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

Bisher leicht golfen. Die Fertigstellung dauert hier etwa 45 Sekunden.

  • Editieren: (268 -> 249) Schreibe auf stdout anstatt auf eine Datei
  • Bearbeiten: (249 -> 222) Fülle das Array nicht mit den Zügen jedes Spielers vor.
  • Bearbeiten: (222 -> 208) Kurzer Weg, um herauszufinden, ob ein Spieler gewonnen hat
  • Bearbeiten: (208 -> 213) Zurück zu 213 war die vorherige Lösung zu langsam.
  • Edit: (213 -> 201) Einige Umlagerungen, Leerzeichen entfernt
Ventero
quelle
Ich habe die Frage ein wenig bearbeitet. Sie müssen jetzt keine Datei erstellen, sondern nur drucken.
st0le
4

J, 124 Zeichen

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

X Sieg, O Sieg und Unentschieden zählen Check-out.

War ein bisschen schmerzhaft zu debuggen. :)

randomra
quelle
3

Haskell, 224 222 Zeichen

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

Leider erzeugt die permutationsFunktion von Data.Listkeine Permutationen in lexografischer Reihenfolge. Also musste ich 6 Zeichen für die Sortierung aufwenden.

MtnViewMark
quelle
2

APL (139)

Dies kann wahrscheinlich mehr verkürzt werden, aber es war schon schwer genug. Ob Sie es glauben oder nicht, auf meinem Computer dauert es ungefähr 45 Sekunden (außer der Zeit, die für die Ausgabe von allem auf dem Bildschirm erforderlich ist).

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

Erläuterung:

  • M←⍳9: Speichern Sie in M ​​die Zahlen von 1 bis 9. Intern verwendet dieses Programm 1..9 anstelle von 0..8.
  • {... }: eine Funktion, um alle Permutationen zu erhalten:
    • 1≥⍴⍵:↑,↓⍵: Wenn die Länge kleiner oder gleich 1 ist, geben Sie das Argument als Matrix zurück.
    • ⋄↑⍪/⍵,∘∇¨⍵∘~¨⍵: ansonsten entferne jedes Zeichen in von , erhalte die Permutationen davon und füge das Zeichen wieder in hinzu.
  • ¨↓: für jede Permutation ...
  • {... }: eine Funktion, die den Gewinner für diese Permutation gibt:
    • ⊃,/(,/⍕¨⍵-1),':',{...}⍵ : Erhalte die Permutation als String, wobei alle Zahlen um 1 verringert werden (um die erforderliche 0..8-Ausgabe anstelle von 1..9 zu erhalten), gefolgt von einem Doppelpunkt, gefolgt von dem Zeichen, das den Gewinner bezeichnet:
      • ⍉5 2⍴0,⍨⍵: trenne die Züge mit X von den Zügen mit O. Da O einen Zug weniger als X hat, wird dieser Raum mit gefüllt 0, was nicht genutzt wird und das Ergebnis nicht beeinflusst.
      • {... }¨↓: Führen Sie für die X-Karte und die O-Karte die folgende Funktion aus, die bestimmt, ob in einem der neun Zeitschritte ein Gewinn erzielt wird:
        • (M∘.≥M)∧[2]M∊⍵Generieren Sie eine Bitboard aus dem Umzug Zahlen und: anddiese Bitboard mit dem bitstrings 100000000, 110000000... 111111111den Zustand der Platte an jeden der neun Momente in der Zeit zu erhalten.
        • {... }¨↓: Führen Sie für jede dieser Funktionen die folgende Funktion aus:
          • ⍉(9⍴2)⊤⎕UCS'㗀㐇㔤㑉㔑㑔': Holen Sie sich die Bitboards für jede mögliche Gewinnsituation
          • ⍵∘{⍵≡⍵∧⍺}¨↓: andJeder Gewinnstatus mit dem aktuellen Bitboard und prüfen, ob der Gewinnstatus noch vorhanden ist
        • ∨/↑: ordiese zusammen geben, ob es einen Gewinn auf diesem Bitboard gibt
      • 1∊T←↑: Erstelle eine 9x2-Matrix mit den 9 X-Zeitschritten in der ersten Reihe und den 9 O-Zeitschritten in der zweiten Reihe. Speichern Sie dies in T. Wenn es eine 1 in dieser Matrix gibt, hat jemand gewonnen.
      • :'XO'[1+</+/T]: Wenn jemand gewonnen hat, geben Sie "X" oder "O", je nachdem, wer 1zuerst war.
      • ⋄'D': Wenn niemand gewonnen hat, geben Sie 'D'.
  • : Bilde daraus eine Matrix, so dass sie jeweils in einer eigenen Zeile angezeigt werden.
Marinus
quelle
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
quelle
Sie brauchen nicht den zweiten Parameter inpermutations
st0le 20.02.11
3
Bitte spielen Sie Ihr Programm.
mbomb007
1

C ++ Ungolfed

#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
quelle
3
Bitte spielen Sie Ihr Programm.
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
quelle