Squares in the mosaic

A conservator surveys a mosaic floor laid on a square grid. Some cells still hold their tesserae, some are bare, and the survey wants a count of the intact squares of every size.

The problem

The floor is a grid of rows by cols cells. A cell holds 1 if it is intact and 0 if the tesserae are gone. A square patch of side s is intact when all s * s cells inside it are intact. Two patches count separately if they sit at different positions, even if they overlap, and a single intact cell is a patch of side 1.

Count every intact square patch on the floor, of every side length.

Input. tiles — a list of rows, each a list of 0 and 1.

Output. The number of intact square patches, counting all sides and all positions.

Example.

tiles = [[1, 1, 0, 1],
         [1, 1, 1, 1],
         [0, 1, 1, 1]]   ->  13

Ten cells are intact, giving ten patches of side 1. Three patches of side 2 sit entirely on intact ground: the block in the top-left corner and two more in the bottom-right. Nothing of side 3 survives, so 10 + 3.

Example, an undamaged floor:

tiles = [[1, 1, 1],
         [1, 1, 1],
         [1, 1, 1]]   ->  14

Nine patches of side 1, four of side 2, one of side 3.

Constraints.

• 1 <= rows, cols <= 300
• every cell is 0 or 1

Hints

Approach

Brute force

For every cell and every side, check the whole square. On a 300 by 300 floor that is 90000 corners, up to 300 sides each, and up to 90000 cells to read per check — around 10^12 reads. Prefix sums cut the check to constant time and still leave 27 million side tests.

The insight

The number of intact squares cornered at a cell equals the side of the largest one, and that side is one more than the smallest side at its north, west and north-west neighbours.

Sides nest: if a square of side s fits with its corner here, shrinking it by one row and one column leaves a square of side s - 1 that also fits. So the sides available at a cell are exactly 1, 2, ... , largest, and counting them is reading one number. The neighbour rule holds because a square of side s here contains a square of side s - 1 at each of those three cells, so it cannot beat the smallest of them by more than one.

Algorithm

1. Keep the previous row of sides, above, and build the current row.
2. A bare cell has side 0 and adds nothing.
3. An intact cell in the first column has side 1.
4. Any other intact cell takes 1 + min(above[j], above[j - 1], current[j - 1]).
5. Add each cell's side to the running total.
6. Move the current row into above and go on to the next row.

Complexity

Time O(rows · cols) — one constant-time decision per cell, 90000 in the worst case. Space O(cols), two rows of sides rather than the whole table.

Solution

"""Squares in the mosaic — the largest square cornered at each cell, summed."""


def solve(tiles):
    """How many intact square patches of any side the floor holds."""
    cols = len(tiles[0])
    above = [0] * cols
    total = 0

    for row in tiles:
        current = [0] * cols
        for j, cell in enumerate(row):
            if cell:
                # side of the largest intact square whose bottom-right corner
                # is this cell — and, because sides nest, also the number of
                # intact squares cornered here
                if j == 0:
                    current[j] = 1
                else:
                    current[j] = 1 + min(above[j], above[j - 1], current[j - 1])
                total += current[j]
        above = current                   # keep the old row intact for the diagonal
    return total

TESTS = [
    (([[1, 1, 0, 1], [1, 1, 1, 1], [0, 1, 1, 1]],), 13),
    (([[1, 1, 1], [1, 1, 1], [1, 1, 1]],), 14),
    (([[0, 1], [1, 1]],), 3),             # the missing diagonal caps the corner at side 1
    (([[0, 0], [0, 0]],), 0),
    (([[1, 0, 1, 0, 1]],), 3),
    (([[1, 1, 1, 0], [1, 1, 1, 0], [1, 1, 1, 1]],), 15),
]

Pitfalls

• Reporting the largest square instead of the count. Taking a maximum over the table answers a different question: the first example gives 2, or 4 if you square it, rather than 13.
• Using only the north and west neighbours. The diagonal is what stops a square growing over a hole behind it: on [[0, 1], [1, 1]] the two-neighbour rule gives the bottom-right cell a side of 2 and reports 4 patches, when the answer is 3.
• Overwriting the row in place. Once current[j - 1] has been written, the north-west value from the row above is gone. Keep the previous row until the current one is finished.
• Assuming a floor with no intact cells still has one patch. An all-bare grid holds nothing, and the answer is 0.

Variants

• Down the lock grid — the same north-and-west sweep over a grid, minimising instead of counting.
• Intervals and matrices — the general shape of a table laid over a rectangle.