Homework 02: House Remains Detection

The Mesoamerican Research Center at the University of California launched project where large amount of public aerial photographs are automatically processed by computer in attempt to detect possible Mayan culture archaeological sites which are currently unknown.
Wall remains under the surface can be detected using aerial photography, because stone structures hidden under the surface cause contrasting crop color in that area.

Images were already preprocessed. Areas with contrasting crop color (possible wall remains) are marked by 1. Rest of the image contains zeros. Images are oriented regarding cardinal directions so there is north at the top of the image and west on the left side of the image.

Next step is to detect and count house remains found in the image. House remaining has rectangular shape and consists of four walls. Notice that Mayans were building houses oriented regarding cardinal directions, thus all walls are oriented only in north-south or east-west direction. Each wall consists of pixels with value 1. Wall has exactly 1 pixel width and its length has to be at least 4 pixels. Pixel in the corner of a house is considered part of both walls that join in the corner. All pixels surrounded by walls forming a house remaining have to contain zeros only. Additionally, each pixel that is adjacent (horizontally, vertically or diagonally) to house remaining walls have to contain zeros only.

Because the detection method is not perfect, it was decided that also structures which can be changed into house remaining by changing exactly one pixel value will be counted separately. Such structures are called possible house remains.

Image 1: Example of input image. Pixel values are 0 or 1. There is one house remain with walls highlighted in green and three possible house remains highlighted by blue color. Each possible house remain could be turned into house remain by changing value (from 0 to 1 or vice versa) of pixel highlighted in red color. All pixels with value 1 which are not part of house remain or of possible house remain are yellow. Notice that rectangle in upper left part of the image is not house remain as it is too small and its walls in north-south direction do not meet criteria for minimum wall length (4 pixels).

Image 2: Two additional examples of input images. All pixels with value 1 are highlighted by the colors with the same meaning as in Image 1, except for the red color which is not used here. In example a) there are no house remains and there are two possible house remains. Example b) shows one house remain and no possible house remains.

The task

Create file main.py containing function find_solution. This function will take matrix as input parameter. Count the number of house remains and the number of possible house remains in the image and return those two numbers as a tuple.

Examples

Additional examples are shown bellow. Notice that in those examples input is not represented as Python 2D array (matrix). This is just for simplicity. Input provided by automatic evaluation will be Python matrix as shown in Starter Code bellow.

Example 1

Input

00000000000010111000
00111100000010001000
00100100000011111000
00111100000000000000
00000000000000000000
00000000001101111100
11111100000001000100
10000100000001010100
10000100000001000100
11111100000001111100
00000010111100000000
00000000100100000000
00000000100100000000
00000000111100000000

Output

(1, 2)

Example 2

Input

011111100000000
010000100111000
010000100101010
011111100101010
000000000111011
111011100000000
111000000000000
111001111100000
000001000100000
000001000100000
000001111100000

Output

(2, 0)

Example 3

Input

1111100000000000000000110
1000000000010011110000101
0011111110000010000000111
0010000010011110000110000
0010010010000000001010000
0010000010001110001010000
0011111110001110001010000
0000000000001110001110000
0000011100000000000000000
0000000000000111110000000
0001111001000100010001000
0001001000000111110000000
0001001000000001000011111
0001111000111111000100001
0000000000000010000100001
0000011000000000000111111

Output

(1, 2)

Starter Code

Below is a basic code structure you can use. Copy-paste the following code and complete the find_solution function according to the description above. Then submit your final main.py.

def find_solution(matrix):
    """
    >>> terrain_img = [
    ... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0],
    ... [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
    ... [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
    ... [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    ... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    ... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0],
    ... [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0],
    ... [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0],
    ... [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0],
    ... [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0],
    ... [0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    ... [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    ... [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    ... [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
    ... ]
    >>> find_solution(terrain_img)
    (1, 2)
    """
    pass