PuzzlersWorld.com

  • Hacker Puzzle
  • Interview Puzzles
  • Number Puzzles
  • Maths Puzzles

Tic-Tac-Toe-Tomek Solution: Google codejam 2013 Qual Round

(No Ratings Yet)

April 14, 2013 by puzzler Leave a Comment

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the first problem from Qualification Round 2013.

Problem Statement

Tic-Tac-Toe-Tomek is a game played on a 4 x 4 square board. The board starts empty, except that a single ‘T’ symbol may appear in one of the 16 squares. There are two players: X and O. They take turns to make moves, with X starting. In each move a player puts her symbol in one of the empty squares. Player X’s symbol is ‘X’, and player O’s symbol is ‘O’.

After a player’s move, if there is a row, column or a diagonal containing 4 of that player’s symbols, or containing 3 of her symbols and the ‘T’ symbol, she wins and the game ends. Otherwise the game continues with the other player’s move. If all of the fields are filled with symbols and nobody won, the game ends in a draw. See the sample input for examples of various winning positions.

Given a 4 x 4 board description containing ‘X’, ‘O’, ‘T’ and ‘.’ characters (where ‘.’ represents an empty square), describing the current state of a game, determine the status of the Tic-Tac-Toe-Tomek game going on. The statuses to choose from are:

  • “X won” (the game is over, and X won)
  • “O won” (the game is over, and O won)
  • “Draw” (the game is over, and it ended in a draw)
  • “Game has not completed” (the game is not over yet)

If there are empty cells, and the game is not over, you should output “Game has not completed”, even if the outcome of the game is inevitable.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of 4 lines with 4 characters each, with each character being ‘X’, ‘O’, ‘.’ or ‘T’ (quotes for clarity only). Each test case is followed by an empty line.

Output

For each test case, output one line containing “Case #x: y”, where x is the case number (starting from 1) and y is one of the statuses given above. Make sure to get the statuses exactly right. When you run your code on the sample input, it should create the sample output exactly, including the “Case #1: “, the capital letter “O” rather than the number “0”, and so on.

Limits

The game board provided will represent a valid state that was reached through play of the game Tic-Tac-Toe-Tomek as described above.

Small dataset

1 ≤ T ≤ 10.

Large dataset

1 ≤ T ≤ 1000.

Sample

Input Output
6
XXXT
....
OO..
....
XOXT
XXOO
OXOX
XXOOXOX.
OX..
….
….

OOXX
OXXX
OX.T
O..O

XXXO
..O.
.O..
T…

OXXX
XO..
..O.
…O

Case #1: X won
Case #2: Draw
Case #3: Game has not completed
Case #4: O won
Case #5: O won
Case #6: O won

Solution

This problem was actually easy, it only needed a bit of coding rather than thinking, we just have to count the X’s, O’s, T’s and dots in every row, column and diagonals. At any point of time if (count of X’s are 4) OR (count of X’s are 3 and count of T’s are 1) we can say “X won” similar logic for “O won”. IF none of the two won and if there are any dots in the board=> Game has not completed else it is a draw.

Here is the Java code for Tic-Tac-Toe-Tomek problem in Google codejam Qualification round 2013

package googlecodejam2013;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Reader;

public class TicTacToeTomek {
	private static String X_WON="X won";
	private static String O_WON="O won";
	private static String DRAW="Draw";
	private static String GAME_NOT_COMPLETED="Game has not completed";
	
	public String getGameStatus(Character[][] board){
		boolean isGameNotCompleted = false;
		for(int i=0; i <4; i++){
			String status = getLineStatus(board[i][0], board[i][1],board[i][2],board[i][3]);
			if(status.equals(X_WON) || status.equals(O_WON)){
				return status;
			}else if(!isGameNotCompleted && status.equals(GAME_NOT_COMPLETED)){
				isGameNotCompleted = true;
			}
		}
		
		for(int i=0; i <4; i++){
			String status = getLineStatus(board[0][i], board[1][i],board[2][i],board[3][i]);
			if(status.equals(X_WON) || status.equals(O_WON)){
				return status;
			}else if(!isGameNotCompleted && status.equals(GAME_NOT_COMPLETED)){
				isGameNotCompleted = true;
			}
		}
		
		{//Diagonal one
			String status = getLineStatus(board[0][0], board[1][1],board[2][2],board[3][3]);
			if(status.equals(X_WON) || status.equals(O_WON)){
				return status;
			}else if(!isGameNotCompleted && status.equals(GAME_NOT_COMPLETED)){
				isGameNotCompleted = true;
			}
		}
		

		{//Diagonal two
			String status = getLineStatus(board[0][3], board[1][2],board[2][1],board[3][0]);
			if(status.equals(X_WON) || status.equals(O_WON)){
				return status;
			}else if(!isGameNotCompleted && status.equals(GAME_NOT_COMPLETED)){
				isGameNotCompleted = true;
			}
		}
		
		if(isGameNotCompleted){
			return GAME_NOT_COMPLETED;
		}
		return DRAW;
	}
	
