Tuesday, June 14, 2016

In-place Stencil

Question:
Given a m*n matrix with integers, calculate the average value based on its 8 neighbors. Do it in-place. 

Code (Java):
import java.io.*;
import java.util.*;


public class Solution {
  public void computeAverageInplace(int[][] matrix) {
    if (matrix == null || matrix.length == 0) {
      return;
    }
    
    int m = matrix.length;
    int n = matrix[0].length;
    
    int[][] padMatrix = new int[m + 2][n + 2];
    
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        padMatrix[i + 1][j + 1] = matrix[i][j];
      }
    }
    
    int t1 = 0;
    int t2 = 0;
    
    // step 1: compute the accumulation in row order
    for (int j = 1; j < n + 1; j++) {
      for (int i = 1; i < m + 1; i++) {      
        if (i == 1) {
          t1 = padMatrix[i][j];
          padMatrix[i][j] += padMatrix[i + 1][j];
        } else if (((i - 1) & 1) == 0) {
          if ((i - 1) % 4 == 0) {
            t1 = padMatrix[i][j];
            padMatrix[i][j] = padMatrix[i - 1][j] - t2 + padMatrix[i + 1][j];
          } else {
            t2 = padMatrix[i][j];
            padMatrix[i][j] = padMatrix[i - 1][j] - t1 + padMatrix[i + 1][j];
          }
        } else {
          if ((i - 1) % 4 == 1) {
            padMatrix[i][j] += t1 + padMatrix[i + 1][j];
          } else {
            padMatrix[i][j] += t2 + padMatrix[i + 1][j];
          }
        }
      }
    }
    
    // step 2: compute the accumatlion in col order
    for (int i = 1; i < m + 1; i++) {      
      for (int j = 1; j < n + 1; j++) {
        if (j == 1) {
          t1 = padMatrix[i][j];
          padMatrix[i][j] += padMatrix[i][j + 1];
        } else if (((j - 1) & 1) == 0) {
          if ((j - 1) % 4 == 0) {
            t1 = padMatrix[i][j];
            padMatrix[i][j] = padMatrix[i][j - 1] - t2 + padMatrix[i][j + 1];
          } else {
            t2 = padMatrix[i][j];
            padMatrix[i][j] = padMatrix[i][j - 1] - t1 + padMatrix[i][j + 1];
          }
        } else {
          if ((j - 1) % 4 == 1) {
            padMatrix[i][j] += t1 + padMatrix[i][j + 1];
          } else {
            padMatrix[i][j] += t2 + padMatrix[i][j + 1];
          }
        }
      }
    }
    
    // Copy the padMatrix back to matrix
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        matrix[i][j] = padMatrix[i + 1][j + 1];
      }
    }
  }
  
  public int[][] computeAverageOutOfPlace(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    
    int[][] padMatrix = new int[m + 2][n + 2];
    
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        padMatrix[i + 1][j + 1] = matrix[i][j];
      }
    }
    
    int[][] result = new int[m][n];
    
    for (int i = 1; i < m + 1; i++) {
      for (int j = 1; j < n + 1; j++) {
        for (int p = i - 1; p <= i + 1; p++) {
          for (int q = j - 1; q <= j + 1; q++) {
            result[i - 1][j - 1] += padMatrix[p][q];
          }
        }
      }
    }
    
    return result;
  }
  
  public static void main(String[] args) {
    Solution sol = new Solution();
    
    int m = 17;
    int n = 20;
    int[][] matrix = new int[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        matrix[i][j] = (i * j) % 10;
      }
    }
    
    int[][] outOfPlace = sol.computeAverageOutOfPlace(matrix);
    
    System.out.println("Out of place result: ");
    for (int[] rows : outOfPlace) {
      for (int e : rows) {
        System.out.print(e + " ");
      }
      
      System.out.println("");
    }
    
    System.out.println("");
    System.out.println("In place result: ");
    sol.computeAverageInplace(matrix);
    
    for (int[] rows : matrix) {
      for (int e : rows) {
        System.out.print(e + " ");
      }
      
      System.out.println("");
    }
  }
}


No comments:

Post a Comment