from functools import reduce

# Generates all valid rectangles that have a lower left hand corner in i and j
def validRectanglesFrom(grid, i, j):
    result = []
    w = 1
    while i + w <= len(grid) and grid[i + w - 1][j] == 1:
        h = 1
        row_is_valid = True
        while j + h <= len(grid[i + w - 1]) and row_is_valid:
            for k in range(i, i + w):
                if grid[k][j + h - 1] == 0:
                    row_is_valid = False
                    break
            if row_is_valid:
                result.append((i, j, w, h))
            h = h + 1
        w = w + 1
    return result

def left_edge_is_internal(grid, i, j):
    return i > 0 and grid[i - 1][j] == 1 and grid[i][j] == 1

def right_edge_is_internal(grid, i, j):
    return i < len(grid) - 1 and grid[i][j] == 1 and grid[i + 1][j] == 1

def bottom_edge_is_internal(grid, i, j):
    return j > 0 and grid[i][j - 1] == 1 and grid[i][j] == 1

def top_edge_is_internal(grid, i, j):
    return j < len(grid[i]) - 1 and grid[i][j] == 1 and grid[i][j + 1] == 1

def bottom_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda i: bottom_edge_is_internal(grid, i, rect[1]),
                    range(rect[0], rect[0] + rect[2])
                )
            )
        )
    )

def top_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda i: top_edge_is_internal(grid, i, rect[1] + rect[3] - 1),
                    range(rect[0], rect[0] + rect[2])
                )
            )
        )
    )

def left_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda j: left_edge_is_internal(grid, rect[0], j),
                    range(rect[1], rect[1] + rect[3])
                )
            )
        )
    )

def right_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda j: right_edge_is_internal(grid, rect[0] + rect[2] - 1, j),
                    range(rect[1], rect[1] + rect[3])
                )
            )
        )
    )

def boundary_penalty(grid, rect):
    return (
        bottom_boundary_penalty(grid, rect) +
        top_boundary_penalty(grid, rect) +
        left_boundary_penalty(grid, rect) +
        right_boundary_penalty(grid, rect)
    )

def internal_grid_edges(rect):
    return ((rect[2] - 1) * rect[3]) + (rect[2] * (rect[3] - 1))

def quality(grid, rect):
    return internal_grid_edges(rect) - boundary_penalty(grid, rect)

# This destroys your grid, so if you don't want that, clone it first
def get_rectangles(grid):
    result = []
    grid_locations = [(i, j) for i in range(0, len(grid)) for j in range(0, len(grid[i]))]
    unfilled = {cell for cell in grid_locations if grid[cell[0]][cell[1]] == 1}
    while len(unfilled) > 0:
        rects = [rect for cell in unfilled for rect in validRectanglesFrom(grid, cell[0], cell[1])]
        qualityScores = list(map(lambda rect: quality(grid, rect), rects))
        bestRectIdx = reduce(lambda i, j: i if qualityScores[i] > qualityScores[j] else j, range(len(qualityScores)))
        bestRect = rects[bestRectIdx]
        result.append(bestRect)
        for i in range(bestRect[0], bestRect[0] + bestRect[2]):
            for j in range(bestRect[1], bestRect[1] + bestRect[3]):
                unfilled.remove((i,j))
    return result

grid = [[1, 1, 1], [0, 1, 0], [0, 1, 1], [0, 1, 0]]
get_rectangles(grid)