1 Attachment(s)

Help with looking through a two-dimensional array.

Hi there, I'm working on a problem that involves finding a largest product of any 4 consecutive numbers in a grid. I don't want the answer to the question, but I can't figure out how to search through the 2-d array diagonally both down to the left and down to the right incrementally by 4s. I don't have any code because I can't figure out how to code an algorithm to sort through. I can figure out how to search diagonally without a increment, but with one, I do not now.

I'll attach the text file I'm feeding into the array.Attachment 1266

Re: Help with looking through a two-dimensional array.

Quote:

how to search through the 2-d array diagonally both down to the left and down to the right incrementally by 4s.

Perhaps drawing a grid and labeling the squares with their row/column indexes would show you how the row and column values change as you go from square to square in a diagonal direction.

Re: Help with looking through a two-dimensional array.

I understand how it flows, for example:

0,0 0,1 0,2 0,3 0,4

1,0 1,1 1,2 1,3 1,4

2,0 2,1 2,2 2,3 2,4

3,0 3,1 3,2 3,3 3,4

4,0 4,1 4,2 4,3 4,4

I just don't understand how I could write an algorithm to do

Re: Help with looking through a two-dimensional array.

How many starting locations have a path through 4 other squares?

Re: Help with looking through a two-dimensional array.

in a 20x20 grid, there would be about 256 possible start locations going one direction.

Re: Help with looking through a two-dimensional array.

Ok, you posted a 4x4 grid. The logic would be the same. What are the changes in row and column for down & left and what are the changes for down & right?

Re: Help with looking through a two-dimensional array.

I understand the changes, as y goes down, x goes up, and vice versa. I just dont know how to code it.

Re: Help with looking through a two-dimensional array.

Add one to row to go down.

Add one to column to go right.

Subtract one from column to go left.

In all cases: Test if past bounds of array.

Re: Help with looking through a two-dimensional array.

Ok, that makes sense, but what about the other part of my question, how would I do it in increments of fours?

Re: Help with looking through a two-dimensional array.

Are you asking how to add 4 to a number instead of adding one?

row 0, row 4, row 8, row 12 etc

Re: Help with looking through a two-dimensional array.

The problem is asking for the greatest product of any four consecutive numbers in a grid. I have the numbers posted in a file above so you can tinker with a program. Increments of four meaning for example:

1 2 3 4 5 6 7 8 9

1*2*3*4

then

2*3*4*5

then

3*4*5*6

and so on. Let's consider it diagonally, which is where I need the help.

so something like this diagonal:

1 2 3 4 5 6 [7] 8 9

1 2 3 4 5 [6] 7 8 9

1 2 3 4 [5] 6 7 8 9

1 2 3 [4] 5 6 7 8 9

1 2 [3] 4 5 6 7 8 9

1 [2] 3 4 5 6 7 8 9

[1] 2 3 4 5 6 7 8 9

7*6*5*4

then

6*5*4*3

then

5*4*3*2

and so one. I don't know how to write code to solve that aspect of the problem. That's also why I gave the text file with all the inputs for the 2-d array.

Re: Help with looking through a two-dimensional array.

same thing with vertically, but horizontally and vertically are easy to code.

Re: Help with looking through a two-dimensional array.

Quote:

Originally Posted by

**aesguitar**
same thing with vertically, but horizontally and vertically are easy to code.

If I understand the problem correctly...and making the vertical (or horizontal) is easy, then why not make the diagonal vertical. In the example in post #11, shift each row +1 and calculate the vertical - when diagonal down to the right, shift each row by -1 and calculate the vertical. You can do this by copying the underlying data and physically shift each row, or think hard about how you can do so by modifying your loops to analyze diagonals.

Re: Help with looking through a two-dimensional array.

What does this mean:** in increments of fours?** Your example looks like it takes 4 adjacent numbers, not every 4th number.

Start at the top left, get the 4 numbers down left first and then the four numbers down right. Then move to the next column to the right and do it again until the end of the columns

Then move to the next row's first column and continue until done.

Many tests will fail because there are not 4 numbers in that direction. For example there are none for down left from the top left corner.

Re: Help with looking through a two-dimensional array.

I've actually figure out how I'm going to do the diagonals now.

here's the code:

Code java:

package stuff;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
import algorithms.StopWatch;
public class tester
{
public static void main(String args[]) throws FileNotFoundException {
StopWatch timer = new StopWatch();
timer.start();
ArrayList<Integer> prods = new ArrayList<Integer>();
int[][] nums = new int[20][20];
Scanner in = new Scanner(new File("prob11.txt"));
for(int i = 0; i < 20; i++)
{
for(int j = 0; j < 20; j++)
{
nums[i][j] = in.nextInt();
}
}
//horizontal products
for(int i = 0; i<20;i++)
{
for(int j = 0; j < 17; j++)
{
int prod = 1;
for(int l = j; l < j + 4; l++ )
{
prod*=nums[i][l];
}
prods.add(prod);
}
}
//vertical products
for(int i = 0; i<20;i++)
{
for(int j = 0; j < 17; j++)
{
int prod = 1;
for(int l = j; l < j + 4; l++ )
{
prod*=nums[l][i];
}
prods.add(prod);
}
}
//diagonal down-left products
for(int i = 0; i < 17; i++)
{
for(int j = 3; j < 20; j++)
{
int prod = nums[i][j]*nums[i+1][j-1]*nums[i+2][j-2]*nums[i+3][j-3];
prods.add(prod);
}
}
//diagonal down-right
for(int i = 0; i < 17; i++)
{
for(int j = 0; j < 17; j++)
{
int prod = nums[i][j]*nums[i+1][j+1]*nums[i+2][j+2]*nums[i+3][j+3];
prods.add(prod);
}
}
//gets the largest product in the arraylist
int largest = 0;
for(int i : prods)
{
if(i>largest)
{
largest=i;
}
}
System.out.println(largest);
timer.stop();
System.out.println("\n" + timer.getElapsedTime());
}
}

Don't worry about the stopwatch stuff, it only times how long it takes, about 50ms.