CareerCup

I just had this in my exam yesterday. The simple solution is traverse each matrix, and check for i whether (i,j) ,(i+1,j) and (i+2,j) are same. If yes then points++, also check for i whether (i,j), (i,j+1) and (i,j+2) are same and for i whether (i,j), (i+1,j+1) and (i+2,j+2) are same. Do points++ if they are same.
Do this till (i<n-1) and (j<n-2).
Compare points of player 1 and player 2 and return the winner.
Time complexity O(n sq).

We need to count triplets of each color (red or black), in the following directions
1) Horizontally
2) Vertically
3) Diagonally, top to bottom. (as we are counting triplets, we can have more diagonals, ex: 2 in case of 4x4 matrix)
4) Diagonally, bottom to top.(as we are counting triplets, we can have more diagonals, ex: 2 in case of 4x4 matrix)

public class Matrix_Color_Points {
	public static void main(String[] args) {

		char[][] matrix = { { 'r', 'r', 'r', 'b' }, { 'b', 'r', 'b', 'r' },
				{ 'b', 'r', 'r', 'b' }, { 'b', 'r', 'b', 'b' } };
		int red_count = findCount(matrix, 4, 4, 'r');
		int blue_count = findCount(matrix, 4, 4, 'b');
		System.out.println("Count of red triplets: " + red_count);
		System.out.println("Count of blue triplets: " + blue_count);
	}

	private static int findCount(char[][] matrix, int row, int col, char c) {
		/**
		 * As we need to count horizontal triplets, we must look at all rows but
		 * stop two columns before, otherwise we would get IndexOutOfBound since
		 * we need to count only triplets.
		 */
		int count = 0;
		// For all horizontal triplets.
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col - 2; j++) {
				if (matrix[i][j] == c && matrix[i][j + 1] == c
						&& matrix[i][j + 2] == c)
					count++;
			}
		}

		/**
		 * As we need to count vertical triplets, we must look at all columns
		 * but stop two rows before, otherwise we would get IndexOutOfBound
		 * since we need to count only triplets.
		 */
		// for all vertical triplet
		for (int i = 0; i < row - 2; i++) {
			for (int j = 0; j < col; j++) {
				if (matrix[i][j] == c && matrix[i + 1][j] == c
						&& matrix[i + 2][j] == c)
					count++;
			}
		}

		/**
		 * As we need to count diagonal triplets from top to bottom, we must but
		 * stop two rows and two columns before, otherwise we would get
		 * IndexOutOfBound since we need to count only triplets.
		 */
		// for all top down diagonal triplets
		for (int i = 0; i < row - 2; i++) {
			for (int k = 0; k < col - 2; k++) {
				if (matrix[i][k] == c && matrix[i + 1][k + 1] == c
						&& matrix[i + 2][k + 2] == c)
					count++;
			}
		}

		/**
		 * As we need to count diagonal triplets from bottom to top, we must but
		 * stop two rows and two columns before, otherwise we would get
		 * IndexOutOfBound since we need to count only triplets. And we start
		 * from bottom.
		 */
		// for all bottom to top diagonal triples
		for (int i = row - 1; i > 1; i--) {
			for (int k = 0; k < col - 2; k++) {
				if (matrix[i][k] == c && matrix[i - 1][k + 1] == c
						&& matrix[i - 2][k + 2] == c)
					count++;
			}
		}
		return count;
	}

}

Count of red triplets: 5
Count of blue triplets: 1

Why not spend an extra 2 min. typing the question more clearly, with more details , and possibly an example? This might save hordes of people many minutes, don't you think?

The easiest way -brute force, will be for each cell, try all possible moving directions in 3 steps, and store the resulting triple-cell into a hashmap. count them at the end and compare.

