Thread: 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.prob11.txt

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

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

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

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

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.

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

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

here's the code:

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.