# "Connect four" code to check for horizontals, verticals, and diagonals

My textbook (David Liang's Introduction to Java Programming) asks me to write a program which

• prompts a user to specify the number of rows and columns in a matrix
• prompts the user to enter each element of the matrix as it would appear in a table
• checks that matrix to see if there are any four elements in a row (horizontally, vertically, and diagonally) that are identical to one another

The problem is a preliminary step to a "Connect Four" game that it asks us to implement later on. I've pasted my code at the very bottom for review, and I've included ample and thorough comments to clarify what I've done. I realize my code is a bit inefficient because it checks all the way up to the very bottom right element. Unfortunately, I was unable to find a workaround to this, as limiting the col and row variables will complicate things quite a bit. On paper, we could toss out the bottom right 3x3 block because there's nothing there for us to check, but there is no way to eliminate that block without eliminating the top-right 3x3 block.

Here are some example scenarios from my textbook. My program successfully returns true for each of these cases, but I would like to optimize my code, now that I've found a successful solution to the problem.

It's about 97 lines long, and I've used methods to make things a bit easier to understand.

import java.util.Scanner;

public class FourIdentical
{

// Class scanner, for simplicity
static Scanner scan = new Scanner(System.in);

/* CLIENT CODE */
public static void main( String [] args )
{
// Prompts the user to enter information
System.out.print("Number of rows: ");
int numRows = scan.nextInt();
System.out.print("Number of columns: ");
int numCols = scan.nextInt();
int [][] matrix = new int[numRows][numCols];

// Initializes the matrix's elements
System.out.println("Below, please enter each element of the array.");
initializeMatrix(matrix);

// Find identical fours and print true if found, false otherwise
System.out.println( checkForIdenticalFour(matrix) );

}

/* Helper method that initializes the elements of the current matrix to the
integers that a user has entered from the console */
public static void initializeMatrix( int [][] matrix )
{
for( int row = 0; row < matrix.length; row++ )
{
for( int col = 0; col < matrix[row].length; col++ )
{
matrix[row][col] = scan.nextInt();
}
}
}

/* This method checks if there are four identical elements in a matrix either
horizontally, vertically, or diagonally */
public static boolean checkForIdenticalFour( int [][] matrix )
{

/* We traverse each element in the matrix */
for( int row = 0; row < matrix.length; row++ )
{
for( int col = 0; col < matrix[row].length; col++ )
{

// This is the current element in our matrix
int element = matrix[row][col];

/* If there are 3 elements remaining to the right of the current element's
position and the current element equals each of them, then return true */
if( col <= matrix[row].length-4 && element == matrix[row][col+1] && element == matrix[row][col+2] && element == matrix[row][col+3] )
return true;

/* If there are 3 elements remaining below the current element's position
and the current element equals each of them, then return true */
if( row <= matrix.length - 4 && element == matrix[row+1][col] && element == matrix[row+2][col] && element == matrix[row+3][col] )
{
return true;
}

/* If we are in a position in the matrix such that there are diagonals
remaining to the bottom right of the current element, then we check */
if( row <= matrix.length-4 && col <= matrix[row].length-4 )
{
// If the current element equals each element diagonally to the bottom right
if( element == matrix[row+1][col+1] && element == matrix[row+2][col+2] && element == matrix[row+3][col+3] )
return true;
}

/* If we are in a position in the matrix such that there are diagonals
remaining to the bottom left of the current element, then we check */
if( row <= matrix.length-4 && col >= matrix[row].length-4 )
{
// If the current element equals each element diagonally to the bottom left
if( element == matrix[row+1][col-1] && element == matrix[row+2][col-2] && element == matrix[row+3][col-3] )
return true;
}

}
}

/* If all the previous return statements failed, then we found no such
patterns of four identical elements in this matrix, so we return false */
return false;
}

}

• Wow, and after running a couple of "tricky" test cases, it seems my code doesn't always work, particularly for diagonals at the corners. Dec 21 '16 at 18:00
• Welcome to Code Review! Great job providing some background to your code and identifying what you'd like to improve. Hopefully you get some helpful feedback! Dec 21 '16 at 19:22
• col >= matrix[row].length-4 is incorrect. It should be something like col >= 3. I.e. col - 3 has to be at least zero. Dec 21 '16 at 23:31
• @mdfst but matrix[row].length is 7 because there are 7 columns, so 7-4 is 3, which is basically what you have, right? Or did I misunderstand something? Dec 22 '16 at 1:18

The primary question was about performance. But let me point out a few things that may be considered as "subjective", but that I consider as rather important:

# Commenting

Comments are important. And I understand that you inserted comments to make things easier (maybe for you as well as for the reviewers). And I think that // Inline comments can really help you to identify relevant parts of the code when quickly skimming over it. These may be short, like

// Check row to the right
...
// Check column to the bottom
...
// Check diagonal to the bottom right
...
// Check diagonal to the bottom left


These really can help to quickly find the relevant loop (as the loops look very similar otherwise).

(Note, however, that some people consider such comments as a "code smell". They argue that, when you think that you have to write a comment, then you should try to make the code clearer. In this particular case, they might recommend introducing additional methods like checkRow, checkColumn, checkDiagonal etc. But I think that inline comments have their justification, as stated above.)

Nevertheless: You can go too far. In practice, comments like these are basically just noise:

// This is the current element in our matrix
int element = matrix[row][col];


They don't really convey information or make clearer what is happening there.

Additionally, I strongly suggest to avoid /* block comments */ in methods. These should be reserved for either implementation notes (outside of methods), or for JavaDoc method- and class comments. (This may be a bit subjective, though)

## Formatting

No, this is not about the question of whether the { should be in the same line or in the next line ;-) This is about consistency: In most cases, you wrote

if(...)
return true;


but in one case, you wrote

if(...)
{
return true;
}


In most coding guidelines that I have read so far, the recommendation was to always use the { brackets } even for single-line blocks.

Similarly, you sometimes wrote matrix.length-4 and sometimes matrix.length - 4. Yes, I think that the spaces matter.

# Testability

Although the task was to allow the user to enter the matrix, I cannot imagine how you tested this more than once or twice. Didn't it become boring to enter the same values again and again? The first thing that I did was replacing the contents of your main method with this:

int matrix[][] = new int[][] {
{ 0, 1, 2, 3, 4, 5 },
{ 6, 7, 8, 9,10,11 },
{12,13,14,15,16,17 },
{18,19,20,21,22,23 },
{24,25,26,27,28,29 },
};

// Find identical fours and print true if found, false otherwise
System.out.println( checkForIdenticalFour(matrix) );


This allows you to quickly test different border cases. And this helped me to verify...

# a bug!

As pointed out in the comments: The condition in the last if-statement is wrong. It should not be col >= matrix[row].length-4, but col >= 3. Otherwise, it crashes with the following matrix

int matrix[][] = new int[][] {
{ 0, 1, 2, 3, 4, 5 },
{ 6, 7, 1, 9,10,11 },
{12, 1,14,15,16,17 },
{ 1,19,20,21,22,23 },
{24,25,26,27,28,29 },
};


causing an ArrayIndexOutOfBoundsException.

# Coming to the core: Performance

This, in fact, is difficult. It's nearly impossible to say how the performance could be improved here. One could argue about the last three if-blocks in the loop...

if( row <= matrix.length - 4 && element == ... ) { ... }
if( row <= matrix.length - 4 && col <= matrix[row].length-4 ) { ...}
if( row <= matrix.length - 4 && col >= 3 ) { ... }


that could obviously be condensed into one. But it's nearly impossible that this will have a measurable performance impact, even if this is executed millions of times.

Similarly, one could argue that the expression matrix[row] is repeated several times, and could be pulled out into a int currentRow[] = matrix[row]; to avoid repeated dereferencing.

But it might be that the JIT does this sort of optimization internally.

So first, a disclaimer:

Without profiling and looking at the resulting assembly, this sort of optimization is just guesswork.

But if I had to make sure that the performance is as high as possible for this particular code snippet, then I would try something that you already mentioned in the question:

On paper, we could toss out the bottom right 3x3 block because there's nothing there for us to check

This can be done. One could write the checks as follows:

private static boolean checkRows(int[][] matrix)
{
for (int row = 0; row < matrix.length; row++)
{
for (int col = 0; col < matrix[row].length - 3; col++)
{
int element = matrix[row][col];
if (element == matrix[row][col + 1] &&
element == matrix[row][col + 2] &&
element == matrix[row][col + 3])
{
return true;
}
}
}
return false;
}

private static boolean checkColumns(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 0; col < matrix[row].length; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col] &&
element == matrix[row + 2][col] &&
element == matrix[row + 3][col])
{
return true;
}
}
}
return false;
}