def points(board):
	if len(board)>=3:
		points= {"red":0,"black":0}
		point_h=False
		point_v=False
		point_d=False

		for n,line in enumerate(board):
			for m,x in enumerate(line):
				if len(board[n])-(m)>=3:
					if board[n][m]==board[n][m+1] and board[n][m]==board[n][m+2] and not point_h:
						points[board[n][m]]+=1
						point_h=True
						print board[n][m], "horizontal"
						if len(board[n])-(m)>=4:
							if board[n][m]==board[n][m+3]:
								points[board[n][m]]+=1
								print board[n][m], "horizontal"
					else:
						point_h=False

				if len(board)-(n)>=3:
					if board[n][m]==board[n+1][m] and board[n][m]==board[n+2][m] and not point_v:
						points[board[n][m]]+=1
						point_v=True
						print board[n][m], "vertical"
						if len(board)-(n)>=4:
							if board[n][m]==board[n+3][m]:
								points[board[n][m]]+=1
								print board[n][m], "vertical"
					else:
						point_v=False

				if len(board)-(n)>=3 and len(board[n])-(m)>=3:
					if board[n][m]==board[n+1][m+1] and board[n][m]==board[n+2][m+2] and not point_d:
						points[board[n][m]]+=1
						point_d=True
						print board[n][m], "diagonal"
						if len(board)-(n)>=4:
							if board[n][m]==board[n+3][m]:
								points[board[n][m]]+=1
								print board[n][m], "diagonal"
					else:
						point_d=False
		print points
		if points["red"]>points["black"]:
			return "Red"
		elif points["black"]>points["red"]:
			return "Black"
		else:
			return "Tie"
	else:
		return "Small board"

traverse from 4 directions. horizontally (N), vertically (N), from left top to right bottom (2N-5), from left top to right bottom (2N-5). Keep track of points during traversing.
Time complexity O(N)

Not sure if this is a right solution.

package DP;

public class Mattrix_color_points {

public static void main(String[] args) {

char[][] matrix = {{'r','r','r','b'},{'b','r','b','r'},{'b','r','r','b'},{'b','r','b','b'}};
int row = 4, column=4;
int red_count = findCount(matrix,4,4,'r');
int blue_count = findCount(matrix,4,4,'b');
System.out.println("Count of red triplets: "+red_count);
System.out.println("Count of blue triplets: "+blue_count);
}

private static int findCount(char[][] matrix, int m, int n, char c) {

int count = 0;

for(int i=0;i<m;i++)
{
for(int j=0;j<n-2;j++) //for all horizontal triplet
{
if(matrix[i][j]==c && matrix[i][j+1]==c && matrix[i][j+2]==c)
count++;
}
for(int k=0;k<n-2-i;k++) //top down diagonal
{
if(matrix[i][k]==c && matrix[i+1][k+1]==c && matrix[i+2][k+2]==c)
count++;
}
}
//for all vertical triplet
for(int i=0;i<m-2;i++)
{
for(int j=0;j<n;j++)
{
if(matrix[i][j]==c && matrix[i+1][j]==c && matrix[i+2][j]==c)
count++;
}
}
//for all bottom to top diagonal triples
for(int i=m-2;i<m;i++)
{
for(int k=0;k<n-2;k++)
{
if(matrix[i][k]==c && matrix[i-1][k+1]==c && matrix[i-2][k+2]==c)
count++;
}
}

return count;
}

}

You should change the last loop for the top down approach.
It should be for(int i=m-1;i>=2;i--)

public static int findCount(char[][] matrix, int x, int y, char c){

int count = 0;


for(int i = 0; i < x; i++){

for(int j = 0; j < y; j++){
//Horizontal
if(j < y-2 && matrix[i][j]==c && matrix[i][j+1]==c && matrix[i][j+2]==c){
count++;
}
//Vertical
if(i < x-2 && matrix[i][j]==c && matrix[i+1][j]==c && matrix[i+2][j]==c){
count++;
}
//Diagonal left to right
if(i < x-2 && j < y-2 && matrix[i][j]==c && matrix[i+1][j+1]==c && matrix[i+2][j+2]==c){
count++;
}

}

for(int j = y-1; j > 0; j--){

//Diagonal right to left
if(i < x-2 && j > 1 && matrix[i][j]==c && matrix[i+1][j-1]==c && matrix[i+2][j-2]==c){
count++;
}
}

}


return count;
}