	private String getLineStatus(Character one, Character two, Character three, Character four){
		Character[] arr = new Character[4];
		arr[0]=one;
		arr[1]=two;
		arr[2]=three;
		arr[3]=four;

		int xCount = 0;
		int oCount = 0;
		int tCount = 0;
		int dotCount = 0;
		
		for(Character c: arr){
			if(c == 'X'){
				xCount++;
			}
			else if(c == 'O'){
				oCount++;
			}else if(c == 'T'){
				tCount++;
			}else{
				dotCount++;
			}
		}
		if(xCount == 4 || (xCount == 3 && tCount == 1)){
			return X_WON;
		}else if(oCount == 4 || (oCount == 3 && tCount == 1)){
			return O_WON;
		}else if(dotCount > 0)
		{
			return GAME_NOT_COMPLETED;
		}else {
			return "";
		}
	}
	
	public static void main(String[] argv) {
		try {
			long startTime = System.currentTimeMillis();
			Reader reader = new FileReader("large.in");
			BufferedReader bufReader = new BufferedReader(reader);
			String x = bufReader.readLine();
			int numOfTestCases = Integer.parseInt(x);
			int count = 0;
	
			File file = new File("large.out");
			FileWriter writer = new FileWriter(file);
	
			for(count =1; count<= numOfTestCases; count++) {
				Character[][] board = getBoard(bufReader);
				String output = new TicTacToeTomek().getGameStatus(board);
				writer.write("Case #" + count + ": " + output+"\n");
			//	System.out.println("Case #" + count + ": "+ output);
				if(count != numOfTestCases){
					bufReader.readLine();//To read empty line
				}
			}
			writer.close();
			System.out.println("Total time = "
					+ (System.currentTimeMillis() - startTime));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	private static Character[][] getBoard(BufferedReader bufReader) throws IOException{
		Character[][] board = new Character[4][4];
		for(int i=0; i < 4;i++){
			String line = bufReader.readLine().trim();
			char[] cArr = line.toCharArray();
			board[i][0] =  cArr[0];
			board[i][1] =  cArr[1];
			board[i][2] =  cArr[2];
			board[i][3] =  cArr[3];
		}
		return board;
	}
}
  • Share on Whatsapp
  • Share on Facebook
  • Share on Twitter
Facebook Comments
Facebook
Next Puzzle
Lawnmower Solution: Google codejam 2013 Qual Round

Checkout more Interview Questions Tags: Easy, Google codejam, Interview, Java, Solved Puzzles

Leave a Comment Cancel reply

Submit your Puzzle

You may also like

  • Deceitful War Solution – Google Code Jam 2014
  • Swap two integer variables
  • Objective Questions set C/C++ – Part 2
  • 2nd smallest number from 32 numbers
  • Objective Questions set C/C++ – Part 4
  • Falling Diamonds Solution: Google codejam 2013 Round 1B
  • Find a pythagorean triplet from an array
  • Objective Questions set C/C++ – Part 1
  • Security problem solution: Facebook hacker cup 2013 Round 1
  • Tic-Tac-Toe-Tomek Solution: Google codejam 2013 Qual Round

Categories

  • Aive hi Puzzles
  • Akbar and Birbal
  • Alphabetical Puzzles
  • Bollywood Puzzles
  • Google Code jam
  • Hindi Riddles
  • Interview Puzzles
  • Interview Questions
  • Logical Puzzles
  • Malayalam Puzzles
  • Maths Puzzles
  • Miscellaneous
  • Number Puzzles
  • Picture Puzzles
  • Riddles
  • Tamil Puzzles
  • Technical

Social

  • View puzzlersworld’s profile on Twitter
privacy policy

Copyright © 2025 · eleven40 Pro Theme on Genesis Framework · WordPress · Log in

  • Hacker Puzzle
  • Logo Puzzles
  • Optical Illusions
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    ▼
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    ▲
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous