# Find longest sequence horizontally, vertically or diagonally in Connect Four game

I'm new to programming and also to Java and working on problems in Intro to Java by Robert Sedgewick. Here is my question:

Connect Four: Given an N-by-N grid with each cell either occupied by an 'X', an 'O', or empty, write a program to find the longest sequence of consecutive 'X's either horizontal, vertically, or diagonally. To test your program, you can create a random grid where each cell contains an 'X' or 'O' with probability 1/3.

With many modifications, I came up with some code, which I feel is not efficient. Can someone help make my code more efficient?

public class connectfour {

public static void main(String[] args) {

int N=Integer.parseInt(args),t=0;

String[][] a=new String[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
double r=Math.random();
if(r<0.33){a[i][j]="X";t=1;}
else if(r<0.66)a[i][j]="O";
else a[i][j]=".";
System.out.print(a[i][j]+" ");
}
System.out.println();
}

for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(a[i][j]=="X"){
//to check horizontally

for(int y=j,length=1;y<N-1;y++){
if(a[i][y]!=a[i][y+1])break;
length++;
if(t<length) t=length;}
//to check vertically

for(int x=i,length=1;x<N-1;x++)
{if(a[x][j]!=a[x+1][j])
break;
length++;
if(t<length) t=length;}
//to check diagonally ,right and down

for(int x=i,y=j,length=1;x<N-1&&y<N-1;x++,y++)
{ if(a[x][y]!=a[x+1][y+1])
break;
length++;
if(t<length) t=length; }

}
}
}
for(int i=N-1;i>=0;i--){
for(int j=0;j<N-1;j++){
if(a[i][j]=="X"){
//to check diagonally ,right and up

for(int x=i,y=j,length=1;x>0&&y<N-1;x--,y++)
{if(a[x][y]!=a[x-1][y+1])
break;
length++;
if(t<length) t=length;
}
}
}
}

System.out.println("the length of longest sequence of X in the above array: "+t);

}
}


I want to post my improved code according to instructions given above. I implemented the algorithm suggested by Simon André Forsberg. It is working for all cases.

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

int N = Integer.parseInt(args), highestconsecutive = 0;

String   string1,  string2 = "X", string3;

String[][] board = new String[N][N];

for(int i = 0; i < N; i++ )
{
for(int j = 0; j < N; j++ )
{
double r = Math.random();
if( r < 0.33 ) board[i][j] = "X";
else if( r < 0.66 ) board[i][j] = "O";
else board[i][j] = ".";
System.out.print( board[i][j] + " " );
}
System.out.println();
}

//        loopingfor checking horizontally / vertically/diagonally down and right,down and  left

for(int i = 0; i < N; i++ )
{       int consecutive1 = 0, consecutive = 0 ;

for(int j = 0; j < N; j++ )
{
//                for horizontal check
string1 = board[i][j];

if( string1.equals(string2))
consecutive++;
else
consecutive=0;

if( highestconsecutive < consecutive)
highestconsecutive = consecutive;
// for vertical check
string1=board[j][i];

if(string1.equals(string2))
consecutive1++;
else
consecutive1=0;

if( highestconsecutive < consecutive1)
highestconsecutive = consecutive1;

//                    looping for diagonal check ,down and right
for( int x = i, y = j, length = 0; x < N  && y < N ; x++, y++ )

{
string1 = board[x][y];

if(string1.equals(string2))
length++;

else
length=0;

if(highestconsecutive < length)
highestconsecutive = length;
}
//                        looping for diagonal check ,down and left

for( int x = i, y = N - j - 1, length = 0; x < N  && y >= 0 ; x++, y-- )

{
string1 = board[x][y];

if(string1.equals(string2))
length++;

else
length=0;

if(highestconsecutive < length)
highestconsecutive = length;
}

}
}

System.out.println("the length of longest sequence of X in the above array: "+highestconsecutive);

}
}


## 3 Answers