private static boolean checkMainDiagonal(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 0; col < matrix[row].length - 3; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col + 1] &&
element == matrix[row + 2][col + 2] &&
element == matrix[row + 3][col + 3])
{
return true;
}
}
}
return false;
}

private static boolean checkCounterDiagonal(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 3; col < matrix[row].length; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col - 1] &&
element == matrix[row + 2][col - 2] &&
element == matrix[row + 3][col - 3])
{
return true;
}
}
}
return false;
}

public static boolean checkForIdenticalFour(int[][] matrix)
{
return checkRows(matrix) ||
checkColumns(matrix) ||
checkMainDiagonal(matrix) ||
checkCounterDiagonal(matrix);
}


(In fact, the four methods could be combined into one again, that receives additional parameters for the loop limits and the row- and column step size - but this would undermine the point here)

The reasoning of why this might have a better performance is

• The methods are shorter. When you look at the Java HotSpot VM options, you will see the option -XX:MaxInlineSize=35 which indicates the maximum bytecode size of a method to be inlined, so shorter methods can be advantageous
• The loops are tailor-made for the checks that have to be done. Note that the if queries that you used to detect whether a certain check can be done are no longer necessary. The loops are fitting exactly to what has to be tested.
• The pattern is more regular. This does not only look nice ;-) it is also not unlikely that this is beneficial in terms of caching. But this is tremendously hard to verify profoundly.

