14
\$\begingroup\$

Background

Skip to "Task" if you are familiar with Tic-Tac-Toe (I think most are!)

Tic-Tac-Toe is a famous two-player game. It consists of a 3x3 board that is filled gradually by two players (clarifications below); The first player uses the character X and the other one uses O. The winner is the first to get 3 consecutive and identical characters (X or O), either horizontally, vertically or diagonally. In case the board is filled and none of the players managed to get three consecutive characters as decribed above, the game ends in a tie. Note that there might be empty spots at the end of the game, in case either of the players wins in less than 9 moves in total (this cannot happen in case of a tie).

Task

Given a Tic-Tac-Toe board at the end of a game (in the form of a string, a matrix, a flat list of 9 ordered values, any other decent format), determine who wins the game.

  • The input will consist of distinct and consistent values, one for X, one for O and another one that represents an empty spot.

  • Your program should be able to output 3 distinct, consistent and non-empty values: one in case X wins, another one in case O wins or another if the players are tied.

    Please specify these values in your answer. You can assume that the input will be a valid Tic-Tac-Toe board.

Test Cases

X, O, _ are the input values here; X wins, O wins and Tie are for the output.

X O X
O X _
O _ X

Output: X wins.

X _ O
X O _
X O X

Output: X wins.

X O X
_ O X
_ O _

Output: O wins.

X O X
O O X
X X O

Output: Tie.


As usual, all our standard rules apply. This is , the shortest code in bytes in every language wins!

\$\endgroup\$
  • 2
    \$\begingroup\$ Get out of my brain! Literally just had an idea for a Noughts & Crosses challenge that I was gonna Sanbox on Monday. Then I crack open the site and see this! \$\endgroup\$ – Shaggy Sep 30 '17 at 17:58
  • 1
    \$\begingroup\$ @Shaggy To cite someone from the "Fast and Furious" series: Too slow! ;p \$\endgroup\$ – Mr. Xcoder Sep 30 '17 at 18:00
  • \$\begingroup\$ It's OK, my idea was for a playable version, assuming that hasn't been done already. \$\endgroup\$ – Shaggy Sep 30 '17 at 18:01
  • 4
    \$\begingroup\$ @Laikoni I don't think it's a dupe, since this has way more flexible input and output and also has empty boxes too, and this also lets you assume the input is a valid board. \$\endgroup\$ – Erik the Outgolfer Sep 30 '17 at 18:16
  • 1
    \$\begingroup\$ @Joshua That’s about making a Tic-tac-toe game. This is about grading one. \$\endgroup\$ – DonielF Oct 1 '17 at 3:57

15 Answers 15

6
\$\begingroup\$

Jelly,  16 15  14 bytes

U,Z;ŒD$€ẎḄỊÐḟḢ

A monadic link accepting a list of lists (the rows - or columns) with the values:

X = 0.155; O = -0.155; _ = 0

Returning results:

X wins = 1.085; O wins = -1.085; Tie = 0

Note: using a value of zero for _, and equal but opposite values for X and O, this value (here 0.155) may be in the range (1/6, 1/7) (exclusive at both ends) - I only chose a value in that range that gave a precisely representable floating point result for the win cases.

Try it online!

How?