### Introduction

Hi and Welcome to Code Review! There are number of things that you can learn today.

First I would like to say that it is nice that your algorithm works. Thanks for providing a compilable example, that helps a lot.

Now, secondly, I have to disappoint you: I will not simply "give you the better code". I don't really think you would learn so much from that. However, I can help you in figuring out what things needs to be improved in your current code.

# YOUR CODE IS NOT READABLE!

Sorry for shouting but I am very serious. The importance of code readability cannot be emphasized enough. The readability of your code is severely off.

• Indentation: Your indentation is not consistent. Each { should be followed by one extra indentation step, and each } should remove one indentation step.

• Spacing: It seems like you are always using as few spaces as possible. If you are having serious storage problems and are running out of bytes, then... no, I wouldn't understand it even then...

Compare

  else if(r<0.66)a[i][j]="O";


with

  else if(r < 0.66) a[i][j] = "O";


And compare

  for(int x=i,y=j,length=1;x<N-1&&y<N-1;x++,y++)


with

  for (int x = i, y = j, length = 1; x < N - 1 && y < N - 1; x++, y++)


Spacing is good for you. One space after each comma, one after semicolon, one before & after = and &&. Makes things so much readable. OrhowwouldyoulikeitifIwrotemyreviewlikethis,withoutusingspacesatall? (I hope that example made things clear why spacing is good).

Please read up on the Java coding conventions, all these things are mentioned there.

Once you have learned how to improved those, if you are using an IDE such as Eclipse, which I hope that you do - if you are not I really suggest that you download Eclipse now. Press Ctrl + Shift + F in Eclipse to make it format for you. If you are using NetBeans, press Alt + Shift + F.

• Variable names: All (except one) of your variable names is only one character. Try to have self-documenting variable names. What is the variable used for? row and col could be better names than i and j. t could be called maximumFoundLength.

### String comparison

It is more or less pure luck that your code works at all. Thanks to Java only creating one String instance for "X" and such, it works with comparing your Strings with ==. However, if you would have any user input, this wouldn't work. == compares object references, to compare Strings correctly in Java you should use the .equals method. Please see the Stack Overflow question "How do I compare Strings in Java?"

### Limited number of possible values --> Enum

Since the possible values of your board is very limited, you can use an enum instead of a String to store the value of the positions.

public enum BoardValue {
X, O, EMPTY; // _ for empty positions
@Override
public String toString() {
return this == EMPTY ? "." : this.name();
}
}


Now make your String[][] a into BoardValue[][] board, which will make it much better to use in the long run.

### Classes, Methods and Objects

Java is an object-oriented programming language. I think you can learn a lot by reading Oracle's Java Lesson: Classes and Objects. I would suggest that you make your game board into a class. Your current String[][] a=new String[N][N]; should be a field in the class.

This class could then have several methods:

• void randomize(): Randomizes new data in to the board.
• void output(): Print the information to System.out.
• int findConsecutive(String lookingFor): Scan the board for the largest consecutive of the specified String.

### Your algorithm

Your current algorithm works by looping through the entire two-dimensional board and for each position it does the following:

• Remember the value of the current position, we can call this "current"
• Loop through the rest of this row/column/diagonal
• When you encounter a position that is not equal to "current", you break this loop.

This is highly inefficient because you are checking each tile way too many times than you need. Instead, you should treat each row/column/diagonal like an individual line of positions. Consider this algorithm:

• searchingFor is the value you want to search for ("X" or "O")
• Initialize the value consecutive to 0.
• Initialize the value highestConsecutive to 0.
• For each row/column/diagonal, loop through the positions in the line and check for searchingFor
• When you encounter this value, you do the following:
• increase consecutive by 1.
• If consecutive is more than highestConsecutive, set highestConsecutive to the value of consecutive.
• If the value did not match, reset consecutive to 0.
• Once the loop is finished, highestConsecutive is the highest consecutive number for this current row/column/diagonal.

