Determine Tic-Tac-Toe winner (round based)

Question

Let's play some code-golf!

The challenge is to find the winner of a game of Tic-Tac-Toe.

This has been done many times by giving a board that has one clear winner but here is the twist:

The cells are numbered like this:

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

You get an array of exactly 9 moves like that:

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

This is parsed as follows:

• Player 1 marks cell 3
• Player 2 marks cell 5
• Player 1 marks cell 6
• Player 2 marks cell 7
• Player 1 marks cell 9
• Player 1 has won

Note: The game does not stop after one player has won, it may happen that the losing player manages to get three in a row after the winning player, but only the first win counts.

Your job is now to get 9 numbers as input and output the winning player and the round in which the win occured. If no one wins, output something constant of your choice. You can receive input and provide output through any standard mean / format.

Have fun!

Some more examples as requested:

{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

Answer 1

Retina, 114 bytes

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

Try it online! Based on my answer to Tic-Tac-Toe - X or O?. Outputs X<N> if the first player wins after N turns, O<N> if the second player wins, T if neither wins. Explanation:

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

Creates an internal board, and also marks each move with the player whose move it is.

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

Applies a move.

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

Searches for a win, and if one is found, then replace the board with the winner and the number of remaining moves.

.*¶
T

If the moves are exhausted and nobody has won then the game is a tie.

T`d`Rd

Calculate the number of the round from the number of remaining moves.

Answer 2

MATL, 39 bytes

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

Output is

• 1 and R, in separate lines, if user 1 wins in round R;
• 0 and R, in separate lines, if user 2 wins in round R;
• empty if no one wins.

Try it online! Or verify all test cases.

Explanation

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

Answer 3

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

Explanation

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

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

Try it online!

Return value {1,8} means that player 1 won in round 8. Return value {0,0} means draw.

Answer 5

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

Beautified

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

Test

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

Answer 6

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)

Try it online! or Try all test cases

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

Answer 7

Jelly, 38 bytes

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

Try it online!

Player 1 win: [round, 1]
Player 2 win: [round, 2]
Tie: [0, 0]

Answer 8

Python 3.6+, 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)

Output format is winner number:round or -1 for a tie. Player 2 is 0 Player 1 is 1. Input in the form of a undeliminated string of 1-indexed square numbers.

Answer 9

Jelly, 35 bytes

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

A monadic link taking a list of the moves and returning a list, [move, player] where the players are identified as 1 (first to act) and 0 (second to act).

Try it online!

How?

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]

Answer 10

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)

Outputs (player,round) or 0 for a tie.

Maps the game onto a 3-by-3 magic square and looks for sets of 3 Os or Xs that sum to 15.

Answer 11

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

Try it online!

The string iterated into h contains nonprintables, and is equivalent to "\003\001\000\000".

Answer 12

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

Try it online!

EDIT: 4 bytes + 2 bytes thx to Eric the Outgolfer.

Outputs a tuple (playerNumber, roundNumber) or False if there is no winner.