Determinar o vencedor do jogo da velha (baseado na rodada)

26

Vamos jogar um pouco de código-golfe!

O desafio é encontrar o vencedor de um jogo de Tic-Tac-Toe.

Isso já foi feito muitas vezes, fornecendo um quadro com um vencedor claro, mas aqui está a diferença:

As células são numeradas assim:

1|2|3
-+-+-
4|5|6
-+-+-
7|8|9

Você obtém uma matriz de exatamente 9 movimentos assim:

{3, 5, 6, 7, 9, 8, 1, 2, 3}

Isso é analisado da seguinte maneira:

  • O jogador 1 marca a célula 3
  • Jogador 2 marca célula 5
  • O jogador 1 marca a célula 6
  • O jogador 2 marca a célula 7
  • O jogador 1 marca a célula 9
  • Jogador 1 ganhou

Nota: O jogo não para depois que um jogador vence, pode acontecer que o jogador perdedor consiga fazer três seguidas após o jogador vencedor, mas apenas a primeira vitória conta.

Seu trabalho agora é obter 9 números como entrada e saída do jogador vencedor e da rodada em que a vitória ocorreu. Se ninguém vencer, produza algo constante de sua escolha. Você pode receber entrada e fornecer saída por qualquer média / formato padrão.

Diverta-se!

Mais alguns exemplos, conforme solicitado:

{2,3,4,5,6,7,1,8,9} => Player 2 wins in round 6
{1,2,4,5,6,7,3,8,9} => Player 2 wins in round 8
{1,2,3,5,4,7,6,8,9} => Player 2 wins in round 8
Grunzwanzling
fonte
11
Bem-vindo ao PPCG! Este é um bom primeiro post, mas geralmente não gostamos de formatos de entrada / saída muito restritivos . Você consideraria remover o "Jogador X vence na rodada Y" e deixar a saída em qualquer formato razoável, como uma lista [X, Y]? Em caso de empate, podemos gerar outro valor consistente? Eu recomendo, porque imprimir essas cordas exatas não faz parte do golfe. Para idéias de desafios futuros, recomendo usar a sandbox . :-)
Sr. Xcoder
Desculpe, minha culpa. Eu acho que está correto agora.
Grunzwanzling
Leia o desafio até o fim, digo que pode haver um empate e que você pode produzir algo de sua escolha quando isso acontecer. Volto {2,6} quando o jogador 2 vence na rodada 6 e {0,0} quando ninguém vence.
Grunzwanzling
Podemos usar tudo indexado a 0? (células, jogadores, rodadas)
Arnauld
1
"Você recebe exatamente uma seqüência de nove movimentos assim: {3, 5, 6, 7, 9, 8, 1, 2, 3}" - deve 3realmente aparecer duas vezes?
Jonathan Allan

Respostas:

8

Retina , 114 bytes