U,Z;ŒD$€ẎḄỊÐḟḢ - Link: list of lists (as described above)
U              - upend (reverse each row)
  Z            - transpose (get the columns)
 ,             - pair the two
      $€       - last two links as a monad for each of them:
    ŒD         -   diagonals (leading diagonals - notes: 1. only one is of length 3;
               -              2. the upend means we get the anti-diagonals too)
        Ẏ      - tighten (make a single list of all the rows, columns and diagonals)
         Ḅ     - from binary (vectorises) (note that [0.155, 0.155, 0.155]
               -                           converts to 4*0.155+2*0.155+1*0.155 = 1.085
               -                           and [-0.155, -0.155, -0.155]
               -                           converts to 4*-0.155+2*-0.155+1*-0.155 = -1.085
               -                           while shorter lists or those of length three
               -                           with any other mixtures of 0.155, -0.155 and 0
               -                           yield results between -1 and 1
               -                           e.g. [.155,.155,0] -> 0.93)
           Ðḟ  - filter discard if:
          Ị    -   insignificant (if abs(z) <= 1) (discards all non-winning results)
             Ḣ - head (yields the first value from the list or zero if it's empty)
\$\endgroup\$
  • \$\begingroup\$ Yes, I think any esoteric language answers should have an explanation (and I like to see explanations for normal languages too!) \$\endgroup\$ – Jonathan Allan Sep 30 '17 at 20:00
  • \$\begingroup\$ Thanks for adding it! Very good approach, way more clever than what I've though of... Nice \$\endgroup\$ – Mr. Xcoder Sep 30 '17 at 20:01
6
\$\begingroup\$

Javascript (ES6), 103 87 bytes

a=>"012+345+678+036+147+258+048+246T".replace(/\d/g,n=>a[n]||!1).match(/(\d)\1\1|T/)[0]

Input

  • X is represented as 1
  • O is represented as 2
  • _ is represented as 0

Output

  • X wins is represented as "111"
  • O wins is represented as "000"
  • Tie is represented as "T"

Explanation

a=>
    "012+345+678+036+147+258+048+246" // List of indexes for each row
    .replace(/\d/g,n=>a[n]||!1)       // Replace all digits with the value of the cell
    .match(/(\d)\1\1|$/)[0]           // Find the first row filled with the same value

Test cases

f=
a=>"012+345+678+036+147+258+048+246T".replace(/\d/g,n=>a[n]||!1).match(/(\d)\1\1|T/)[0]
console.log(f([1,2,1,2,1,0,2,0,1]))
console.log(f([1,0,2,1,2,0,1,2,1]))
console.log(f([1,2,1,0,2,1,0,2,0]))
console.log(f([1,2,1,2,2,1,1,1,2]))

\$\endgroup\$
  • \$\begingroup\$ "Your program should be able to output 3 distinct, consistent and non-empty values", so you can't output empty string for tie. \$\endgroup\$ – RedClover Oct 2 '17 at 16:37
  • 1
    \$\begingroup\$ @Soaku My bad, I missed that part of the rules. \$\endgroup\$ – Herman L Oct 2 '17 at 16:57
4
\$\begingroup\$

Jelly, 18 bytes

UŒD;;Z;ŒDµSA⁼3µÐfḢ

Try it online!

X = 1, O = -1, _ = 0
X wins = [1, 1, 1], O wins = [-1, -1, -1], Tie = 0
Input as list of 3 lists of 3 elements in (1, -1, 0) each.

\$\endgroup\$
  • \$\begingroup\$ Wow Nice... When you are done golfing, please add the I/O values and an explanation :-) \$\endgroup\$ – Mr. Xcoder Sep 30 '17 at 16:59
  • \$\begingroup\$ Here is a similar approach with a slightly shorter test. Takes X=1, O=2, _=3, returns 1 (X wins), 2 (O wins) or 3 (tie). \$\endgroup\$ – Arnauld Sep 30 '17 at 22:29
  • \$\begingroup\$ @Arnauld thanks for the shortening \$\endgroup\$ – Erik the Outgolfer Sep 30 '17 at 22:32
3
\$\begingroup\$

Python 3, 73 bytes

lambda b:{'XXX','OOO'}&{*b.split(),b[::4],b[1::4],b[2::4],b[::5],b[2::3]}

Try it online!


Python 2, 100 95 92 87 82 77 bytes

lambda b:{'XXX','OOO'}&set(b.split()+[b[::4],b[1::4],b[2::4],b[::5],b[2::3]])

Try it online!


Takes input as a newline separated string of XO_

Outputs:

  • {'XXX'} for X,
  • {'OOO'} for O
  • {} for a tie

Works by slicing the string into rows columns and diagonals:

The board:
    1 2 3
    4 5 6
    7 8 9
