Tic Tac Toe: Alle möglichen Positionen ohne Duplikate drucken

8

Schreiben Sie ein Programm, das alle möglichen Tic Tac Toe-Positionen einschließlich des entsprechenden Spielergebnisses ausgibt. Vermeiden Sie doppelte Ausgaben gleicher Positionen.

Das Programm nimmt keine Eingabe entgegen.

Regeln:

  • Eine Positionsausgabe muss aus 9 Zeichen unter Verwendung von Xund Ofür die aufgenommenen Quadrate und einem beliebigen Nicht-Leerzeichen für die leeren Quadrate bestehen
  • Jede Position muss in 3 Zeilen / Spalten gedruckt werden, wobei eine leere Zeile als Trennzeichen zwischen zwei Positionen dient.
  • Zusätzliche Leerzeichen / Leerzeilen / Kästchenzeichen sind willkommen
  • Spieler X geht zuerst
  • Das Ergebnis kann eines der folgenden sein:

    • X hat gewonnen
    • O hat gewonnen
    • Zeichnen
    • Gerade stattfindendes Spiel

    Sie können eine geeignete Visualisierung des Positionsergebnisses auswählen, z. B. als farbigen Text oder als Textanmerkung, sofern diese in der Nähe der entsprechenden Position platziert ist

  • Positionen werden als gleich angesehen, wenn eine durch Drehen oder Spiegeln voneinander erhalten werden kann. Doppelte Positionen dürfen nicht gedruckt werden. (Mit anderen Worten, drucken Sie nur die Gleichheitsklassen.)
    Drucken Sie beispielsweise nur eine der folgenden Optionen:
X••  ••X  •••  •••
•••  •••  •••  •••
•••  •••  X••  ••X
  • Dies ist , also gewinnt der kürzeste Code!

Beispielausgabe:

•••
•••
••• -

X••
•••
••• -

•X•
•••
••• -

•••
•X•
••• -


[…]


XXO
OOX
XXO /

OXO
XXX
OXO X

Tipp: Es gibt 765 Positionen mit 91 Siegen für X, 44 Siegen für O und 3 Unentschieden.


Eine ähnliche Frage wurde bereits gestellt, aber diese ist anders.

ThomasR
quelle
2
Willkommen bei PPCG! Jede Herausforderung bei PPCG muss ein Gewinnkriterium haben. Was ist das Kriterium für diese Herausforderung? Ist es Code-Golf, wo das Programm mit dem kürzesten Bytecount gewinnt?
user41805
Wenn Sie das Gewinnkriterium bestätigen, sollte dieses bald wieder geöffnet werden. Ich habe die Positionen noch nicht gezählt, aber ich habe mich gefragt, ob das leere Brett a) erforderlich b) verboten c) optional ist.
Level River St
Gerade realisiert, haben Sie bereits gesagt, dass der kürzeste Code gewinnt. Bearbeiten im Code-Golf-Tag. Wir bewerten hier normalerweise nach Anzahl der Bytes, da es einige Sprachen gibt, die speziell für die Verwendung von Multibyte-Zeichen zum Verkürzen von Code erfunden wurden, was nicht sehr interessant ist.
Level River St
@ StephenS Das ist eine andere Sache. Ein Byte kann einen beliebigen Wert zwischen 0 und 255 haben. Diese Website kann nur Einzelbyte-Zeichen im Bereich von 32 bis 126 sowie einige andere anzeigen. 256-Byte-Codepages gibt es schon seit Ewigkeiten, und ich selbst habe C-Antworten auf Codepage 437 veröffentlicht. UTF-8 wurde erfunden, weil diese Codepages nicht genügend Zeichen für alle natürlichen Sprachen enthielten, UTF-8 jedoch nicht für die Verarbeitung von Nicht-Text ausgelegt ist Daten mit zufälligen Bytes. Ich bezog mich auf Sprachen wie esolangs.org/wiki/Sclipting, die häufig asiatische Multibyte-Zeichen verwenden, um die Lücke bei der Bewertung von Zeichen auszunutzen
Level River St
@ LevelRiverSt ah, gotcha. Danke für die Info :)
Stephen

Antworten:

5

