Problem

This problem is a simplified version of problem 11 on projecteuler.net. Using the provided array find the 4 numbers along a row, column or diagonal with the greatest product. I have included some skeleton code to make problem a little easier.

For example at row 0, column 0 there are three lines to check.
8 x 2 x 22 x 97 = 34144
8 x 49 x 81 x 52 = 1651104
8 x 49 x 31 x 23 = 279496

public class matrix {

	static final int   lineLength = 4;		      //length of line to check 
	static       int[] bestNumbers = new int[lineLength]; //best line found so far
	static       int   bestNumber = 0;                    //product of the best line
	
	static final int array[][] ={ 
		{ 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8},
		{49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0},
		{81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65},
		{52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,36,91},
		{22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
		{24,47,32,60,99, 3,45, 2,44,75,33,53,78,36,84,20,35,17,12,50},
		{32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
		{67,26,20,68, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},
		{24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
		{21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95},
		{78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92},
		{16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57},
		{86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58},
		{19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40},
		{04,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66},
		{88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69},
		{04,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36},
		{20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16},
		{20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54},
		{01,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48} };


	public static void main(String[] args) {

		for( int row = 0; row < array[0].length; row++ )
		{
			for( int col = 0; col < array.length; col++ )
			{
				checkRow( row, col );
				checkCol( row, col );
				checkDiagonal( row, col );
			}
		}

		System.out.println( "WINNER!! " + bestNumber );
		printLine( bestNumbers );

	}
	
	//prints a nice output for a provided line
	public static void printLine( int[] toPrintArray, int toPrintProd )
	{
	}
	
	//calculate the product for the line passed
	//if it the product is better than bestNumber update it
	public static void checkLine( int[] toCheck )
	{
		
	}
	
	//from (row,col) check product of the row
	public static void checkRow( int row, int col )
	{
		int[] tempRow = new int[ 4 ];
		...
		checkLine( tempRow );
	}
	
	//from (row,col) check product of the column
	public static void checkCol( int row, int col )
	{
		int[] tempRow = new int[ 4 ];
		...
		checkLine( tempRow );
	}
	
	//from (row,col) check product of the diagonal
	public static void checkDiagonal( int row, int col )
	{
		int[] tempRow = new int[ 4 ];
		...
		checkLine( tempRow );
	}

}

More with Arrays

Solution

To solve this problem it would be best to start by filling in the printLine method as it is useful in debugging. Given an array and an int this method prints the output like in my example. The main loop here should look a little strange to you. We want to print "x" between the numbers but not at the end. So we will print toPrintArray[ 0 ] first, then add a "x" and the next value in the loop.

//prints a nice output for a provided line
//8 x  2 x 22 x 97 = 34144
public static void printLine( int[] toPrintArray, int toPrintProd )
{
	System.out.print( toPrintArray[ 0 ] );
	
	for( int i = 1; i < toPrintArray.length; i++ )
	{
		System.out.print( " x " + toPrintArray[ i ] );
	}
	
	System.out.println( " = " + toPrintProd );
}

The next step is to fill in checkRow. Given a row and a column in the array

Now that you have list of rows printing you can write checkLine. Manually check a few lines to make sure you are getting the right results. You're almost there, fill in checkCol, checkDiagonal, and verify that you are getting the right answer.

//from (row,col) check product of the row
public static void checkRow( int row, int col )
{
	//make sure the row we are checking does not exceed the array row length
	if( col + lineLength <=  array[0].length )
	{
		int[] tempRow = new int[ 4 ];
		
		for( int i = 0; i < lineLength; i++ )
		{
			tempRow[ i ] = array[ row ][ col + i ];
		}
		
		checkLine( tempRow );
	}
	
}//checkRow

Code

Solution Code

public class matrix {

	static final int   lineLength = 4;		      //length of line to check 
	static       int[] bestNumbers = new int[lineLength]; //best line found so far
	static       int   bestNumber = 0;                    //product of the best line
	
	static final int array[][] ={ 
		{ 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8},
		{49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0},
		{81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65},
		{52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,36,91},
		{22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
		{24,47,32,60,99, 3,45, 2,44,75,33,53,78,36,84,20,35,17,12,50},
		{32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
		{67,26,20,68, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},
		{24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
		{21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95},
		{78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92},
		{16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57},
		{86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58},
		{19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40},
		{04,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66},
		{88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69},
		{04,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36},
		{20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16},
		{20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54},
		{01,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48} };

	public static void main(String[] args) {

		for( int row = 0; row < array[0].length; row++ )
		{
			for( int col = 0; col < array.length; col++ )
			{
				checkRow( row, col );
				checkCol( row, col );
				checkDiagonal( row, col );
			}
		}

		System.out.println( "WINNER!! " + bestNumber );
		printLine( bestNumbers );

	}
	
	//prints a nice output for a provided line
	//8 x  2 x 22 x 97 = 34144
	public static void printLine( int[] toPrintArray, int toPrintProd )
	{
		System.out.print( toPrintArray[ 0 ] );
		
		for( int i = 1; i < toPrintArray.length; i++ )
		{
			System.out.print( " x " + toPrintArray[ i ] );
		}
		
		System.out.println( " = " + toPrintProd );
	}
	
	//calculate the product for the line passed
	//if it the product is better than bestNumber update it
	public static void checkLine( int[] toCheck )
	{
		int tempProduct = 1;
		
		for( int i = 0; i < toCheck.length; i++ )
		{
			tempProduct = tempProduct * toCheck[i];			
		}
		
		if( tempProduct > bestNumber )
		{
			bestNumber = tempProduct;
			bestNumbers = toCheck;
		}
	}
	
	//from (row,col) check product of the row
	public static void checkRow( int row, int col )
	{
		//make sure the row we are checking does not exceed the array row length
		if( col + lineLength <=  array[0].length )
		{
			int[] tempRow = new int[ 4 ];
			
			for( int i = 0; i < lineLength; i++ )
			{
				tempRow[ i ] = array[ row ][ col + i ];
			}
			
			checkLine( tempRow );
		}
		
	}//checkRow
	
	//from (row,col) check product of the column
	public static void checkCol( int row, int col )
	{
		//make sure the column we are checking does not exceed the array column length
		if( row + lineLength <=  array.length )
		{
			int[] tempRow = new int[ 4 ];
			
			for( int i = 0; i < lineLength; i++ )
			{
				tempRow[ i ] = array[ row + i ][ col ];
			}
			
			checkLine( tempRow );
		}
		
	}//checkCol
	
	//from (row,col) check product of the diagonal
	public static void checkDiagonal( int row, int col )
	{
		//for diagonals we need to check row and column
		if( ( row + lineLength <=  array.length ) && (col + lineLength <=  array[0].length) )
		{
			int[] tempRow = new int[ 4 ];
			
			for( int i = 0; i < lineLength; i++ )
			{
				tempRow[ i ] = array[ row + i ][col + i ];
			}
			
			checkLine( tempRow );
		}
		
	}//checkDiagonal
	
}


Output
======
66 x 91 x 88 x 97 = 51267216