which is '123\n456\n789' is sliced into:

['123', '456', '789', '147', '258', '369', '159', '357']
rows: b.split() -> ['123', '456', '789']
cols: [b[::4],b[1::4],b[2::4]] -> ['147', '258', '369']
diag: [b[::5],b[2::3]] -> ['159', '357']

then 'XXX' and 'OOO' are checked against the slices.

Takes input as a newline separated string of XO_

Outputs:

  • {'XXX'} for X,
  • {'OOO'} for O
  • {} for a tie

Works by slicing the string into rows columns and diagonals:

The board:
    1 2 3
    4 5 6
    7 8 9
which is '123\n456\n789' is sliced into:

['123', '456', '789', '147', '258', '369', '159', '357']
rows: b.split() -> ['123', '456', '789']
cols: [b[::4],b[1::4],b[2::4]] -> ['147', '258', '369']
diag: [b[::5],b[2::3]] -> ['159', '357']

then 'XXX' and 'OOO' are checked against the slices.

\$\endgroup\$
  • \$\begingroup\$ Python slicing FTW Anyways, 81 bytes, should work, I think. \$\endgroup\$ – totallyhuman Oct 2 '17 at 9:25
  • \$\begingroup\$ @icrieverytim [2::2] slices to 3579, while [2:8:2] gives 357 \$\endgroup\$ – TFeld Oct 2 '17 at 10:06
  • \$\begingroup\$ Python 3, 73 bytes. \$\endgroup\$ – Jonathan Frech Oct 2 '17 at 10:57
3
\$\begingroup\$

R, 118 116 115 bytes

Thanks to @user2390246 for two extra bytes.

function(M,b=table,u=unlist(c(apply(M,1,b),apply(M,2,b),b(diag(M)),b(M[2*1:3+1]))))`if`(any(u>2),names(u[u>2]),"T")

Slightly ungolfed:

function(M){
    u=unlist(c(apply(M,1,table), #Contingency table of the rows
             apply(M,2,table), #of the columns
             table(diag(M)), #of the diagonal
             table(M[2*1:3+1]))) #of the opposite diagonal
    `if`(any(u>2),names(u[u>2]),"T") #Give name of element that occurs more than twice in any setting
 }

Returns X if X wins, O if O wins and T in case of a tie.

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ M[c(3,5,7)] is shorter for the opposite diagonal \$\endgroup\$ – user2390246 Oct 2 '17 at 10:54
3
\$\begingroup\$

Perl 5, 58 bytes

56 bytes code + 2 fpr -p0.

$_=eval sprintf'/(.)(.{%s}\1){2}/s||'x4 .'0?$1:T',0,2..4

Try it online!

Outputs X and O for wins, or T for a tie. Includes a bunch of header/footer code to test all at once.


Alternative, 58 bytes

$}.="/(.)(.{$_}\\1){2}/s||"for 0,2..4;$_=eval$}.'0?$1:T'

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 124 118 117 115 bytes

  • Saved six bytes thanks to Erik the Outgolfer; using a string to avoid commata.
  • Saved one byte thanks to Mr. Xcoder; golfing [j*3:j*3+3] to [j*3:][:3].
  • Saved two bytes by using a magic number to compress the string.
def T(B):
 for j in range(8):
	a,b,c=map(int,`0x197bf3c88b2586f4bef6`[j*3:][:3])
	if B[a]==B[b]==B[c]>0:return B[a]

Try it online!

Input / Output values

  • X is represented as 1
  • O is represented as 2
  • _ is represented as None
