Java - Algorithm for finding the most related numbers

Question

I have a problem, but I can not find anyone else who tried to accomplish a similar task. I have a grid of numbers in the grid of an array int [] []

  2 5 1 0 8 0 8
 2 1 0 9 7 2 4
 3 6 2 3 4 9 7
 3 3 3 4 7 8 9
 3 3 1 2 3 1 4
 9 7 4 1 2 3 4 

I need a simple algorithm to find where the most numbers are connected, only up, down, left and right. So, in the above example, he will find 3 in the index [2] [0].

I know that the problem can be solved by simply executing if statement and loop after loop, but that would be very repetitive, but I was wondering if there is an easier way to do this?

Any help is appreciated, this is for the game I am creating. Thanks:)

EDIT: to help fix this issue.

  2 5 1 0 8 0 8
 2 1 0 9 7 2 4
 3 6 2 3 4 9 7
 3 3 3 4 7 8 9
 3 3 1 2 3 1 4
 9 7 4 1 2 3 4 

the method will return 0.2 as an answer, because it will find that

  3
 3 3 3
 3 3 

has the most adjacent numbers

another example,

  2 5 1 0 8 0 8
 2 1 0 9 7 2 4
 3 3 3 3 4 6 7
 1 0 3 4 7 4 9
 3 3 3 2 3 1 6
 9 7 4 1 8 4 6 

a complete find would be

  3 3 3 3
     3
 3 3 3 

Thanks for all the answers so far, the depth search looks interesting, but you can still find information on the search in the style of a tree.

Answer 1

Perhaps something like this will work with small settings. I myself did not run it, but the concept should be clear. It can also be optimized since the same spaces can be evaluated several times.

public class FindConsecutiveNumbersInGrid { public static int[][] grid = new int[][]{ {2, 5, 1, 0, 8, 0, 8}, {2, 1, 0, 9, 7, 2, 4}, {3, 3, 3, 3, 4, 6, 7}, {1, 0, 3, 4, 7, 4, 9}, {3, 3, 3, 2, 3, 1, 6}, {9, 7, 4, 1, 8, 4, 6} }; public static void main(String[] args) { int maxFound = 0; int[] maxFoundPos = new int[2]; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { boolean[][] foundGrid = new boolean[grid.length][grid[0].length]; findConsecutive(i, j, foundGrid); int found = getFound(foundGrid); if (found > maxFound) { maxFound = found; maxFoundPos[0] = i; maxFoundPos[1] = j; } } } System.out.println(maxFoundPos[0] + " " + maxFoundPos[1]); } public static void findConsecutive(int i, int j, boolean[][] foundGrid) { foundGrid[i][j] = true; if (i < grid.length - 1 && grid[i][j] == grid[i+1][j] && !foundGrid[i+1][j]) { findConsecutive(i+1, j, foundGrid); } if (i > 0 && grid[i][j] == grid[i-1][j] && !foundGrid[i-1][j]) { findConsecutive(i-1, j, foundGrid); } if (j < grid[i].length - 1 && grid[i][j] == grid[i][j+1] && !foundGrid[i][j+1]) { findConsecutive(i, j+1, foundGrid); } if (j > 0 && grid[i][j] == grid[i][j-1] && !foundGrid[i][j-1]) { findConsecutive(i, j-1, foundGrid); } } public static int getFound(boolean[][] foundGrid) { int found = 0; for (boolean[] foundRow : foundGrid) { for (boolean foundSpace : foundRow) { if (foundSpace) found++; } } return found; } 

}

Correctly printed "2 0".

Answer 2

in fact you want to find all related components . BFS and DFS are a well-known algorithm about this. And for this problem you can use DFS . You also assume that for each number you have a vertex. And this peak is connected only up, down, left and right, so that their numbers are equal. Repeat DFS until the entire vertex returns. Now find the component that it has the maximum number in this graph.

Answer 3

If you just want the largest flood area, then you can use the standard fill fill algorithm by counting the number of nodes you fill, filling them with a value that indicates that they should not be visited again. This will be O(n 2 ) for the nxn array, which should be optimal.

If you need the longest sequence, and not the largest region, you will have to look for the longest Hamiltonian path within each fill region. Unfortunately, you are out of luck, according to Hamilton Paths in Grid Charts (1982) Alon Itai, Christos H. Papadimitriou and Jame Louis Szwarcfiter. I could not find the version without paid access, but the abstract text is clear enough. (Of course, the fact that the NP-complete problem does not mean that it is unsolvable. Maybe your N is small enough to make it practical.)

Answer 4

I need a simple algorithm to find where there are the most consecutive numbers connected down and to the right.

A simple algorithm is a row and column loop that looks for the longest sequence down and to the right.

Since you only need the first entry, you do not need to look left or up.

You can break the loops when you get indexes that are smaller than the longest row found. In other words, once you find a 3-character row, you do not need to scroll the last two columns and the last two rows.

However, it is almost as fast and much easier to skip the entire matrix.

In your example, you will find two lines of 3 triples, one in (2,0) and one in (3,0). You would answer with the first answer as your final answer.

Answer 5

You can state this as a dynamic programming problem.

Calculate the number of adjacent paths that increase path [i] [j] = 1 for all i, j

 for i=0;i<n for j=0;j<n for dirx, diry in [(1,0),(0,1) ... etc ... ] if arr[i+dirx][j+diry] = arr[i][j] + 1 path[i+dirx][j+diry] += path[i][j] 

The answer will be max(path[i][j]) for all i, j.

Or recursively if you prefer

  for i,j<n go(i,j) def go(i,j) if path[i][j]>0 return path[i][j] ret = 1; for dirx, diry in [(1,0),(0,1) ... etc ... ] if arr[i+dirx][j+diry] = arr[i][j] + 1 ret = max(ret, go(i+dirx,j+diry)) return ret 

Answer 6

First find the unused cell and start the recursion. disclaimer: this is not java, but pseudo C without most declarations and headers. C is in any case much easier to convert to java ... Use a global or class member to count, if necessary.

To make things simpler, combine an N * N array with protective devices.

  // with -1 -1 -1 -1 // -1 xx -1 // -1 -1 -1 -1 for (i=N+2;i<(N+2)*(N+1);i++) { // exact starting and ending locations are disclosed if (k=array[i]!=-1) { j=1; flood_fill(array,i,k,&j); if (j>max) { max=j; max_number=k; } } } #define UP -(N+2) #define DOWN (N+2) #define LEFT -1 #define RIGHT 1 int flood_fill(int *array, int position, int value_to_compare, int *count) { // for each direction UP,DOWN,RIGHT,LEFT static const int directions[4]={UP,DOWN,RIGHT,LEFT]; int t; for (t=0;t<4;t++) if (array[position + directions[t]]==value_to_compare) { array[position + directions[t]] = -1; *count+=1; flood_fill(array, position+directions[t], value_to_compare, count); } }