Regarding diagonals, you can loop through those by starting at a position on the edge of the board and do the loop once in a straight diagonal line, like the following. Start at all positions where x=0 or y=0 and loop on each square in a bottom-right manner.

Then to the same for the other direction, you will have to start at x=MAX and y=0 and loop on each square in the bottom-left direction.

One final thing:

When you have improved your code, please come back here and post your improved version (also pointing us to this question).

• thank you sir, i understood my fault ,i was checking each individual many times and able to change for horizontal and vertical checks but finding difficult in checking diagonally. can you be more specific about looping for diagonals? thank you once again sir – user3300600 Feb 17 '14 at 16:04
• @user3300600 Added a little description and a picture on how you could do the diagonal looping. – Simon Forsberg Feb 17 '14 at 17:27
• Insteadofcodinglikethis whyNotTryThis? – Timtech Feb 17 '14 at 23:45

Oh dear. Where do we start?

## Formatting

Formatting is important, because it makes code easier to read. That in turn makes it easier to understand and debug your code. What kind of formatting is recommended? Java has it's own Coding Conventions which you can follow. Here is a short summary of a sensible style which I use:

• Binary operators like + or = are surrounded by a space.
• The opening braces of a block begin on the same line.
• Closing braces always go on a line of their own, and are vertically aligned under the opening keyword.
• Statements inside a block are indented by one level (4 spaces), and for no other reasons.
• Inside a for loop, the semicolons separating the three statements are followed by a space.
• A keyword that takes a condition in parens has a space before and after the parens.
• Corresponding phrases on different lines are vertically aligned to emphasize their connection.

Using these guidelines, a piece of code like

//to check diagonally ,right and down

for(int x=i,y=j,length=1;x<N-1&&y<N-1;x++,y++)
{ if(a[x][y]!=a[x+1][y+1])
break;
length++;
if(t<length) t=length; }


would become

// to check diagonally, right and down
for (int x = i, y = j, length = 1; x < N - 1 && y < N - 1; x++, y++) {
if (a[x][y] != a[x + 1][y + 1]) {
break;
}
length++;
if (t < length) {
t = length;
}
}


This is already much easier to read. If you take care of the “small things” like formatting, it's much more believable that you are also careful with the “big things” like design or algorithms.

# Variable Names

Good variable names are another way to make code easier to understand. While mathematics have the convention that single-letter variable names should be used, this is not the case in modern programming. A variable should convey the meaning of the data. For example, it would be better to call your a what it is: the board. The r could be random, or a roll (as in dice roll). The t is probably meant to be the longestLength.

I will stop right here, because your code isn't otherwise reviewable in it's current state. If you could make that code work, you can surely also make it beautiful.

• thank you amon for your time and suggestions ,surely change my style – user3300600 Feb 17 '14 at 2:59

I'm not a Java programmer, so I won't attempt to mislead you with any specific information. However, I'd really like to address the issues with indentation and whitespace, as a basic thing to writing code. I'll address this using example code.

Please keep your indentation consistent throughout the code. Although you're a beginner, this is something you should be able to do. It helps your code stay clean for yourself and others. It's most common to indent by four spaces.

For instance, when you open curly braces, the following lines (until the closing brace) should be indented so that it looks like the code "belongs" there.

public static void func {
// first line...
// second line...
// n lines...
}


Also, put whitespace between your keywords, operators, operands, and curly braces. It'll help separate them, making it much easier to read them.

Before:

for(i=0;i<10;++i){}


After:

for (i = 0; i < 10; ++i) {}


Combining the points about indentation and whitespace:

public static void func {
for (i = 0; i < 10; ++i) {
for (i = 0; i < 10; ++i) {
int i = 0;
i++;
}
}
}


Also note from this example that the closing braces are on their own lines. This is preferred for any multi-line placement type, although still done for single-line statements. Opening braces, on the other hand, can still be on the same line as the statement.