\$\endgroup\$
  • \$\begingroup\$ [8,0,3,6,1,4,7,2,5,8,0,4,8,2,4,6] -> map(int,'8036147258048246') \$\endgroup\$ – Erik the Outgolfer Sep 30 '17 at 17:34
  • \$\begingroup\$ @EriktheOutgolfer Thanks. I was trying to golf the integer list by using map(ord,"..."), though a nul byte in the middle of a string did not work out... \$\endgroup\$ – Jonathan Frech Sep 30 '17 at 17:42
  • \$\begingroup\$ 117 bytes. [j*3:j*3+3] is [j*3:][:3]. As a side note, j*3+3 is the same as -~j*3, but that is 118 bytes too. \$\endgroup\$ – Mr. Xcoder Sep 30 '17 at 17:43
  • \$\begingroup\$ @JonathanFrech You seem to have an extra 01234567... \$\endgroup\$ – Erik the Outgolfer Sep 30 '17 at 17:45
  • 1
    \$\begingroup\$ @Mr.Xcoder Thanks. Learnt a new slicing golf today. \$\endgroup\$ – Jonathan Frech Sep 30 '17 at 17:55
2
\$\begingroup\$

Python 3, 173 bytes

lambda x:h(x,1)*2or+h(x,0)
h=lambda x,y:g(x,y)or g(zip(*x),y)or x[0][0]==x[1][1]==x[2][2]==y or x[0][2]==x[1][1]==x[2][0]==y
g=lambda x,y:any(all(e==y for e in r)for r in x)

Try it online!

  • Input as a matrix of 1 == X, 0 == O, -1 == _

  • Output as a single value: 2 == X, 1 == O, 0 == TIE

-8 bytes thanks to Erik the Outgolfer

\$\endgroup\$
  • \$\begingroup\$ You can replace the first line with lambda x:h(x,1)*2or+h(x,0) for -8 bytes and 0 == TIE (which is prettier imo). \$\endgroup\$ – Erik the Outgolfer Sep 30 '17 at 17:40
  • \$\begingroup\$ @EriktheOutgolfer cool, thanks \$\endgroup\$ – HyperNeutrino Oct 1 '17 at 3:19
2
\$\begingroup\$

PHP, 70 bytes

for($c=95024101938;${${$i++&7}.=$argn[$c%9]}=1<$c/=3;);echo$XXX-$OOO;

Assumes -n (interpreter defaults). Additionally requires -R (execute <code> for every line of input), counted as one.

Input is taken on a single line (exactly as in the problem description, except with all whitespace removed).

Output is the following: 1 → X Wins, -1 → O Wins, 0 → Tie .

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You do not need to have the whole strings, you can choose your output values. 'X Wins' can be changed to 'X' (or even an integer -- say 1). The same applies to 'O wins' and Tie. That being said, 109 bytes. \$\endgroup\$ – Mr. Xcoder Oct 1 '17 at 17:18
  • \$\begingroup\$ @Mr.Xcoder thanks for the clarification. \$\endgroup\$ – primo Oct 1 '17 at 17:22
1
\$\begingroup\$

Retina, 49 bytes

;
;;
.*(\w)(.)*\1(?<-2>.)*(?(2)(?!))\1.*
$1
..+
T

Try it online! Takes input as an 11-character string of 9 Xs, Os or -s in three groups of three separated by ;s, although the link includes a header which translates the given test cases to this format. Works by matching a winning line directly using a balancing group to ensure that the three matching characters are equidistant. (Suitable distances are 0 (horizontal line), 4 (reverse diagonal), 5 (vertical line), or 6 (diagonal); other distances would hit a ; or extend outside the string.)

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

Java 8, 112 108 106 104 90 102 93 bytes

b->b.replaceAll(".*(X|O)(\\1|...\\1...|.{4}\\1.{4}|..\\1..)\\1.*","$1").replaceAll("..+","T")

+12 bytes (90 → 102) due to bug-fix of only checking one diagonal instead of both..
-9 bytes (102 → 93) by using replaceAll instead of matches.

Input in the format XOX OX_ O_X, output X, O or T.

Explanation:

Try it here.

