Tic Tac Toe: imprima todas as posições possíveis sem duplicatas

8

Escreva um programa que mostre todas as posições possíveis do Tic Tac Toe, incluindo o resultado do jogo correspondente. Evite saída duplicada de posições iguais.

O programa não aceita entrada.

Regras:

  • Uma saída de posição deve consistir em 9 caracteres, usando Xe Opara os quadrados tirados, e um caractere não-espaço em branco arbitrário para os quadrados em branco
  • Cada posição deve ser impressa em 3 linhas / colunas, com uma linha em branco como separador entre duas posições.
  • Caracteres adicionais de espaço em branco / linhas em branco / desenho da caixa são bem-vindos
  • O jogador X vai primeiro
  • O resultado pode ser um dos seguintes:

    • X venceu
    • O ganhou
    • Desenhar
    • Jogo em progresso

    Você pode escolher uma visualização adequada do resultado da posição, por exemplo, como texto colorido ou como anotação textual, desde que seja colocada perto da posição correspondente

  • As posições são consideradas iguais se uma puder ser obtida da outra por rotação ou espelhamento. As posições duplicadas não devem ser impressas. (Em outras palavras, imprima apenas as classes de igualdade.)
    Por exemplo, imprima apenas um dos seguintes:
X••  ••X  •••  •••
•••  •••  •••  •••
•••  •••  X••  ••X

Saída de amostra:

•••
•••
••• -

X••
•••
••• -

•X•
•••
••• -

•••
•X•
••• -


[…]


XXO
OOX
XXO /

OXO
XXX
OXO X

Dica: Existem 765 posições, com 91 vitórias em X, 44 vitórias em O e 3 empates.


Uma pergunta semelhante foi feita antes, mas esta é diferente.

ThomasR
fonte
2
Bem-vindo ao PPCG! Todo desafio no PPCG precisa ter um critério de vitória. Qual é o critério para esse desafio? É code-golf onde o programa com o menor número de bytes vence?
User41805
Se você confirmar o critério de vencimento, ele deverá ser aberto novamente em breve. Ainda não contei as posições, mas fiquei pensando: o tabuleiro vazio a) é obrigatório b) é proibido c) é opcional?
Level River St
Acabo de perceber, você já disse que o código mais curto vence. Edição na tag code-golf. Normalmente, pontuamos por número de bytes aqui, porque existem alguns idiomas especificamente inventados para usar caracteres multibyte para reduzir o código, o que não é muito interessante.
Level River St
@ Stephenos Isso é uma coisa diferente. Um byte pode ter qualquer valor de 0 a 255. Este site pode exibir apenas caracteres de byte único no intervalo 32-126 e mais alguns outros. As páginas de código de 256 bytes existem há muito tempo e eu mesmo publiquei respostas C na página de códigos 437. O UTF-8 foi inventado porque essas páginas de código não tinham caracteres suficientes para todas as línguas naturais, mas o UTF-8 não foi projetado para lidar com textos não-texto. dados com bytes aleatórios. Eu estava me referindo a línguas como o esolangs.org/wiki/Sclipting que usa extensivamente multibyte caracteres asiáticos para explorar a brecha de pontuação em caracteres
Nível do rio St
@LevelRiverSt ah, entendi. Obrigado pela informação :)
Stephen

Respostas:

5

Geléia , 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⁾¶¶

Experimente online! (Demora cerca de 30 segundos, então seja paciente).

Como funciona

Visão geral de alto nível:

Em etapas intermediárias, isso armazena X como 1, não colocado como 0e O como -1. O programa gera todas as possibilidades 3 ^ 9 e, em seguida, mantém apenas as posições válidas com base no atendimento aos três critérios:

  • Há 1 ou 0 mais X que O.
  • Nem X e O venceram.
  • Se X venceu, há mais 1 X que O. Se O venceu, há um número igual de Os e Xs.

Em seguida, o programa substitui cada estado do jogo por todas as suas rotações e reflexões para obter uma lista de todas as classes de equivalência. Esta é a operação que leva a maior parte do tempo.

O primeiro estado do jogo é retirado de cada uma das classes de equivalência, e quem ganha é calculado.

