dp.py

#!/usr/bin/env python
"""Find height, width of the largest rectangle containing all 0's in the matrix.

The algorithm for `max_size()` is suggested by @j_random_hacker [1].
The algorithm for `max_rectangle_size()` is from [2].
The Python implementation [3] is under CC BY-SA 3.0
(if you need other license, e-mail me)

[1]: http://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-nn-binary-matrix#comment5169734_4671342

[2]: http://blog.csdn.net/arbuckle/archive/2006/05/06/710988.aspx

[3]: http://stackoverflow.com/a/4671342
"""
from collections import namedtuple
from operator import mul
from itertools import product

try:
    reduce = reduce
except NameError:
    from functools import reduce # py3k

Info = namedtuple('Info', 'start height')

def max_size(mat, value=0):
    """Find height, width of the largest rectangle containing all `value`'s.

    For each row solve "Largest Rectangle in a Histrogram" problem [1]:

    [1]: http://blog.csdn.net/arbuckle/archive/2006/05/06/710988.aspx

    Return ((height,width), (hpos, vpos))
    """
    it = iter(mat)
    hist = [(el==value) for el in next(it, [])]
    max_size, max_loc  = max_rectangle_size(hist)
    for idrow, row in enumerate(it):
        hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)]
        res = max_rectangle_size(hist)
        if area(max_size) < area(res[0]):
            max_size, max_loc = res[0], (res[1][0], idrow + 1)
    return (max_size, (max_loc[1], max_loc[0]))

def max_rectangle_size(histogram):
    """Find height, width of the largest rectangle that fits entirely under
    the histogram.

    >>> f = max_rectangle_size
    >>> f([5,3,1])
    (3, 2)
    >>> f([1,3,5])
    (3, 2)
    >>> f([3,1,5])
    (5, 1)
    >>> f([4,8,3,2,0])
    (3, 3)
    >>> f([4,8,3,1,1,0])
    (3, 3)
    >>> f([1,2,1])
    (1, 3)

    Algorithm is "Linear search using a stack of incomplete subproblems" [1].

    [1]: http://blog.csdn.net/arbuckle/archive/2006/05/06/710988.aspx
    """
    stack = []
    top = lambda: stack[-1]
    max_size = (0, 0) # height, width of the largest rectangle
    max_location = (-1, -1)
    pos = 0 # current position in the histogram
    for pos, height in enumerate(histogram):
        start = pos # position where rectangle starts
        while True:
            if not stack or height > top().height:
                stack.append(Info(start, height)) # push
            elif stack and height < top().height:
                if area(max_size) < area((top().height, (pos - top().start))):
                    max_size = (top().height, (pos - top().start))
                    max_location = ( top().start, 0)
                start, _ = stack.pop()
                continue
            break # height == top().height goes here

    pos += 1
    for start, height in stack:
        if area(max_size) < area((height, (pos - start))):
            max_size = (height, (pos - start))
            max_location = (start, 0)

    return (max_size, max_location)

def area(size):
    return reduce(mul, size)


def s2m(s):
    return [map(int, line.split())
            for line in s.splitlines() if line.strip()]

import unittest
class TestCase(unittest.TestCase):
    def test(self):
        self.assertEqual(max_size(s2m("""
        0 0 0 0 1 0
        0 0 1 0 0 1
        0 0 0 0 0 0
        1 0 0 0 0 0
        0 0 0 0 0 1
        0 0 1 0 0 0"""))[0], (3, 4))
        self.assertEqual(max_size([[1, 1], [0, 0]])[0], (1, 2))
        self.assertEqual(max_size([[0, 0], [1, 1]])[0], (1, 2))
        self.assertEqual(max_size([[1, 0], [1, 0]])[0], (2, 1))
        self.assertEqual(max_size([[0, 1], [0, 1]])[0], (2, 1))
        self.assertEqual(max_size(s2m("""
        0 0 0 0 1 0
        0 0 1 0 0 1
        0 0 0 0 0 0
        1 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], (7, 2))
        self.assertEqual(max_size([[]])[0], (0, 0))
        self.assertEqual(max_size([])[0], (0, 0))
        self.assertEqual(max_size(s2m("""
        0 0 0 0 1 0
        0 0 1 0 0 1
        0 0 0 0 0 0
        1 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], (3, 5))
        self.assertEqual(max_size(s2m("""
        0 0 0 0 1 0
        0 0 0 0 0 0
        0 0 1 0 0 1
        0 0 0 0 0 0
        1 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 1"""))[0], (8, 2))
        self.assertEqual(max_size(s2m("""
        0 0 0 0 1 1 1
        0 0 0 0 0 0 0
        0 0 0 1 1 1 1
        0 0 1 1 1 1 1
        1 0 1 1 1 1 1
        1 0 1 1 1 1 1
        1 0 1 1 1 1 1
        """))[0], (3, 3))


if __name__=="__main__":
    #import unittest; unittest.main()
    filtered_layer = s2m("""
        0 9 8 8 8 1 1
        5 0 8 8 8 0 0
        5 0 8 1 1 1 1
        0 0 1 1 1 1 1
        1 0 1 1 1 1 1
        1 0 1 1 1 1 1
        1 0 1 1 1 1 1
        """)
    b_size, b_loc = max_size(filtered_layer, 0)
    print b_size
    print b_loc
    locs = [list(tup) for tup in product(range(b_loc[0] - (b_size[0] - 1), b_loc[0] + 1), range(b_loc[1] , b_loc[1] + b_size[1]))]
    print locs
    print str([[None if [row_id, column_id] in locs else cell for column_id, cell in enumerate(row)]
                                          for row_id, row in enumerate(filtered_layer)]).replace("], [","],\n [")