Code Fights - boxBlur

README.md

Last night you had to study, but decided to party instead. Now there is a black and white photo of you that is about to go viral. You cannot let this ruin your reputation, so you want to apply box blur algorithm to the photo to hide its content.

The algorithm works as follows: each pixel x in the resulting image has a value equal to the average value of the input image pixels' values from the 3 × 3 square with the center at x. All pixels at the edges are cropped.

As pixel's value is an integer, all fractions should be rounded down.

Example

For

image = [[1, 1, 1], 
         [1, 7, 1], 
         [1, 1, 1]]

the output should be boxBlur(image) = [[1]].

In the given example all boundary pixels were cropped, and the value of the pixel in the middle was obtained as
(1 + 1 + 1 + 1 + 7 + 1 + 1 + 1 + 1) / 9 = 15 / 9 = ~rounded down~ = 1.

Input/Output

• [time limit] 4000ms (py3)

• [input] array.array.integer image

  An image is stored as a rectangular matrix of non-negative integers.

  Guaranteed constraints:

  3 ≤ image.length ≤ 10,
  3 ≤ image[0].length ≤ 10,
  0 ≤ image[i][j] ≤ 255.
  

• [output] array.array.integer

  A blurred image.

box_blur.py

from typing import List


class BoxBlur:
    @classmethod
    def box_blur(cls, image: List[List[int]]) -> List[List[int]]:
        num_rows = len(image)
        num_cols = len(image[0])
        result = []
        for x, row in enumerate(image):
            if x == 0 or x == num_rows - 1:
                continue
            new_row = []
            for y, px in enumerate(row):
                if y == 0 or y == num_cols - 1:
                    continue
                new_row.append(cls._kernel_filter(image, x, y))
            result.append(new_row)
        return result

    @classmethod
    def _kernel_filter(cls, image: List[List[int]], x: int, y: int) -> int:
        cell = image[x][y]
        up = image[x - 1][y]
        up_right = image[x - 1][y + 1]
        right = image[x][y + 1]
        down_right = image[x + 1][y + 1]
        down = image[x + 1][y]
        down_left = image[x + 1][y - 1]
        left = image[x][y - 1]
        up_left = image[x - 1][y - 1]
        sum_val = sum([cell, up, up_right, right, down_right, down, down_left, left, up_left])
        return sum_val // 9

boxBlur.py

def boxBlur(image: list) -> list:
    num_rows = len(image)
    num_cols = len(image[0])
    result = []
    for x, row in enumerate(image):
        if x == 0 or x == num_rows - 1:
            continue
        new_row = []
        for y, px in enumerate(row):
            if y == 0 or y == num_cols - 1:
                continue
            new_row.append(_kernel_filter(image, x, y))
        result.append(new_row)
    return result


def _kernel_filter(image: list, x: int, y: int) -> int:
    cell = image[x][y]
    up = image[x - 1][y]
    up_right = image[x - 1][y + 1]
    right = image[x][y + 1]
    down_right = image[x + 1][y + 1]
    down = image[x + 1][y]
    down_left = image[x + 1][y - 1]
    left = image[x][y - 1]
    up_left = image[x - 1][y - 1]
    sum_val = sum([cell, up, up_right, right, down_right, down, down_left, left, up_left])
    return sum_val // 9

test_box_blur.py

import unittest
from box_blur import BoxBlur


class TestBoxBlur(unittest.TestCase):
    def test_1(self):
        image = [[1, 1, 1],
                 [1, 7, 1],
                 [1, 1, 1]]
        solution = [[1]]
        result = BoxBlur.box_blur(image)
        self.assertEqual(result, solution)

    def test_2(self):
        image = [[0,  18,  9],
                 [27,  9,  0],
                 [81, 63, 45]]
        solution = [[28]]
        result = BoxBlur.box_blur(image)
        self.assertEqual(result, solution)

    def test_3(self):
        image = [[36,  0, 18,  9],
                 [27, 54,  9,  0],
                 [81, 63, 72, 45]]
        solution = [[40, 30]]
        result = BoxBlur.box_blur(image)
        self.assertEqual(result, solution)

    def test_4(self):
        image = [[7,  4,  0,  1],
                 [5,  6,  2,  2],
                 [6, 10,  7,  8],
                 [1,  4,  2,  0]]
        solution = [[5, 4],
                    [4, 4]]
        result = BoxBlur.box_blur(image)
        self.assertEqual(result, solution)

    def test_5(self):
        image = [[36,  0, 18,  9,  9, 45, 27],
                 [27,  0, 54,  9,  0, 63, 90],
                 [81, 63, 72, 45, 18, 27,  0],
                 [0,   0,  9, 81, 27, 18, 45],
                 [45, 45, 27, 27, 90, 81, 72],
                 [45, 18,  9,  0,  9, 18, 45],
                 [27, 81, 36, 63, 63, 72, 81]]
        solution = [[39, 30, 26, 25, 31],
                    [34, 37, 35, 32, 32],
                    [38, 41, 44, 46, 42],
                    [22, 24, 31, 39, 45],
                    [37, 34, 36, 47, 59]]
        result = BoxBlur.box_blur(image)
        self.assertEqual(result, solution)


if __name__ == '__main__':
    unittest.main()