So again, the disclaimer:

Without profiling and looking at the resulting assembly, this sort of optimization is just guesswork.

In order to obtain reliable results, you should use a profiler like JMH.

But also keep in mind: The actual performance may depend on factors that are beyond the implementation. Imagine that you had to check a few million matrices. And imagine that all these matrices contained

• 4 equal values in the last checked diagonal OR
• 4 equal values in the first checked row

The performance would vary wildly depending on where the equal values are found, and you could seemingly(!) affect the performance just by changing the order of your loops, to cause the method to return true earlier for one of both cases.

# Update

I was curious about the performance, and went an extra mile here.

I created a "microbenchmark". As usual, such microbenchmarks should be taken with a grain of salt. But I took into account several basics for this: The different implementations are run alternatingly, in several passes, with different inputs, several times, to give the JIT a chance to kick in. The results of the computations are used and printed, to avoid dead code elimination.

The tl;dr is: Your original approach already was pretty fast. The Improvements that can be achieved with my initial suggestsion are hardly measurable, and in the range of a few percent.

As stated above, the "performance" of one approach may heavily depend on the combination of

• where the four equal values are contained in the matrix
• in which order the possible appearances of the four values are checked

To compensate for that, I created a method that generates all possible matrices with all possible appearances of four equal elements. The printMatrices flag may be enabled to print these matrices:

   26    1    2    3    4
26    6    7    8    9
26   11   12   13   14
26   16   17   18   19
20   21   22   23   24

0   26    2    3    4
5   26    7    8    9
10   26   12   13   14
15   26   17   18   19
20   21   22   23   24