b->{                   // Method with String as both parameter and return-type
  b.replaceAll(".*(X|O)(\\1|...\\1...|.{4}\\1.{4}|..\\1..)\\1.*",
                       //  If we found a line of X or O:
     "$1")             //   Replace it with either X or O
   .replaceAll("..+",  //  If there are now more than 2 characters left:
     "T")              //   Replace it with T
                       // End of method (implicit / single-line return-statement)

Explanation regex:

.*(X|O)(\1|...\1...|.{4}\1.{4}|..\1..)\1.*
.*                                      .*# 0 or more trailing & leading chars
  (X|O)                               \1  # X or O next to those leading/trailing chars
       (\1                                # A single X or O in between (row found)
          |...\1...                       # 3 chars, X or O, 3 chars (column found)
                   |.{4}\1.{4}            # 4 chars, X or O, 4 chars (diagonal TL→BR found)
                              |..\1..)    # 2 chars, X or O, 2 chars (diagonal TR→BL found)
\$\endgroup\$
0
\$\begingroup\$

Retina, 127 bytes

.*(X|O)\1\1.*
$1
(X|O).. \1.. \1..
$1
.(X|O). .\1. .\1.
$1
..(X|O) ..\1 ..\1
$1
(X|O).. .\1. ..\1
$1
..(X|O) .\1. \1..
$1
..+
_

Try it online!

...I guess you could call this brute force... Thought there might be some merit to it...

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

Retina, 51 bytes

.*(X|O)(\1|...\1...|.{4}\1.{4}|..\1..)\1.*
$1
..+
T

Port of my Java 8 answer. Input in the format XOX OX_ O_X, output X, O or T.

Explanation:

Try it here.

.*(X|O)(\1|...\1...|.{4}\1.{4}|..\1..)\1.*
.*                                      .*# 0 or more trailing & leading chars
  (X|O)                               \1  # X or O next to those leading/trailing chars
       (\1                                # A single X or O in between (row found)
          |...\1...                       # 3 chars, X or O, 3 chars (column found)
                   |.{4}\1.{4}            # 4 chars, X or O, 4 chars (diagonal TL→BR found)
                              |..\1..)    # 2 chars, X or O, 2 chars (diagonal TR→BL found)

$1                                        #  Replace match of above with either X or O

..+                                       # If there are now 2 or more characters left:
T                                         #  Replace everything with T
\$\endgroup\$
0
\$\begingroup\$

J, 34 bytes

[:>./[:+./"1(2 1 0},:0 1 2}),(,|:)

Ungolfed:

[: >./ [: +./"1 (2 1 0} ,: 0 1 2}) , (, |:)

Explanation

Encoding:

X = 2
O = 3
_ = 1

Our high-level strategy is first to create a matrix each of whose rows is a possible win. Row one is diagonal /, row 2 is diagonal \, the next three rows are the rows, and the final three rows are the columns. This part is accomplished by the phrase (using Item Amend }):

(2 1 0},:0 1 2}),(,|:)

Finally we take the GCD of each row:

+./"1

Thanks to our encoding, any row with a blank will have a GCD of 1, as will any row that contains any mix of Xs and Os, because 2 and 3 are coprime. So all we need to do next is find the maximum element: >./

If the game is a tie, it will be 1. If a player wins, it will be that player's number.

Try it online!

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

JavaScript, 66 bytes

([a,b,c,d,e,f,g,h,i])=>e&(a&i|c&g|b&h|d&f)|a&(b&c|d&g)|i&(c&f|g&h)

Keeping it simple.

  • Input: A string, or array of numbers or strings, with 0 corresponding to a blank space, 1 an X, and 2 an O.
  • Output: 0 for a tie, 1 for X victory, 2 for O victory.

Expanded, lightly commented:

( [a,b,c,d,e,f,g,h,i] ) => // Break apart the input into nine variables w/ destructuring
  // Run through all possible win conditions. 1&1&1 -> 1, 2&2&2 -> 2
  e & (             // All victories involving the middle square
    a & i | c & g | // Diagonal lines
    b & h | d & f   // Vertical/horizontal through the middle
  ) | 
  a & ( b & c | d & g ) | // Victories with the top-left square
  i & ( c & f | g & h )   // Victories with the bottom-right square
\$\endgroup\$

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.