Replace the pattern in the 2d array with another pattern

Question

I am trying to write a method that does the following: Replace each occurrence of array A with array B, where A is inside the 2D array C, then return the modified array. A, B and C are two-dimensional arrays of integers.

For a rectangular array c and another rectangular array a with dimensions a <= from c, find the first occurrence of the sub-array c that matches a, and replace this submatrix with b (which should have the same dimensions as a).

public class ReplacePatterns { public static void main(String[] args){ } //replace every instance of the pattern a with the pattern b inside c. //find a way to get the dimensions of a 2D array public static int[][] replacePattern(int[][] a, int[][] b, int[][] c){ for(int i = 0; i < c.length; i++){ for(int j = 0; j < c[0].length; j++){ if(c[i][j] == a[i][j]){ //c[i][j] should match up with a[0][0]. int[][] d; //copy the array inside c to d. } } } } } 

Answer 1

So, assuming I understood the question correctly, you want something like this:

 public class ReplacePatterns { //replace every instance of the pattern a with the pattern b inside c. //find a way to get the dimensions of a 2D array public static int[][] replace(int[][] a, int[][] b, int[][] c){ for(int i = 0; i < c.length; i++){ for(int j = 0; j < c[0].length; j++){ if(c[i][j] == a[0][0]){ //c[i][j] should match up with a[0][0]. // Start verifying the rest of A boolean flag = true; for (int k = 0; k < a.length; k++) { for (int l = 0; l < a[k].length; l++) { if ((i+k) >= c.length || (j+l) >= c[0].length) { flag = false; break; } if (c[i+k][j+l] != a[k][l]) { flag = false; } } } // If all the values for A were exactly the same, then replace it all with whatever is in B if (flag) { for (int k = 0; k < a.length; k++) { for (int l = 0; l < a[k].length; l++) { c[i+k][j+l] = b[k][l]; } } } } } } return c; } public static String prettyPrint(int[][] c) { StringBuilder sb = new StringBuilder(); for(int i = 0; i < c.length; i++){ for(int j = 0; j < c[0].length; j++){ sb.append("[" + c[i][j] + "]"); } sb.append("\n"); } sb.append("\n"); return sb.toString(); } public static void test(int[][] patternA, int[][] patternB, int[][] patternC) { System.out.println("Pattern A:"); System.out.println(prettyPrint(patternA)); System.out.println("Pattern B:"); System.out.println(prettyPrint(patternB)); System.out.println(" Array C:"); System.out.println(prettyPrint(patternC)); int[][] result = ReplacePatterns.replace(patternA, patternB, patternC); System.out.println(" Result:"); System.out.println(prettyPrint(result)); } public static void main(String[] args){ int[][] patternA, patternB, patternC; System.out.println("Test1:"); patternA = new int[][]{{1,1}, {1,1}}; patternB = new int[][]{{3,3}, {3,3}}; patternC = new int[][]{{0,1,1,1}, {1,1,1,1}, {0,1,1,1}}; test(patternA, patternB, patternC); System.out.println("Test2:"); patternA = new int[][]{{1,1}, {1,1}}; patternB = new int[][]{{5,6}, {7,8}}; patternC = new int[][]{{0,1,1,1,0,1}, {1,1,1,0,1,1,1}, {0,1,1,1,1,1,1}}; test(patternA, patternB, patternC); } } 

I even included two tests there to confirm, but I'm sure it will work in the general case. It is probably inefficient and might not work for huge arrays, but in this case it does its job.

The program displays graphically three preset patterns (A, B and C) and displays how C looks after replacement. In the second test run, you should see something like this:

 Test2: Pattern A: [1][1] [1][1] Pattern B: [5][6] [7][8] Array C: [0][1][1][1][0][1] [1][1][1][0][1][1] [0][1][1][1][1][1] Result: [0][5][6][1][0][1] [1][7][8][0][5][6] [0][1][1][1][7][8] 

Answer 2

One solution is shown below. Please note that I did not think about optimizing the code to minimize template validation. I am sure that there is a better template search algorithm. I took a naive approach to checking the template on each node. Notes inside the code.

 //replace every instance of the pattern a with the pattern b inside c. //find a way to get the dimensions of a 2D array public int[][] replacePattern(int[][] a, int[][] b, int[][] c) { //first make d as copy of array c int[][] d = new int[c.length][c[0].length]; for (int i = 0; i < c.length; i++) { for (int j = 0; j < c[0].length; j++) { d[i][j] = c[i][j]; } } //now scan array c for appearance of a. go over every node and on each node initiate a check if the pattern happens at that node //note the scan is done as long as we don't step out of array c dimensions for (int i = 0; i < c.length - a.length + 1; i++) { for (int j = 0; j < c[0].length - a[0].length + 1; j++) { //we verify pattern on each node as it can start on each of them boolean isPatternOcurring = true; for (int m = 0; m < a.length && isPatternOcurring; m++) { for (int n = 0; j < a[0].length; n++) { if (c[i + m][j + n] != a[m][n]) { isPatternOcurring = false; break; } } } //if pattern occurs, then copy b into d if (isPatternOcurring) { for (int m = 0; m < b.length; m++) for (int n = 0; j < b[0].length; n++) d[i + m][j + n] = b[m][n]; } } } return d; }