Difference between revisions of "2D array problem"
From CompSciWiki
| Line 1: | Line 1: | ||
{{1010PrAD|ProblemName=Editing 2D matrix problem | {{1010PrAD|ProblemName=Editing 2D matrix problem | ||
| − | |Problem= This problem is a simplified version of problem 11 on projecteuler.net. Using the provided array find | + | |Problem= This problem is a simplified version of problem 11 on projecteuler.net. Using the provided array find 4 adjacent numbers along any row, column or diagonal with the greatest product. To keep things simple we will only worry about rows going from left-right, columns going top-bottom, and diagonals going right-down. 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.<br> | For example at row 0, column 0 there are three lines to check.<br> | ||
| Line 52: | Line 52: | ||
} | } | ||
| − | + | printLine( bestNumbers, bestNumber ); | |
| − | printLine( bestNumbers ); | + | |
} | } | ||
| Line 102: | Line 101: | ||
|Solution= | |Solution= | ||
| + | First a quick overview of how we are going to solve this. The main body of the program reads a lot like the description of the problem. The two for loops scan the array, and at each cell we check the row, column and diagonal. | ||
| + | <pre> | ||
| + | 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 ); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | printLine( bestNumbers, bestNumber ); | ||
| + | } | ||
| + | </pre> | ||
| + | |||
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. | 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. | ||
| Line 120: | Line 137: | ||
</pre> | </pre> | ||
| − | + | With printing out of the way the next method to write is checkLine. This method checks if a set of numbers is the new highest. The current highest set of number and their product is store in bestNumbers and bestNumber. Manually check a few lines to make sure you are getting the right results. | |
| + | <pre> | ||
| + | static int[] bestNumbers = new int[lineLength]; | ||
| + | static int bestNumber = 0; | ||
| + | |||
| + | 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; | ||
| + | } | ||
| + | } | ||
| + | </pre> | ||
| + | |||
| + | |||
| + | |||
| + | |||
| − | + | The only things left are checkRow, checkCol and checkDiagonal. These three methods are very similar. checkRow copies lineLength<4> numbers from the row and column provided. Next checkRow passes the resulting array to to checkLine to see if we have a new winner. | |
<pre> | <pre> | ||
//from (row,col) check product of the row | //from (row,col) check product of the row | ||
| Line 141: | Line 182: | ||
}//checkRow | }//checkRow | ||
| − | |||
</pre> | </pre> | ||
| + | |||
| + | You're almost there, fill in checkCol, checkDiagonal, and verify that you are getting the right answer.<br> | ||
| + | |||
| Line 190: | Line 233: | ||
} | } | ||
| − | + | printLine( bestNumbers, bestNumber ); | |
| − | printLine( bestNumbers ); | + | |
} | } | ||
Revision as of 02:49, 9 April 2010
Back to the Program-A-Day homepage
ProblemThis problem is a simplified version of problem 11 on projecteuler.net. Using the provided array find 4 adjacent numbers along any row, column or diagonal with the greatest product. To keep things simple we will only worry about rows going from left-right, columns going top-bottom, and diagonals going right-down. 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.
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 );
}
}
printLine( bestNumbers, bestNumber );
}
//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
| |
|---|---|---|
SolutionFirst a quick overview of how we are going to solve this. The main body of the program reads a lot like the description of the problem. The two for loops scan the array, and at each cell we check the row, column and diagonal.
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 );
}
}
printLine( bestNumbers, bestNumber );
}
//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 );
}
With printing out of the way the next method to write is checkLine. This method checks if a set of numbers is the new highest. The current highest set of number and their product is store in bestNumbers and bestNumber. Manually check a few lines to make sure you are getting the right results.
static int[] bestNumbers = new int[lineLength];
static int bestNumber = 0;
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;
}
}
The only things left are checkRow, checkCol and checkDiagonal. These three methods are very similar. checkRow copies lineLength<4> numbers from the row and column provided. Next checkRow passes the resulting array to to checkLine to see if we have a new winner.
//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
You're almost there, fill in checkCol, checkDiagonal, and verify that you are getting the right answer. | ||
Code | ||
