Page Contents
Codechef Tic Tac Toe TCTCTOE Solution
Tic-tac-toe is a game played between two players on a 3×33×3 grid. In a turn, a player chooses an empty cell and places their symbol on the cell. The players take alternating turns, where the player with the first turn uses the symbol XX and the other player uses the symbol OO. The game continues until there is a row, column, or diagonal containing three of the same symbol (XX or OO), and the player with that token is declared the winner. Otherwise if every cell of the grid contains a symbol and nobody won, then the game ends and it is considered a draw.
You are given a tic-tac-toe board AA after a certain number of moves, consisting of symbols OO, XX, and underscore(__). Underscore signifies an empty cell.
- 11: if the position is reachable, and the game has drawn or one of the players won.
- 22: if the position is reachable, and the game will continue for at least one more move.
- 33: if the position is not reachable.
Note:
- Starting from an empty board, reachable position means that the grid is possible after a finite number of moves in the game where the players may or may not be playing optimally.
- The answer for each testcase should be with respect to the present position and independent of the results in the further successive moves.
Input
- The first line contains an integer TT, the number of test cases. Then the test cases follow.
- Each test case contains 33 lines of input where each line contains a string describing the state of the game in ithith row.
Output
For each test case, output in a single line 11, 22 or 33 as described in the problem.
Constraints
- 1≤T≤391≤T≤39
- Aij∈{X,O,_}Aij∈{X,O,_}
Subtasks
Subtask #1 (100 points): Original Constraints
Sample Input 1
3 XOX XXO O_O X X X OOO ___ XOX OX_ XO_
Sample Output 1
2 3 1
Explanation
Test Case 11: The board is reachable, and although no player can win from this position, still the game continues.
Test Case 22: There can’t be multiple winners in the game.
Test Case 33: The first player is clearly a winner with one of the diagonals.
Solution
Program: Tic Tac Toe TCTCTOE Solution in C++
#include<bits/stdc++.h> using namespace std; #define int long long // #define m 1000000007 signed main() { int t; cin>>t; while(t--) { char a1[3][3]; int x=0,o=0,c=0,a=0,b=0; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { cin>>a1[i][j]; if(a1[i][j] == 'X')x++; if(a1[i][j] == 'O')o++; if(a1[i][j] == '_')c++; } } for(int i=0;i<3;i++) { if(a1[i][0] == a1[i][1] && a1[i][1] == a1[i][2]) { if(a1[i][0] == 'X')a++; else if(a1[i][0] == 'O')b++; } } for(int i=0;i<3;i++) { if(a1[0][i] == a1[1][i] && a1[1][i] == a1[2][i]) { if(a1[0][i] == 'X')a++; else if(a1[0][i] == 'O')b++; } } if(a1[0][0] == a1[1][1] && a1[1][1] == a1[2][2]) { if(a1[0][0] == 'X')a++; else if (a1[0][0] == 'O')b++; } if(a1[0][2] == a1[1][1] && a1[1][1] == a1[2][0]) { if(a1[0][2] == 'X')a++; else if (a1[0][2] == 'O')b++; } if(o>x) { cout<<3<<endl; } else if(x-o>1) { cout<<3<<endl; } else if(x > o && a==1 && b == 0) { cout<<1<<endl; } else if(o == x && a ==0 && b== 1) { cout<<1<<endl; } else if(c==0&& a == 0 && b == 0 ) { cout<<1<<endl; } else if(c == 0 && b == 0 && a == 2) { cout<<1<<endl; } else if(c>0 && a == 0 && b == 0) { cout<<2<<endl; } else { cout<<3<<endl; } } }
Program: Tic Tac Toe TCTCTOE Solution in Java
import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Codechef{ public static void main (String[] args) throws java.lang.Exception{ Scanner sc=new Scanner(System.in); try{ int testCase = sc.nextInt(); while(testCase-- > 0){ String[] board=new String[3]; board[0]=sc.next(); board[1]=sc.next(); board[2]=sc.next(); String boardStr = board[0]+board[1]+board[2]; char[] characters = boardStr.toCharArray(); System.out.println(checkCond(characters)); } } catch(Exception e){} } public static int solution(char[] board, char ch){ if ((board[0] == ch)&&(board[0] == board[1])&&(board[0] == board[2])) return 1; // for 0 1 2 if ((board[0] == ch)&&(board[0] == board[3])&&(board[0] == board[6])) return 1; // for 0 3 6 if ((board[0] == ch)&&(board[0] == board[4])&&(board[0] == board[8])) return 1; // for 0 4 8 if ((board[1] == ch)&&(board[1] == board[4])&&(board[1] == board[7])) return 1; // for 1 4 7 if ((board[2] == ch)&&(board[2] == board[4])&&(board[2] == board[6])) return 1; // for 2 4 6 if ((board[2] == ch)&&(board[2] == board[5])&&(board[2] == board[8])) return 1; // for 2 5 8 if ((board[3] == ch)&&(board[3] == board[4])&&(board[3] == board[5])) return 1; // for 3 4 5 if ((board[6] == ch)&&(board[6] == board[7])&&(board[6] == board[8])) return 1; // for 6 7 8 return 0; } public static int checkCond(char[] characters){ int countX=0, countO=0; for (char ch:characters) { if (ch == 'X') countX++; if (ch == 'O') countO++; } int count_ = 9 - (countX+countO); if (countX < countO){ return 3; } if (countX > countO+1){ return 3; } int winX = solution(characters, 'X'); int winO = solution(characters, 'O'); if (winX == 1 && winO == 1){ return 3; } if (winX == 1 && countX == countO){ return 3; } if (winO == 1 && countX > countO){ return 3; } if (winO == 1 || winX == 1){ return 1; } if (count_ == 0) return 1; return 2; } }
Program: Tic Tac Toe TCTCTOE Solution in Python
from math import ceil,floor mat = ["___" for j in range(3)] for _ in range(int(input())): for i in range(3): mat[i] = input().strip() r = [] for i in range(3): r.append([0,0]) c = [] for i in range(3): c.append([0,0]) xval = 0; oval = 0; space = 0;cnt = 0 for i in range(3): for j in range(3): if mat[i][j] == 'X': r[i][0] += 1 c[j][0] += 1 xval += 1 elif mat[i][j] == 'O': r[i][1] += 1 c[j][1] += 1 oval += 1 else: space += 1 if xval > ceil( (9-space)/2 ) or oval > floor( (9-space)/2 ): print(3) else: xcnt = 0; ocnt = 0 for i in range(3): if r[i][0] == 3: xcnt += 1 if r[i][1] == 3: ocnt += 1 if c[i][0] == 3: xcnt += 1 if c[i][1] ==3: ocnt += 1 if mat[0][0] == 'X' and mat[1][1] == 'X' and mat[2][2] == 'X': xcnt += 1 if mat[0][0] == 'O' and mat[1][1] == 'O' and mat[2][2] == 'O': ocnt += 1 if mat[0][2] == 'X' and mat[1][1] == 'X' and mat[2][0] == 'X': xcnt += 1 if mat[0][2] == 'O' and mat[1][1] == 'O' and mat[2][0] == 'O': ocnt += 1 cnt = xcnt + ocnt if xcnt > 0 and ocnt > 0: print(3) elif xcnt > 0 : if xval == oval + 1: print(1) else: print(3) elif ocnt > 0: if xval == oval: print(1) else: print(3) elif space == 0: print(1) else: print(2)
Codechef Long Challenge Solutions
April Long Challenge 2021 Solutions
- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution
March Long Challenge 2021 Solutions
- An Interesting Sequence ISS SOLUTION
- Tree House THOUSES SOLUTION
- Valid Paths VPATH SOLUTION
- Modular Equation MODEQ SOLUTION
- Tic Tac Toe TCTCTOE SOLUTION
- Xor Equality XOREQUAL SOLUTION
- Golf LKDNGOLF SOLUTION
- Solubility SOLBLTY SOLUTION
February Long Challenge 2021
- 1. Frog Sort Solution Codechef
- 2. Chef and Meetings Solution Codechef
- 3. Maximise Function Solution Codechef
- 4. Highest Divisor Solution Codechef
- 5. Cut the Cake Challenge Solution Codechef
- 6. Dream and the Multiverse Solution Codechef
- 7. Cell Shell Solution Codechef
- 8. Multiple Games Solution Codechef
- 9. Another Tree with Number Theory Solution Codechef
- 10. XOR Sums Solution Codechef
- 11. Prime Game Solution CodeChef
- 12. Team Name Solution Codechef
January Long Challenge 2021
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef