26
\$\begingroup\$

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
\$\endgroup\$
  • 11
    \$\begingroup\$ Welcome to PPCG! This is a nice first post, but usually we do not like very restrictive input / output formats. Would you consider removing the "Player X wins in round Y" and let us output in any reasonable format, like a list [X, Y]? In case of a tie, can we output any other consistent value instead? I recommend so, because printing those exact strings aren't really part of golfing. For future challenge ideas, I recommend using the sandbox. :-) \$\endgroup\$ – Mr. Xcoder Jan 9 '18 at 10:17
  • \$\begingroup\$ Sorry, my bad. I think it is correct now. \$\endgroup\$ – Grunzwanzling Jan 9 '18 at 13:16
  • \$\begingroup\$ Read the challenge to the end, I say that there may be a draw and that you can output something of your choice when it happens. I return {2,6} when player 2 wins in round 6 and {0,0} when no one wins. \$\endgroup\$ – Grunzwanzling Jan 9 '18 at 13:18
  • \$\begingroup\$ Can we use 0-indexed everything? (cells, players, rounds) \$\endgroup\$ – Arnauld Jan 9 '18 at 21:56
  • 1
    \$\begingroup\$ "You get an array of exactly 9 moves like that: {3, 5, 6, 7, 9, 8, 1, 2, 3}" - should 3 really appear twice? \$\endgroup\$ – Jonathan Allan Jan 9 '18 at 22:09

12 Answers 12

8
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ This is one of the more.... voluptuous answers I've seen here. \$\endgroup\$ – Lord Farquaad Jan 9 '18 at 21:41
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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=[])
\$\endgroup\$
  • \$\begingroup\$ Would you mind providing an explanation or an ungolfed version please? I'm interested in understanding your solution. \$\endgroup\$ – Jack Jan 10 '18 at 0:53
4
\$\begingroup\$

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ Unless you remove all the unnecessary spacing, this answer is considered invalid due to the lack of golfing effort. Moreover, it is not really recommended to answer your own challenge that fast, and you might want to add a TIO link such that we can test your code. \$\endgroup\$ – Mr. Xcoder Jan 9 '18 at 11:06
  • \$\begingroup\$ Reference links: Serious contender, compete in your own challenge \$\endgroup\$ – user202729 Jan 9 '18 at 11:16
  • \$\begingroup\$ I am sorry, I copied the wrong thing. It is in fact way shorter \$\endgroup\$ – Grunzwanzling Jan 9 '18 at 11:29
  • \$\begingroup\$ You can see the tips for golfing in Java question to remove some bytes. For example false can be replaced by 1<0, and the space after the first ] can be removed. \$\endgroup\$ – user202729 Jan 9 '18 at 11:50
  • \$\begingroup\$ 442 bytes. Also the reason why the "Header" and "Footer" section exists on TIO is that you don't need to comment //Code that was submitted and //End of code. \$\endgroup\$ – user202729 Jan 9 '18 at 11:52
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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]

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 134 bytes \$\endgroup\$ – Erik the Outgolfer Jan 11 '18 at 13:43
  • \$\begingroup\$ @Erik - Yah, I should have done that already; but I'm fighting the flu and my eyes were hurting :). Thx! \$\endgroup\$ – Chas Brown Jan 12 '18 at 2:04
  • \$\begingroup\$ Well, get well soon. :) \$\endgroup\$ – Erik the Outgolfer Jan 12 '18 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.