...

0    1    2    3    4
5    6    7    8   26
10   11   12   26   14
15   16   26   18   19
20   26   22   23   24


You can see that the equal values appear

• As a column, in row 0, column 0
• As a column, in row 0, column 1
• ...
• As a counter-diagonal in row 1, column 4

So these are simply all possible matrices, stored in a list.

The code of this micromenchmark and the tested approaches are at the bottom. The approaches are implemented in the classes FourIdenticalA (your approach), FourIdenticalB (my modified approach), and FourIdenticalC a new approach:

# The new approach

First of all: The new approach is slower than the others, but included here nevertheless.

When looking at your initial approach, one can see that it seems to be redundant and repetitive. For example, when checking for 4 equal elements in a row, then you acually check the following matrix elements for equality:

                                        column:     0 1 2 3 4 5 6 7
---------------
row 0 values:    8 2 5 5 5 5 9 1
checked values:
row 0, check for 4 elements starting at column 0:   X X X X
row 0, check for 4 elements starting at column 1:     X X X X
row 0, check for 4 elements starting at column 2:       X X X X
(return "true", because "5 5 5 5" was found)


My idea was that this could be ""optimized"". I thought that it could be beneficial to simply check the whole row, and count how many equal elements are found

                                        column:     0 1 2 3 4 5 6 7
---------------
row 0 values:    8 2 5 5 5 5 9 1
counter how many equal elements are found:          1 1 1 2 3 4
(return "true", because four equal elements are found)


But again, this turned out to be slower. It seems that the "loop unrolling" that you did by manually accessing the entries r[col], r[col+1], r[col+2], r[col+3] causes a higher performance in the end.

The whole code of the microbenchmark:

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;

public class FourIdenticalPerformance
{
public static void main(String[] args)
{
int minRows = 5;
int maxRows = 15;
int minCols = 5;
int maxCols = 15;
int times = 4;

System.out.println("Generating...");
List<int[][]> matrices = generateMatrices(
minRows, maxRows, minCols, maxCols, times);
System.out.println("Generating DONE, " + matrices.size() + " matrices");

boolean printMatrices = false;
//printMatrices = true;
if (printMatrices)
{
for (int matrix[][] : matrices)
{
print(matrix);
}
}

int passes = 10;
int runs = 50;
for (int pass=0; pass < passes; pass++)
{
long before = 0;
long after = 0;

int countA = 0;
before = System.nanoTime();
for (int matrix[][] : matrices)
{
for (int run = 0; run < runs; run++)
{
boolean b = FourIdenticalA.checkForIdenticalFour(matrix);
if (b)
{
countA++;
}
}
}
after = System.nanoTime();

System.out.printf(Locale.ENGLISH, "A duration %8.3fms count %d\n",
(after - before) / 1e6, countA);

int countB = 0;
before = System.nanoTime();
for (int matrix[][] : matrices)
{
for (int run = 0; run < runs; run++)
{
boolean b = FourIdenticalB.checkForIdenticalFour(matrix);
if (b)
{
countB++;
}
}
}
after = System.nanoTime();

System.out.printf(Locale.ENGLISH, "B duration %8.3fms count %d\n",
(after - before) / 1e6, countB);

int countC = 0;
before = System.nanoTime();
for (int matrix[][] : matrices)
{
for (int run = 0; run < runs; run++)
{
boolean b = FourIdenticalC.checkForIdenticalFour(matrix);
if (b)
{
countC++;
}
}
}
after = System.nanoTime();

System.out.printf(Locale.ENGLISH, "C duration %8.3fms count %d\n",
(after - before) / 1e6, countC);

}
}

// Generate all matrices in the given size range that contain all
// possible configurations of 'times' equal values, horizontally,
// vertically and diagonally
private static List<int[][]> generateMatrices(
int minRows, int maxRows, int minCols, int maxCols, int times)
{
List<int[][]> matrices = new ArrayList<int[][]>();
int directions[][] = {
{ 1, 0 },
{ 0, 1 },
{ 1, 1 },
{ 1, -1 },
};

for (int rows = minRows; rows <= maxRows; rows++)
{
for (int cols = minCols; cols <= maxCols; cols++)
{
for (int dir = 0; dir < directions.length; dir++)
{
int value = rows * cols + 1;

int dr = directions[dir][0];
int dc = directions[dir][1];

int minRow = 0;
int maxRow = rows;
int minCol = 0;
int maxCol = cols;

if (dr < 0)
{
minRow = times - 1;
}
if (dr > 0)
{
maxRow = rows - times + 1;
}
if (dc < 0)
{
minCol = times - 1;
}
if (dc > 0)
{
maxCol = cols - times + 1;
}

for (int r = minRow; r < maxRow; r++)
{
for (int c = minCol; c < maxCol; c++)
{
int[][] matrix = createMatrix(rows, cols);
placeValue(matrix, r, c, dr, dc, times, value);
}
}
}
}
}
return matrices;
}

private static void print(int matrix[][])
{
int rows = matrix.length;
int cols = matrix[0].length;
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
System.out.printf("%5d", matrix[r][c]);
}
System.out.println();
}
System.out.println();
}

