## Wednesday, June 15, 2016

### Buttercola: In-place Stencil

Buttercola: In-place Stencil
Given a m*n matrix with integers, calculate the average value based on its 8 neighbors. Do it in-place.
`  ``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(``""``);`
`    ``}`
`  ``}`