Onde isso acontece As linhas são numeradas para facilitar a leitura

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

Isso funciona de maneira semelhante às outras respostas, pois gera todas as 3**9placas e depois filtra as válidas. Internamente, usamos números ternários 0=X 1=. 2=Ona saída. Itere cpelos 3 valores possíveis para o centro e spelos 3**8 = 6561valores do perímetro. Antes de converter i/3para uma representação de seqüência de caracteres de um número ternário, multiplicamos por 6562para duplicar todos os dígitos e adicionamos 3**16para iniciar o número com 1, a fim de garantir que haja zeros à esquerda, quando aplicável. wé a condição de vitória - defina como zero.

Para cada placa, repita 4 rotações dos dígitos spara encontrar a versão lexicamente mais baixa do atual número ternário de 8 dígitos que representa o perímetro. Ao mesmo tempo, adicione os valores ASCII dos três primeiros dígitos (linha superior da rotação atual) e use-o para verificar se há uma vitória. Além disso, adicione os valores ascii de ce um par de dígitos diametralmente opostos para verificar se há uma vitória no centro.

Verifique se a saída é válida - Se os bits 1 e 64 westiverem definidos, ambos os lados vencem - isso não é válido. Verifique o saldo de X e O (se ainda não houver vencedor, ele pode ser igual a X e O ou mais um X - mas se o jogo for vencido, existe apenas um valor possível, pois o vencedor deve ter passado por último.) Para evitar mostrar rotações diferentes da mesma placa, somente produza saída se a versão lexicamente mais baixa do perímetro corresponder ao valor atual de s[2,9].

Saída da placa , sustentando os símbolos tr("012","X.O"). O status do jogo é mostrado abaixo do tabuleiro. Se w = 0, isso ocorre truese ainda houver quadrados vazios (o jogo ainda está em andamento) e falsese o tabuleiro estiver cheio. Se wfor diferente de zero, produzimos 1se o jogador 1 (X) venceu ou 64%31==2se o jogador 2 (O) venceu.

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.

Esquema de verificação

Os diagramas abaixo mostram o esquema de rotação (e verificação de vitórias, em maiúsculas). Os diagramas são mostrados sem rotação. As quatro rotações diferentes são tomadas como substrings na cópia dupla de i/3, com as 3 letras maiúsculas consecutivas no perímetro de cada diagrama (o "topo" por rotação atual) sendo os 3 primeiros caracteres na substring de 9 caracteres. Para cada rotação, também é tentada a reversão de 9 caracteres (rotação diagonal sobre o eixo AE ou CG). A placa é emitida apenas se o valor atual de i/3é o mais baixo lexicamente de todas as rotações e espelhos.

 ABC    abC    aBc    Abc 
 hZd    hZD    hZd    HZD
 gfE    GfE    GFE    Gfe
Level River St
fonte
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])]))

Experimente online!

Provavelmente um pouco de golfe menor é possível aqui com essa abordagem; mas não muito.

Edit: Thx para ovs, que notou um ajuste ganhando 28 bytes; e 3 de Artemis Fowl

Código não golfe

A idéia básica aqui é: força bruta cada uma das codificações possíveis de 3 ^ 9 = 19683. Mantenha o controle dos conjugados (rotações e reflexões) das placas que já foram examinadas para não duplicar as entradas. No mínimo, as placas válidas devem ter um número igual de X e O ou mais um X que O. Não é possível obter uma vitória para X e uma vitória para O; além de algumas restrições adicionais complicadas.

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
fonte
Eu não acho que você precisa do Counter. Você pode substituí-lo porc=b.count;d=c(x)-c(o)
ovs 28/05
@ovs: tão notável!
Chas Brown
Esse grande tempo returnpode serreturn 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ý
Post antigo eu sei, mas isso parece ser 623 bytes? Você pode substituir o segundo nível de indentação (2 espaços) por uma única guia para 620 bytes, talvez pretendesse fazer isso?
Artemis ainda não confia
@ArtemisFowl Sim, isso foi antes de eu descobrir o TIO - fácil de cometer erros de contagem!
Chas Brown