// Place the given value at the specified position, the given number
// of times, making a step of (dr,dc) each time
private static void placeValue(
int matrix[][], int row, int col, int dr, int dc, int times, int value)
{
int r = row;
int c = col;
for (int i = 0; i < times; i++)
{
matrix[r][c] = value;
r += dr;
c += dc;
}
}

// Create a matrix with the given size, with values 0...(r*c-1)
private static int[][] createMatrix(int rows, int cols)
{
int matrix[][] = new int[rows][cols];
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
int index = r * cols + c;
matrix[r][c] = index;
}
}
return matrix;
}

}

class FourIdenticalA
{
/*
* This method checks if there are four identical elements in a matrix
* either horizontally, vertically, or diagonally
*/
public static boolean checkForIdenticalFour(int[][] matrix)
{

/* We traverse each element in the matrix */
for (int row = 0; row < matrix.length; row++)
{
for (int col = 0; col < matrix[row].length; col++)
{
// This is the current element in our matrix
int element = matrix[row][col];

/*
* If there are 3 elements remaining to the right of the current
* element's position and the current element equals each of
* them, then return true
*/
if (col <= matrix[row].length - 4
&& element == matrix[row][col + 1]
&& element == matrix[row][col + 2]
&& element == matrix[row][col + 3])
return true;

/*
* If there are 3 elements remaining below the current element's
* position and the current element equals each of them, then
* return true
*/
if (row <= matrix.length - 4 && element == matrix[row + 1][col]
&& element == matrix[row + 2][col]
&& element == matrix[row + 3][col])
{
return true;
}

/*
* If we are in a position in the matrix such that there are
* diagonals remaining to the bottom right of the current
* element, then we check
*/
if (row <= matrix.length - 4 && col <= matrix[row].length - 4)
{
// If the current element equals each element diagonally to
// the bottom right
if (element == matrix[row + 1][col + 1]
&& element == matrix[row + 2][col + 2]
&& element == matrix[row + 3][col + 3])
return true;
}

/*
* If we are in a position in the matrix such that there are
* diagonals remaining to the bottom left of the current
* element, then we check
*/
if (row <= matrix.length - 4 && col >= 3)
{
// If the current element equals each element diagonally to
// the bottom left
if (element == matrix[row + 1][col - 1]
&& element == matrix[row + 2][col - 2]
&& element == matrix[row + 3][col - 3])
return true;
}

}
}

/*
* If all the previous return statements failed, then we found no such
* patterns of four identical elements in this matrix, so we return
* false
*/
return false;
}
}