(.)(.)
$1O$2X
^
123;;456;;789¶X
{`(.)(.*¶)(.)\1
$3$2
}`.*(.)(.)*\1(?<-2>.)*(?(2)(?!))\1.*¶(..)*
$1$#3
.*¶
T
T`d`Rd

Experimente online! Com base na minha resposta a Tic-Tac-Toe - X ou O? . Saída X<N>se o primeiro jogador vencer após os Nturnos, O<N>se o segundo jogador vencer, Tse nenhum deles vencer. Explicação:

(.)(.)
$1O$2X
^
123;;456;;789¶X

Cria um quadro interno e também marca cada jogada com o jogador de quem é a jogada.

{`(.)(.*¶)(.)\1
$3$2

Aplica uma jogada.

}`.*(.)(.)*\1(?<-2>.)*(?(2)(?!))\1.*¶(..)*
$1$#3

Procura uma vitória e, se houver, substitua o tabuleiro pelo vencedor e pelo número de jogadas restantes.

.*¶
T

Se os movimentos estão esgotados e ninguém venceu, o jogo está empatado.

T`d`Rd

Calcule o número da rodada a partir do número de movimentos restantes.

Neil
fonte
4
Esta é uma das mais .... respostas voluptuosas que já vi aqui.
Lord Farquaad
6

MATL , 39 bytes

3:g&+XIx"IX@oXK@(XIt!yXdyPXd&hK=Aa?KX@.

Saída é

  • 1e R, em linhas separadas, se o usuário 1 vencer na rodada R ;
  • 0e R, em linhas separadas, se o usuário 2 vencer na rodada R ;
  • vazio se ninguém vencer.

Experimente online! Ou verifique todos os casos de teste .

Explicação

3:       % Push [1 2 3]
g        % Convert to logical. Gives [true true true]
&+       % Matrix of all pairs of additions. Gives a 3×3 matrix, which represents
         % the board in its initial state, namely all cells contain 2. This value
         % means "cell not used yet". 1 will represent "cell marked by user 1",
         % and 0 will represent "cell marked by user 2"
XI       % Copy into clipboard I
x        % Delete
"        % Implicit input: array with moves. For each move
  I      %   Push current board state
  X@     %   Push iteration index (starting at 1), that is, current round number
  o      %   Modulo 2: gives 1 or 0. This represents the current user
  XK     %   Copy into clipboard K
  @      %   Push current move ((that is, cell index)
  (      %   Write user identifier (1 or 0) into that cell. Cells are indexed
         %   linearly in column-major order. So the board is transposed compared
         %   to that in the challenge, but that is unimportant
  XI     %   Copy updated board into clipboard I
  t!     %   Duplicate and transpose
  y      %   Duplicate from below: push copy of board
  Xd     %   Extract main diagonal as a 3×1 vector
  y      %   Duplicate from below: push copy of transposed board
  PXd    %   Flip vertically and extract main diagonal. This is the anti-diagonal
         %   of the board
  &h     %   Concatenate stack horizontally. This concatenates the board (3×3),
         %   transposed board (3×3), main diagonal (3×1 vector) and anti-diagonal
         %   (3×1) into an 3×8 matrix
  K=     %   Push current user identifier. Test for equality with each entry of the
         %   3×8 matrix
  A      %   For each column, this gives true if all its entries are true. Note 
         %   that the first three columns in the 3×8 matrix are the board columns;
         %   the next three are the board rows; and the last two columns are the
         %   main diagonal and anti-diagonal. The result is a 1×8 vector
  a      %   True if any entry is true, meaning the current user has won
  ?      %   If true
    K    %     Push current user identifier
    X@   %     Push current round number
    .    %     Break for loop
         %   Implicit end
         % Implicit end
         % Implicit display
Luis Mendo
fonte
5

Javascript (ES6), 130 bytes

m=>m.reduce((l,n,i)=>l||(b[n-1]=p=i%2+1,"012,345,678,036,147,258,048,246".replace(/\d/g,m=>b[m]).match(""+p+p+p)&&[p,i+1]),0,b=[])

f=m=>m.reduce((l,n,i)=>l||(b[n-1]=p=i%2+1,"012,345,678,036,147,258,048,246".replace(/\d/g,m=>b[m]).match(""+p+p+p)&&[p,i+1]),0,b=[])
console.log(JSON.stringify(f([3,5,6,7,9,8,1,2,3])))
console.log(JSON.stringify(f([2,3,4,5,6,7,1,8,9])))
console.log(JSON.stringify(f([1,2,4,5,6,7,3,8,9])))
console.log(JSON.stringify(f([1,2,3,5,4,7,6,8,9])))

Explicação

m=>m.reduce((l,n,i)=>               // Reduce the input array with n as the current move
  l||(                              //  If there is already a winner, return it
  b[n-1]=p=i%2+1,                   //  Set the cell at b[n-1] to the current player p
  "012,345,678,036,147,258,048,246" //  For every digit in the list of possible rows:
    .replace(/\d/g,m=>b[m])         //   Replace it with the player at the cell
    .match(""+p+p+p)                //  If any of the rows is filled with p:
      &&[p,i+1]                     //   Return [p, current move]
),0,b=[])
Herman L
fonte
Você se importaria de fornecer uma explicação ou uma versão não destruída, por favor? Estou interessado em entender sua solução.
Jack
4

Java (OpenJDK 8) , 445 bytes

int[] t(int[]m){int[][]f=new int[3][3];boolean z=false;for(int i=0;i<9;i++){f[m[i]%3][m[i]/3]=z?2:1;if(f[m[i]%3][0]==(z?2:1)&&f[m[i]%3][1]==(z?2:1)&&f[m[i]%3][2]==(z?2:1)||f[0][m[i]/3]==(z?2:1)&&f[1][m[i]/3]==(z?2:1)&&f[2][m[i]/3]==(z?2:1)||m[i]%3+m[i]/3==2&&f[0][2]==(z?2:1)&&f[1][1]==(z?2:1)&&f[2][0]==(z?2:1)||m[i]%3==m[i]/3&&f[0][0]==(z?2:1)&&f[1][1]==(z?2:1)&&f[2][2]==(z?2:1)){return(new int[]{(z?2:1),++i});}z=!z;}return(new int[]{0,0});}

Experimente online!

O valor de retorno {1,8} significa que o jogador 1 venceu na rodada 8. O valor de retorno {0,0} significa empate.

Grunzwanzling
fonte
5
A menos que você remova todo o espaçamento desnecessário, esta resposta é considerada inválida devido à falta de esforço no golfe. Além disso, não é realmente recomendado responder a seu próprio desafio tão rapidamente, e você pode adicionar um link TIO para que possamos testar seu código.
Mr. Xcoder
Links de referência:
Contendor
Me desculpe, eu copiei a coisa errada. Na verdade, é bem mais curto
Grunzwanzling
Você pode ver as dicas para jogar golfe na questão Java para remover alguns bytes. Por exemplo, falsepode ser substituído por 1<0e o espaço após o primeiro ]pode ser removido.
precisa saber é o seguinte
442 bytes . Além disso, a razão pela qual a seção "Cabeçalho" e "Rodapé" existe no TIO é que você não precisa comentar //Code that was submittede //End of code.
precisa saber é o seguinte
2

Kotlin , 236 bytes

i.foldIndexed(l()to l()){o,(a,b),p->fun f(i:(Int)->Int)=b.groupBy(i).any{(_,v)->v.size>2}
if(f{(it-1)/3}|| f{it%3}|| listOf(l(1,5,9),l(3,5,7)).any{b.containsAll(it)}){return p%2+1 to o}
b to a+p}.let{null}
fun l(vararg l:Int)=l.toList()

Embelezado

    i.foldIndexed(l() to l()) { o, (a, b), p ->
        fun f(i: (Int) -> Int) = b.groupBy(i).any { (_, v) -> v.size > 2 }
        if (f { (it - 1) / 3 } || f { it % 3 } || listOf(l(1, 5, 9), l(3, 5, 7)).any { b.containsAll(it) }) {
            return p % 2 + 1 to o
        }
        b to a + p
    }.let { null }
fun l(vararg l:Int)= l.toList()

Teste

fun f(i: List<Int>): Pair<Int, Int>? =
i.foldIndexed(l()to l()){o,(a,b),p->fun f(i:(Int)->Int)=b.groupBy(i).any{(_,v)->v.size>2}
if(f{(it-1)/3}|| f{it%3}|| listOf(l(1,5,9),l(3,5,7)).any{b.containsAll(it)}){return p%2+1 to o}
b to a+p}.let{null}
fun l(vararg l:Int)=l.toList()

data class Test(val moves: List<Int>, val winner: Int, val move: Int)

val tests = listOf(
        Test(listOf(3, 5, 6, 7, 9, 8, 1, 2, 3), 1, 5),
        Test(listOf(2, 3, 4, 5, 6, 7, 1, 8, 9), 2, 6),
        Test(listOf(1, 2, 4, 5, 6, 7, 3, 8, 9), 2, 8),
        Test(listOf(1, 2, 3, 5, 4, 7, 6, 8, 9), 2, 8)
)

fun main(args: Array<String>) {
    tests.forEach { (input, winner, move) ->
        val result = f(input)
        if (result != winner to move) {
            throw AssertionError("$input ${winner to move} $result")
        }
    }
}

TIO

TryItOnline

jrtapsell
fonte
1

Python 2 , 170 bytes

q=map(input().index,range(1,10))
z=zip(*[iter(q)]*3)
o='',
for l in[q[2:7:2],q[::4]]+z+zip(*z):
 r=[n%2for n in l];y=all(r)*2+1-any(r)
 if y:o+=[max(l)+1,y],
print min(o)

Experimente online! ou Experimente todos os casos de teste

#swap cell number / turn
q=map(input().index,range(1,10))
#split in 3 parts (rows)
z=zip(*[iter(q)]*3)
#starting value for the list with the results
#since string are "greater" than lists, this will
#be the output value when there is a draw
o='',
#iterate over diagonals, rows and columns
for l in[q[2:7:2],q[::4]]+z+zip(*z):
 #use %2 to separate between player 1 and 2
 r=[n%2 for n in l]
 #store in y the value of the player if the trio is a valid win, 0 otherwise
 #it's a win if all moves are from the same player
 y=all(r)*2+1-any(r)
 #if y has a valid player, add the highest turn of the trio, and the player to o
 if y:o+=[max(l)+1,y],
#output the smaller turn of the valid winning trios
print min(o)
Cajado
fonte
1

Gelatina , 38 bytes

;⁵s2ZṬḤ2¦SṖs3µ,ṚJị"$€;;ZEÐfṀḢµ$ƤµTḢ,ị¥

Experimente online!

Vitória do Jogador 1: Vitória do [round, 1]
Jogador 2: [round, 2]
Gravata:[0, 0]

Erik, o Outgolfer
fonte
1

Python 3.6 ou superior, 137 bytes

n=m=c=z=0
for a in input():m+=1<<~-int(a);c+=1;z=z or f'{c&1}:{c}'*any(m&t==t for t in[7,56,448,73,146,292,273,84]);n,m=m,n
print(z or-1)

O formato de saída é winner number:roundou -1para um empate. Jogador 2 é 0Jogador 1 é 1. Entrada na forma de uma sequência não eliminada de números quadrados indexados em 1.

mypetlion
fonte
1

Geléia , 35 bytes

9s3,ZU$$;ŒD$€Ẏf€⁸L€3e
s2ZÇƤ€ZFTḢ;Ḃ$

Um link monádico que pega uma lista dos movimentos e retorna uma lista, [move, player]onde os jogadores são identificados como 1(primeiro a agir) e 0(segundo a agir).

Experimente online!

Quão?

9s3,ZU$$;ŒD$€Ẏf€⁸L€3e - Link 1: any winning play?: list of player's moves:
9s3                   - (range of) nine split into threes = [[1,2,3],[4,5,6],[7,8,9]]
       $              - last two links as a monad:
      $               -   last two links as a monad:
    Z                 -     transpose = [[1,4,7],[2,5,8],[3,6,9]]
     U                -     upend     = [[7,4,1],[8,5,2],[9,6,3]]
   ,                  -  pair = [[[1,2,3],[4,5,6],[7,8,9]],[[7,4,1],[8,5,2],[9,6,3]]]
           $€         - last two links as a monad for €ach:
         ŒD           -   diagonals = [[1,5,9],[2,6],[3],[7],[4,8]] or [[7,5,3],[4,2],[1],[9],[8,6]]
        ;             -  concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,5,9],[2,6],[3],[7],[4,8]] or [[7,4,1],[8,5,2],[9,6,3],[7,5,3],[4,2],[1],[9],[8,6]]
             Ẏ        - tighten = [[1,2,3],[4,5,6],[7,8,9],[1,5,9],[2,6],[3],[7],[4,8],[7,4,1],[8,5,2],[9,6,3],[7,5,3],[4,2],[1],[9],[8,6]]
                      -    i.e.:    row1    row2    row3    diag\   x     x   x   x     col1    col2    col3    diag/   x     x   x   x
                      -    where x's are not long enough to matter for the rest...
                ⁸     - chain's left argument, list of player's moves
              f€      - filter to keep those moves for €ach of those lists to the left
                 L€   - length of €ach result
                   3e - 3 exists in that? (i.e. were any length 3 when filtered down to only moves made?)

s2ZÇƤ€ZFTḢ;Ḃ$ - Main link: list of the moves  e.g. [2,3,4,5,6,7,1,8,9]
s2            - split into twos                    [[2,3],[4,5],[6,7],[1,8],[9]]
  Z           - transpose                          [[2,4,6,1,9],[3,5,7,8]]
    Ƥ€        - for Ƥrefixes of €ach:
   Ç          -   call last link (1) as a monad     [0,0,0,0,0] [0,0,1,1]
      Z       - transpose                          [[0,0],[0,0],[0,1],[0,1],[0]]
       F      - flatten                            [0,0,0,0,0,1,0,1,0]
        T     - truthy indices                     [          6   8  ]
         Ḣ    - head (if empty yields 0)           6
            $ - last two links as a monad:
           Ḃ  -   modulo by 2 (evens are player 2) 0
          ;   -   concatenate                      [6,0]
Jonathan Allan
fonte
0

Python 2, 168 bytes

import itertools as z
f=lambda g:next(([i%2+1,i+1]for i in range(9) if any(c for c in z.combinations([[0,6,1,8,7,5,3,2,9,4][j]for j in g[i%2:i+1:2]],3)if sum(c)==15)),0)

Saídas (jogador, rodada) ou 0 para um empate.

Mapeia o jogo em um quadrado mágico de 3 por 3 e procura conjuntos de 3 Os ou Xs que somam 15.

aPaulT
fonte
0

Limpo , 244 ... 220 bytes

import StdEnv
f[a,b]i#k= \l=or[and[isMember(c+n)(take i l)\\c<-:"123147159357"%(j,j+2)]\\j<-[0,3..9]&h<-:"\0\0",n<-[h-h,h,h+h]]
|k a=(1,i*2-1)|i>4=(0,0)|k b=(2,i*2)=f[a,b](i+1)
@l=f(map(map((!!)l))[[0,2..8],[1,3..7]])1

Experimente online!

A sequência iterada em hcontém não-imprimíveis e é equivalente a "\003\001\000\000".

Furioso
fonte
0

Python 2 , 140 136 134 bytes

lambda a,i=0:i<9and(any(set(a[i%2:i+1:2])>=set(map(int,t))for t in'123 456 789 147 258 369 159 357'.split())and(i%2+1,i+1)or f(a,i+1))

Experimente online!

EDIT: 4 bytes + 2 bytes thx para Eric, o Outgolfer.

Produz uma tupla (playerNumber, roundNumber) ou False, se não houver vencedor.

Chas Brown
fonte
134 bytes
Erik the Outgolfer
@Erik - Sim, eu já deveria ter feito isso; mas estou lutando contra a gripe e meus olhos estavam doendo :). THX!
Chas Brown
Bem, fique bom logo. :)
Erik the Outgolfer