[Google] Winner of tic-tac-toe

Question

link

How would you determine if someone has won a game of tic-tac-toe on a board of any size?

(This is also on CC150v4 19.2 and CC150v4 17.2)

Solution

First, confirm that when the number of pieces in a line equals to the dimension of the board, one person wins. Eg. for 10 * 10 board, 10 pieces need to be in 1 line.

We can determine if someone has won during a game in real time, as in checking after every move.

Create an array of size 2n+2 at the beginning of the game and fill it with zeros. Each spot in the array will be a sum of X’s or O’s horizontally (the first n places in the array), vertically (the second n places in the array) and diagonally (the last 2 places). Then with every move, you add 1 to the 2 places (or 3 if on a diagnol) of the array if X, and subtract 1 if its an O. After adding you check and see if the value of the array is equal to n or -n, if it is, n mean X has won and -n means O has won.

This is uses O(2n+2) space, but it’s the best solution I can find online. I wrote code posted below.

Code

written by me

enum Piece {
	Empty, Red, Blue
};

public static Piece hasWon3(Piece[][] board) {

	int N = board.length;

	// O(2n+2) space to store count info
	int[] rowCnt = new int[N];
	int[] colCnt = new int[N];
	int[] digCnt = new int[2];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {

			int pieceValue = 0;
			if (board[i][j] == Piece.Blue) {
				pieceValue = 1;
			} else if (board[i][j] == Piece.Red) {
				pieceValue = -1;
			}

			// if empty, pieceValue is 0
			// if blue, add 1 in count
			// if red, subtract 1 in count
			rowCnt[i] += pieceValue;
			if (checkFinish(rowCnt[i], N) != null) {
				return checkFinish(rowCnt[i], N);
			}

			// after adding the count, check if the game finishes
			colCnt[j] += pieceValue;
			if (checkFinish(colCnt[j], N) != null) {
				return checkFinish(colCnt[j], N);
			}

			if (i == j) {
				digCnt[0] += pieceValue;
				if (checkFinish(digCnt[0], N) != null) {
					return checkFinish(digCnt[0], N);
				}
			} else if (i + j == N) {
				digCnt[1] += pieceValue;
				if (checkFinish(digCnt[1], N) != null) {
					return checkFinish(digCnt[1], N);
				}
			}
		}
	}
	// game not finished, continue
	return Piece.Empty;
}

private static Piece checkFinish(int count, int N) {
	if (count == N)
		return Piece.Blue;
	else if (count == -1 * N)
		return Piece.Red;
	else
		return null;
}