class FourIdenticalB
{
private static boolean checkRows(int[][] matrix)
{
for (int row = 0; row < matrix.length; row++)
{
for (int col = 0; col < matrix[row].length - 3; col++)
{
int element = matrix[row][col];
if (element == matrix[row][col + 1] &&
element == matrix[row][col + 2] &&
element == matrix[row][col + 3])
{
return true;
}
}
}
return false;
}

private static boolean checkColumns(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 0; col < matrix[row].length; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col] &&
element == matrix[row + 2][col] &&
element == matrix[row + 3][col])
{
return true;
}
}
}
return false;
}

private static boolean checkMainDiagonal(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 0; col < matrix[row].length - 3; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col + 1] &&
element == matrix[row + 2][col + 2] &&
element == matrix[row + 3][col + 3])
{
return true;
}
}
}
return false;
}

private static boolean checkCounterDiagonal(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 3; col < matrix[row].length; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col - 1] &&
element == matrix[row + 2][col - 2] &&
element == matrix[row + 3][col - 3])
{
return true;
}
}
}
return false;
}

public static boolean checkForIdenticalFour(int[][] matrix)
{
return checkRows(matrix) ||
checkColumns(matrix) ||
checkMainDiagonal(matrix) ||
checkCounterDiagonal(matrix);
}
}

class FourIdenticalC
{
public static boolean checkForIdenticalFour(int[][] matrix)
{
int rows = matrix.length;
int cols = matrix[0].length;
int times = 4;

// Check rows, starting at column 0 of each row
for (int r = 0; r < rows; r++)
{
if (check(matrix, r, 0, 0, 1, cols))
{
return true;
}
}

// Check columns, starting at row 0 of each column
for (int c = 0; c < cols; c++)
{
if (check(matrix, 0, c, 1, 0, rows))
{
return true;
}
}

// Check diagonals, starting at column 0 of each row
for (int r = 0; r < rows - times + 1; r++)
{
int steps = Math.min(cols, rows - r);
if (check(matrix, r, 0, 1, 1, steps))
{
return true;
}
}

// Check diagonals, starting at row 0 of each column
for (int c = 0; c < cols - times + 1; c++)
{
int steps = Math.min(rows, cols - c);
if (check(matrix, 0, c, 1, 1, steps))
{
return true;
}
}

// Check counter-diagonals, starting at last column of each row
for (int r = 0; r < rows - times + 1; r++)
{
int steps = Math.min(cols, rows - r);
if (check(matrix, r, cols - 1, 1, -1, steps))
{
return true;
}
}

// Check counter-diagonals, starting at row 0 of each column
for (int c = times - 1; c < cols; c++)
{
int steps = Math.min(rows, c + 1);
if (check(matrix, 0, c, 1, -1, steps))
{
return true;
}
}
return false;
}

private static boolean check(
int matrix[][], int row, int col, int dr, int dc, int steps)
{
int previous = matrix[row][col];
int r = row + dr;
int c = col + dc;
int counter = 1;
for (int i = 1; i < steps; i++)
{
int current = matrix[r][c];
if (current != previous)
{
previous = current;
counter = 1;
}
else
{
counter++;
if (counter == 4)
{
return true;
}
}
r += dr;
c += dc;
}
return false;
}

}

• Woah, thank you so much for this thorough post! I now understand why matrix[row].length-4 doesn't work as intended. Dec 22 '16 at 2:00
• Also, I assume I should hardcode and replace all of the matrix[row].length-4 and matrix.length-4 code snippets with just 3, right? For the same reason? It also seems there's an IndexOutOfBoundsException with a 4-by-4 matrix. Dec 22 '16 at 2:02
• @AleksandrH Only that instance should be changed from matrix[row].length-4 to 3. The reason being that that instance relates to the left edge. The other occurrences relate to the right edge. So the columns count 0, 1, 2, 3 -- needs to be at least 3 to move left 3 and stay in the board. The right edge counts from the last column. In a 7 column board, it can be at most 3 and count up to 6. Similarly, some occurrences should be matrix.length - 4 to avoid dropping off the bottom of the board. Dec 22 '16 at 3:24