Gelee , 192 179 168 Bytes

5ĿḢṠµFf0L¬ị⁾-/µ5ĿḢṠµ?
U,µṚ,µ€µ“æɗþƑ’DịFs3,µ€€Fs9s3$€Ṣ
FSµ×’¬
ÑPµA_µọ9n1
,UŒDḢ$€;;ZS€f3,-3
Ç,SS€µṪµṪCµSṠ‘µ?÷Ḣ
Ça3Ŀa4Ŀ
3ṗ9_2s3$€ÇÐf2Ŀ€QḢ€µ;ÑFµ€µ3Ḷ’,“O¤X”yµ€Fs10µs3Gµ€j⁾¶¶

Probieren Sie es online aus! (Dauert ungefähr 30 Sekunden, seien Sie also geduldig).

Wie es funktioniert

Überblick auf hoher Ebene:

In Zwischenschritten speichert dies X als 1, nicht platziert als 0und O als -1. Das Programm generiert alle 3 ^ 9 Möglichkeiten und behält dann nur die gültigen Positionen bei, basierend auf der Erfüllung der drei Kriterien:

  • Es gibt 1 oder 0 mehr X als O.
  • Nicht sowohl X als auch O haben gewonnen.
  • Wenn X gewonnen hat, gibt es 1 mehr X als O. Wenn O gewonnen hat, gibt es eine gleiche Anzahl von Os und Xs.

Anschließend ersetzt das Programm jeden Spielstatus durch alle seine Rotationen und Reflexionen, um eine Liste aller Äquivalenzklassen zu erhalten. Dies ist der Vorgang, der die meiste Zeit in Anspruch nimmt.

Der erste Spielstatus wird aus jeder der Äquivalenzklassen entnommen, und dann wird berechnet, wer gewonnen hat.

Wo dies geschieht Die Zeilen sind zur besseren Lesbarkeit nummeriert

1: 5ĿḢṠµFf0L¬ị⁾-/µ5ĿḢṠµ?          ••calculates who wins (output as -1 or 1) or draw ("-") or in game ("/")
                 µ5ĿḢṠµ?          - if(someone won based on line 5):
   5ĿḢṠ                             - return 1 if X won and -1 if O won
       µ                          - else:
        Ff0L¬ị⁾-/                   - return "/" if the game is in progress and "-" if the game is at a tied end-state
2: U,µṚ,µ€µ“æɗþƑ’DịFs3,µ€€Fs9s3$€Ṣ••outputs the equivalence class to a game state
   U,                             - list of game state [reflected horizontally, unaltered]
     µṚ,µ€                        - for each, replace with the list [reflected vertically,unaltered]
          µ“æɗþƑ’DịFs3,µ€€        - for each, replace with the list [rotated 90 degrees counter-clockwise,unaltered]
                          Fs9s3$€ - reformat into list of game states
                                 Ṣ- Sort
3: FSµ×’¬                         ••outputs truthy iff there is the right number of `X`s to `O`s (condition 1)
   FS                             - d = number of `X`s minus number of `O`s
     µ×’                          - d*(d-1): falsey iff d is 0 or 1
        ¬                         - logical not, to return truthy iff d is 0 or 1
4: ÑPµA_µọ9n1                     ••outputs truthy iff there is the right number of winners (condition 2)
   Ñ                              - the winners. [-3,3] is what we want to return falsy on
    PµA_µ                         - 18 on [-3,3] and 0 otherwise
         ọ9n1                     - not divisible by 9 exactly once: 0 on [-3,3] and 1 otherwise
5: ,UŒDḢ$€;;ZS€f3,-3              ••outputs the number of times each player won.
   ,UŒDḢ$€;;Z                     - the diagonals, rows, and columns of a board
             S€                   - sum of each. Returns -3 or 3 iff the line is only 1s or -1s
               f3,-3              - filter out, keeping only 3s and -3s
6: Ç,SS€µṪµṪCµSṠ‘µ?÷Ḣ             ••return truthy iff the winner corresponds to the respective numbers of X and O (condition 3)
   Ç,SS€                          - list of winners and how many more Xs than Os there are
             µSṠ‘µ?               - if O won, then
        µṪ                          - how many more Xs than Os there are
                                  - else:
          µṪC                       - the complement of how many more Xs than Os there are
                   ÷Ḣ             - deal with no one winning
7: Ça3Ŀa4Ŀ                        ••return truthy iff the game state meets all three conditions
   Ç 3Ŀ 4Ŀ                        - the three conditions: on line 3,4, and 6
    a  a                          - joined by logical ANDs
8: 3ṗ9_2s3$€ÇÐf2Ŀ€QḢ€µ;ÑFµ€µ3Ḷ’,“O¤X”yµ€Fs10µs3Gµ€j⁾¶¶ ••do everything
   3ṗ9_2                        - all possible game states, with -1 for O and 1 for X
        s3$€                    - turn into two-dimensional game boards
            ÇÐf                 - filter based on line 6: if the board meets all three ocnditions
               2Ŀ€Q             - generate the equivalence classes for each and remove repeats based on line 1
                   Ḣ€           - get the first board from each class
                     µ;ÑFµ€     - append the winner to each board based on line 1
   µ3Ḷ’,“O¤X”yµ€                   - map each -1, 0, and 1 to the proper `O`,  `¤`, and `X`.
                Fs10µs3Gµ€         - format each board- winner combos
                          j⁾¶¶     - join the combos by double-newlines
fireflame241
quelle
2

Ruby, 305 Bytes

19683.times{|i|c=(i%3).to_s 
s=(9**8+i/3*6562).to_s(3)
w=0
t=(0..3).map{|j|r=s[1+j*2,9]
w|=1<<r[0..2].sum%8|1<<(c+r[j/2]+r[4+j/2]).sum%8
[r,r.reverse].min}.min
v=t[0..2]+$/+t[7]+c+t[3]+$/+t[6]+t[5]+t[4]
w&=65
b=v.sum%51
w<65&&b>w/64&&b<3-w%2&&t==s[1,9]&&puts(v.tr("012","X.O"),w<1?v.include?(?1):w%31,"")}

Dies funktioniert ähnlich wie bei den anderen Antworten, indem alle 3**9Karten generiert und dann die gültigen herausgefiltert werden. Intern verwenden wir ternäre Zahlen 0=X 1=. 2=Oin der Ausgabe. Durchlaufen Sie cdie 3 möglichen Werte für die Mitte und sdie 3**8 = 6561Werte für den Umfang. Bevor i/3wir in eine Zeichenfolgendarstellung einer ternären Zahl konvertieren , multiplizieren wir mit 6562, um alle Ziffern zu duplizieren, und addieren 3**16, um die Zahl mit einer 1 zu beginnen, um sicherzustellen, dass gegebenenfalls führende Nullen vorhanden sind. wist die Gewinnbedingung - setzen Sie diese auf Null.

Durchlaufen Sie für jede Karte 4 Umdrehungen der Ziffern s, um die lexikalisch niedrigste Version der aktuellen 8-stelligen ternären Zahl zu finden, die den Umfang darstellt. Addieren Sie gleichzeitig die ASCII-Werte der ersten 3 Ziffern (obere Reihe der aktuellen Drehung) und überprüfen Sie anhand dieser Werte, ob ein Gewinn erzielt wurde. Addieren Sie außerdem die ASCII-Werte cund ein Paar diametral entgegengesetzter Ziffern, um zu überprüfen, ob in der Mitte ein Gewinn erzielt wird.

Überprüfen Sie, ob die Ausgabe gültig ist. Wenn sowohl das 1-Bit als auch das 64-Bit wgesetzt sind, gewinnen beide Seiten. Dies ist ungültig. Überprüfen Sie das Gleichgewicht zwischen X und O (wenn es noch keinen Gewinner gibt, kann es entweder gleich X und O oder ein weiteres X sein - aber wenn das Spiel gewonnen ist, gibt es nur einen möglichen Wert, da der Gewinner zuletzt gegangen sein muss.) Um zu vermeiden, dass unterschiedliche Rotationen derselben Karte angezeigt werden, wird nur ausgegeben, wenn die lexikalisch niedrigste Version des Umfangs dem aktuellen Wert von entspricht s[2,9].

Ausgabe der Vorstand , sustituting die Symbole tr("012","X.O"). Der Spielstatus wird unter dem Brett angezeigt. Wenn w = 0 ist, ist dies der Fall, truewenn noch leere Felder vorhanden sind (Spiel falseläuft noch) und wenn das Brett voll ist. Wenn wungleich Null ist, geben wir aus, 1ob Spieler 1 (X) gewonnen hat oder 64%31==2ob Spieler 2 (O) gewonnen hat.

Ungolfed

19683.times{|i|                             #check 3**9 possibilities
  c=(i%3).to_s                              #centre square: 0=X, 1=. 2=O 
  s=(9**8+i/3*6562).to_s(3)                 #perimeter:multiply i/3 by 3**8+1 to duplicate digits, add 3**16 to give a 1 at left side to ensure leading zeros
  w=0                                       #set w=0 to clear wins (1´s bit holds win for X, 64´s bit holds win for O)
  t=(0..3).map{|j|                          #build an array of 4 different rotations of the perimeter
     r=s[1+j*2,9]                           #by taking different 9-character slices of s
     w|=1<<r[0..2].sum%8|                   #add ascii codes mod 8 for top row of current rotation, take sum modulo 8 to give sum of digits. set a bit in w (we only care about bits 0 and 6)
        1<<(c+r[j/2]+r[4+j/2]).sum%8        #do the same for one of the 4 lines through the centre. if j/2=0 check diagonal, if j/2=1 check horizontal/vertical. 
     [r,r.reverse].min}.min                 #add to the array the lexically lowest version(forward or reverse) of the current rotation. When the loop ends, find the lexically lowest version overall and assign to t.
  v=t[0..2]+$/+t[7]+c+t[3]+$/+t[6]+t[5]+t[4]#format the output into a square 012\n 7c3\n 654
  w&=65                                     #clear bits 1 through 5 of w, leave only bits 0 and 6 which are the ones of interest.
  b=v.sum%51                                #valid values of sum of ascii codes in output are 461 (equal 0's and 2's) and 460 (one more 0 than 2). Take modulo 51 to reduce these values to 1 and 2       
  w<65&&                                    #if a maximum of one player has a winning line (not both) and
  b>w/64&&                                  #b must be 1 or 2 (only 2 permitted if O's won)
  b<3-w%2&&                                 #b must be 1 or 2 (only 1 permitted if X's won)
  t==s[1,9]&&                               #s[2,9] is the lexically lowest version of the current board (to avoid duplicates) then 
  puts(v.tr("012","X.O"),                   #output the board, subsituting internal "012" characters for external "X.O"
  w<1?v.include?(?1):w%31,"")               #if nobody won, output true if game in still in play (1's present on board) else false
}                                           #if there is a winner, output (player) 1 for X, (player) w%31=2 for O. Also output a blank line.

Überprüfungsschema

Die folgenden Diagramme zeigen das Rotationsschema (und die Gewinnprüfung in Großbuchstaben). Die Diagramme werden ungedreht angezeigt. Die vier verschiedenen Rotationen werden als Teilzeichenfolgen aus der Doppelkopie von übernommen i/3, wobei die 3 aufeinanderfolgenden Großbuchstaben am Umfang jedes Diagramms (die "Spitze" pro aktueller Rotation) die ersten 3 Zeichen in der 9-stelligen Teilzeichenfolge sind. Für jede Umdrehung wird auch eine Umkehrung mit 9 Zeichen (diagonale Umkehrung um die AE- oder CG-Achse) versucht. Die Karte wird nur ausgegeben, wenn der aktuelle Wert von i/3der lexikalisch niedrigste aller Drehungen und Spiegel ist.

 ABC    abC    aBc    Abc 
 hZd    hZD    hZd    HZD
 gfE    GfE    GFE    Gfe
Level River St.
quelle
2

Python 2 , 648 620 Bytes

import re
M=re.match
x='X';o='O'
R=lambda b,z=[6,3,0,7,4,1,8,5,2]:''.join(b[z[i]]for i in range(9))
p='XXX......|...XXX...|......XXX|X...X...X';q=p.replace(x,o)
def e(b):c=b.count;d=c(x)-c(o);w=M(p,b)or M(p,R(b));v=M(q,b)or M(q,R(b));return 0 if d not in[0,1]else 0 if w and v else(x if d==1 else 0)if w else(o if d==0 else 0)if v else'.'if'.'in b else'/'
h=set()
for n in range(3**9):
 b=reduce(lambda a,v:('.XO'[a[1]%3]+a[0],a[1]/3),range(9),('',n))[0]
 if b not in h:
	u=e(b)
	if u:print'%s\n%s\n%s %s\n'%(b[:3],b[3:6],b[6:],u)
	h.update(reduce(lambda a,v:a+[R(a[-2]),R(a[-1])],range(3),[b,R(b,[2,1,0,5,4,3,8,7,6])]))

Probieren Sie es online aus!

Wahrscheinlich ist hier mit diesem Ansatz ein bisschen geringfügiges Golfen möglich; Aber nicht viele.

Bearbeiten: Danke an die Ovs, die eine Optimierung festgestellt haben, die 28 Bytes gewonnen hat; und 3 von Artemis Fowl

Code ohne Golf

Die Grundidee hier ist: Brute Force jede der 3 ^ 9 = 19683 möglichen Board-Codierungen. Behalten Sie die Konjugate (Rotationen und Reflexionen) von Brettern im Auge, die bereits untersucht wurden, damit Sie keine Einträge duplizieren. Gültige Boards müssen mindestens eine gleiche Anzahl von X und O haben oder ein X mehr als O. Es ist nicht möglich, sowohl einen Gewinn für X als auch einen Gewinn für O zu erzielen. plus einige zusätzliche knifflige Einschränkungen.

import re
from collections import Counter

FLIP_XFRM = [2,1,0,5,4,3,8,7,6]
ROT_XFRM = [6,3,0,7,4,1,8,5,2]

def xfrm(b, xf):
    return ''.join(b[xf[i]] for i in range(9))

def flipIt(b):
    return xfrm(b,FLIP_XFRM)

def rotIt(b):
    return xfrm(b,ROT_XFRM)

def conjugates(b):
    conj = [b, flipIt(b)]
    for i in range(3):
        conj += [rotIt(conj[-2]), rotIt(conj[-1])]
    return conj

def tttToB(n):
    b = ''
    for i in range(9):
        b = '.XO'[n %3]+b
        n /= 3
    return b

def printBoard(b,outcome='.'):
    print '%s\n%s\n%s %s\n' % (b[:3],b[3:6],b[6:],outcome)

def evalBoard(b):
    c = Counter(b)
    if c['X']-c['O'] not in [0,1]:
        return False

    p1 = 'XXX......|...XXX...|......XXX|X...X...X'
    p2 = p1.replace('X','O')

    br = rotIt(b)
    w1 = re.match(p1,b) or re.match(p1,br)    
    w2 = re.match(p2,b) or re.match(p2,br)    
    if w1 and w2:
        return False

    if w1:
        return 'X' if c['X']==c['O']+1 else False

    if w2:
        return 'O' if c['X']==c['O'] else False

    if '.' in b:
        return '.'
    else:
        return '/'

def main():
    history = set()
    for m in range(3**9):
        b = tttToB(m)
        if b not in history:
            outcome = evalBoard(b)
            if outcome:
                printBoard(b,outcome)
            history.update(conjugates(b))

main()
Chas Brown
quelle
Ich glaube nicht, dass du das brauchst Counter. Sie können es durchc=b.count;d=c(x)-c(o)
ovs
@ovs: so vermerkt!
Chas Brown
So groß returnkann seinreturn 0if d not in[0,1]else 0if w and v else(x*(d==1))if w else(o*(d==0))if v else'.'if'.'in b else'/'
Zacharý
Alter Beitrag, den ich kenne, aber das scheinen 623 Bytes zu sein? Sie können die zweite Einrückungsstufe (2 Leerzeichen) durch eine einzelne Registerkarte für 620 Byte ersetzen. Vielleicht wollten Sie dies tun?
Artemis vertraut SE
@ArtemisFowl Ja, das war, bevor ich TIO entdeckte - einfach, Zählfehler zu machen!
Chas Brown