Difference between revisions of "2D matrix problem"
From CompSciWiki
| Line 108: | Line 108: | ||
public static void checkRow( int row, int col ) | public static void checkRow( int row, int col ) | ||
{ | { | ||
| − | //make sure | + | //make sure the row we are checking does not exceed the array row length |
if( col + lineLength <= array[0].length ) | if( col + lineLength <= array[0].length ) | ||
{ | { | ||
| Line 206: | Line 206: | ||
public static void checkRow( int row, int col ) | 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 ) | if( col + lineLength <= array[0].length ) | ||
{ | { | ||
| Line 223: | Line 224: | ||
public static void checkCol( int row, int col ) | 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 ) | if( row + lineLength <= array.length ) | ||
{ | { | ||
| Line 240: | Line 242: | ||
public static void checkDiagonal( int row, int col ) | 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) ) | if( ( row + lineLength <= array.length ) && (col + lineLength <= array[0].length) ) | ||
{ | { | ||
Revision as of 01:55, 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 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.
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[] toPrint )
{
}
//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
| |
|---|---|---|
SolutionTo solve this problem it would be best to start by filling in the printLine method as it is useful in debugging. Once that is working the next step is to fill in checkRow.
//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
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. | ||
Code | ||