public class Epic_REDBLK {
public String findWinner(int[][] grid){//1 is RED, 0 is BLK

int countRED = 0;
int countBLK = 0;
for(int row = 0;row<grid.length;row++){
for(int col = 0;col<grid[0].length;col++){
if(grid[row][col] == 1) countRED += findWinner(grid,1,row,col);
else countBLK += findWinner(grid,0,row,col);
}
}
return countRED>countBLK? "RED":(countRED==countBLK? "TIE":"BLACK");
}

/** just for test the result
*
* @param grid
* @param color
* @return the points of the target color
*/
public int findWinner(int[][] grid, int color){//1 is RED, 0 is BLK
int countRED = 0;
int countBLK = 0;
for(int row = 0;row<grid.length;row++){
for(int col = 0;col<grid[0].length;col++){
if(grid[row][col] == 1) countRED += findWinner(grid,1,row,col);
else countBLK += findWinner(grid,0,row,col);
}
}
return color==1? countRED:countBLK;
}

public int findWinner(int[][] grid, int target, int row, int col){
int countRED = 0;
int rows = grid.length;
int cols = grid[0].length;
int countCur = 1;
//right
for(int i=1;i+col<cols;i++){
if(grid[row][col+i]==target){
++countCur;
if(countCur==3){
++countRED;
break;
}
}else{
break;
}
}
countCur = 1;
//rightdown
for(int i=1;i+row<rows&&i+col<cols;i++){
if(grid[row+i][col+i]==target){
++countCur;
if(countCur==3){
++countRED;
break;
}
}else{
break;
}
}
countCur = 1;
//down
for(int i=1;i+row<rows;i++){
if(grid[row+i][col]==target){
++countCur;
if(countCur==3){
++countRED;
break;
}
}else{
break;
}
}
countCur = 1;
//leftdown
for(int i=1;i+row<rows&&col-i>=0;i++){
if(grid[row+i][col-i]==target){
++countCur;
if(countCur==3){
++countRED;
break;
}
}else{
break;
}
}

return countRED;
}

/**main func/test case
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Epic_REDBLK test = new Epic_REDBLK();


int[][] grid = new int[][]{
{0,1,0,1,1},
{0,1,1,1,1},
{0,1,0,1,1},
{1,0,1,0,1},
};
System.out.println(test.findWinner(grid));
}

}

Few bugs, but you get the idea.

var matrixTrval = (function() {

	var findWinner = function(matrix, currentResult) {
		if (matrix.length === 0) {
			console.log(currentResult.score);
			return currentResult.score;
		}
		var thisNodeScore = {};

		currentResult = currentResult || {
			color: matrix[0][0],
			count: 0,
			score: 0,
			isVertical: true,
			vcount: 0
		}

		if (matrix[0][0] === currentResult.color) {
			thisNodeScore = {
				count: currentResult.count + 1,
				color: currentResult.color
			};
			if (currentResult.isVertical) {
				if (currentResult.vcount >= 3) {
					thisNodeScore.score = currentResult.score + 2;
				}
				thisNodeScore.vcount = currentResult.vcount + 1;
			} else if (currentResult.count >= 2) {
				thisNodeScore.score = currentResult.score + 1;
			}
			thisNodeScore.count = currentResult.count + 1;
		}
		thisNodeScore = {
			count: thisNodeScore.count || 1,
			color: currentResult.color,
			isVertical: currentResult.isVertical,
			vcount: thisNodeScore.vcount || 1,
			score: thisNodeScore.score || 0
		}

		var moveDownMatrix = [];
		var moveRightMatrix = [];
		var moveDiagonalMatrix = [];
		var i = 0;
		var m = 0;
		var length = matrix.length;
		var vLength = matrix[0].length;


		for (i = 0; i < length; i++) {
			moveRightMatrix[i] = [];
			moveDownMatrix[i] = [];
			moveDiagonalMatrix[i] = [];
			for (m = 0; m < vLength; m++) {
				moveRightMatrix[i][m] = matrix[i][m];
				moveDownMatrix[i][m] = matrix[i][m];
				moveDiagonalMatrix[i][m] = matrix[i][m];
			}
		}

		if (moveDownMatrix.length >= 1) {
			moveDownMatrix = moveDownMatrix.slice(1);
			thisNodeScore.isVertical = true;
		}
		for (i = 0; i < length && moveRightMatrix[i].length > 0; i++) {
			moveRightMatrix[i] = moveRightMatrix[i].slice(1);
		}

		for (i = 0; i < length && moveDiagonalMatrix[i].length > 0; i++) {
			moveDiagonalMatrix[i] = moveDiagonalMatrix[i].slice(1);
		}
		if (moveDiagonalMatrix.length > 1 && moveDiagonalMatrix[0].length >= 1) {
			moveDiagonalMatrix = moveDiagonalMatrix.slice(1);
		}
		if (moveRightMatrix[0].length === 0) {
			moveRightMatrix = [];
		}
		if (moveDiagonalMatrix[0].length === 0) {
			moveDiagonalMatrix = [];
		}

		var moveDownScore = thisNodeScore.score;
		if (moveDownMatrix.length > 0) {
			moveDownScore = findWinner(moveDownMatrix, thisNodeScore);
		}
		thisNodeScore.isVertical = false;


		var moveRightScore = thisNodeScore.score;

		if (moveRightMatrix.length > 0) {
			moveRightScore = findWinner(moveRightMatrix, thisNodeScore);
		}


		var moveDiagonalScore = thisNodeScore.score;
		if (moveDiagonalMatrix.length > 0) {
			moveDiagonalScore = findWinner(moveDiagonalMatrix, thisNodeScore);
		}

		var bestWinner = moveRightScore > moveDownScore ? moveRightScore : moveDownScore;
		bestWinner = moveDiagonalScore > bestWinner ? moveDiagonalScore : bestWinner;

		return bestWinner;
	};

	return function(matrix) {
		return findWinner(matrix);
	};
})();

console.log(matrixTrval([
	['red', 'black', 'black', 'black', 'red'],
	['red', 'black', 'black', 'black', 'red'],
	['red', 'black', 'black', 'black', 'red'],
	['red', 'black', 'black', 'black', 'red'],
	['red', 'black', 'black', 'black', 'red'],
	['red', 'black', 'black', 'black', 'red'],
	['red', 'black', 'black', 'black', 'red'],
	['red', 'black', 'black', 'black', 'red']
]));

This question needs to be clarified a little bit.

Have you ever considered the case when the user goes right, then down, then upright?

For this question, tt seems that only one direction is considered at a time, which greatly reduce the complexity of this problem. But the random walk case seems more fun to do (seems like a 3 dimensional DP problem I guess).

Anyway, with a bit memoization steps, this question is easy to solve. O(n^2), O(n).

Playable code at

ideone.com/qFgocO

int countHelper(vector<vector<char>>& matrix, char targetColor, pair<int, int> dir, int onepoint=3) {
	if (!matrix.size() || !matrix[0].size()) return 0;
	int rowcount(matrix.size()), colcount(matrix[0].size());

	int ret = 0;
	vector<vector<int>> count(rowcount, vector<int>(colcount, 0));
	for (int col = colcount - 1; col >= 0; --col) {		// col goes next
		for (int row = rowcount - 1; row >= 0; --row) {	// row goes first
			if (matrix[row][col] != targetColor) continue;
			// check the next one along the line.
			count[row][col] = 1;
			int nextrow(row + dir.first), nextcol(col + dir.second);
			if (!(nextrow < 0 || nextrow == rowcount || nextcol < 0 || nextcol == colcount))
				count[row][col] += count[nextrow][nextcol];
			ret += (count[row][col] >= onepoint);
		}
	}

	return ret;
}

bool winner(vector<vector<char>>& matrix) {
	int red = countHelper(matrix, 'r', pair<int, int>{-1, 1}) + \
			  countHelper(matrix, 'r', pair<int, int>{0, 1}) + \
			  countHelper(matrix, 'r', pair<int, int>{1, 1}) + \
			  countHelper(matrix, 'r', pair<int, int>{1, 0});

	int black = countHelper(matrix, 'b', pair<int, int>{-1, 1}) + \
				countHelper(matrix, 'b', pair<int, int>{0, 1}) + \
				countHelper(matrix, 'b', pair<int, int>{1, 1}) + \
				countHelper(matrix, 'b', pair<int, int>{1, 0});

	return red > black;
}

#include <iostream>
#include <sstream>
#include <cmath>
#include <string.h>
using namespace std;

int main()
{
int n, counter=1,rpoint=0,bpoint=0;
cout<<"\n Enter n";
cin>>n;
int arr[n][n];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>arr[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<" "<<arr[i][j];
}
cout<<endl;
}
for(int i=0;i<n;i++)
{ counter=1;
for(int j=0;j<n-1;j++)
{
if(arr[i][j]==arr[i][j+1]) counter++;
else
{
if(counter>=3)
{
if(arr[i][j]==0)
{
bpoint+=(counter%3)+(counter/3);
counter=1;
}
else
{
rpoint+=(counter%3)+(counter/3);
counter=1;
}
}
else counter=1;
}
if(j==n-2)
{
if(counter>=3)
{
if(arr[i][j]==0)
{
bpoint+=(counter%3)+(counter/3);
counter=1;
}
else
{
rpoint+=(counter%3)+(counter/3);
counter=1;
}
}
else counter=1;
}

}
}
if(rpoint>bpoint) cout<<"r is winner";
else cout<<"b is winner";
return 0;
}

public class MatrixBlackWhite {
	public static void main(String args[]){
		
		int[][] BAndW ={{0,1,0,1,0},{1,0,1,0,1},{0,0,0,1,1},{1,1,1,1,1},{1,1,0,0,1}};
		System.out.println(checkPoints(BAndW,0));
		System.out.print(checkPoints(BAndW,1));
	}
	public static int checkPoints(int[][] a,int f){
		int count=0;//You cannot set visibility scopes (private,...) to local variables.
		//row
		for(int i=0;i<a.length;i++){
			for(int c1=0;c1<a[i].length-2;c1++){
				if(a[i][c1]==a[i][c1+1]&&a[i][c1+1]==a[i][c1+2]&&a[i][c1]==f)
				count++;	
			}
		}
		//column
		for(int j=0;j<a[0].length;j++){
			for(int c2=0;c2<a.length-2;c2++){
				if(a[c2][j]==f&&a[c2][j]==a[c2+1][j]&&a[c2+1][j]==a[c2+2][j])
					count++;
			}
		}
		//diagonal
		//lefttop-rightdown
		for(int row=2;row>=0;row--){
			for(int colm=0;colm<3-row;colm++){
				if(a[row][colm]==f&&a[row+1][colm+1]==a[row][colm]&&a[row+2][colm+2]==a[row][colm])
					count++;
			}
		}
		//leftdown-righttop
		for(int row=2;row>=0;row++){
			for(int colm=0;colm<3-row;colm++){
				if(a[row][colm]==f&&a[row-1][colm+1]==a[row][colm]&&a[row-2][colm+2]==a[row][colm])
					count++;
			}
		}
		return count;
	}

}