length_square.py

#!/usr/bin/env python

# The area of maximum length square

__author__ = "Shimomura Ikkei"
__date__ = "2005/06/01"

from UserList import UserList
from random import randint

class Field(UserList):
    WIDTH = 5
    HEIGHT = 5

    def __init__(self):
        UserList.__init__(self)

        """
        for i in xrange(self.HEIGHT):
            self.append([])
            for j in xrange(self.WIDTH):
                self[i].append( randint(0,1) )
        """
        for i in xrange(self.HEIGHT):
            self.append(map(lambda _:randint(0,1), xrange(self.WIDTH)))

    def getRow(self, row, start=0):
        return self[row][start:]

    def get(self, x, y):
        return self[y][x]

    def dump(self):
        """
        r = ""
        for row in self:
            r += repr(row) + "\n"
        return r
        """
        return "\n".join(map(repr,self))


def solve(field):
    """
        +---+---+---+---+---+
        |   |   |   |   |   |
        +---+---+---+---+---+
        | 1 | 1 | 1 | 1 |   |
        +---+---+---+---+---+
        | 1 | 1 |   |   |   |
        +---+---+---+---+---+
        | 1 | 1 |   |   |   |
        +---+---+---+---+---+
        | 1 |   |   |   |   |
        +---+---+---+---+---+

        How to count the area of length square ?

        Step 1) count first bits
            [ 4, 2, 2, 1 ]

        Step 2) how many numbers contains (make length square)
            5 ... [ 0 ]
            4 ... [ 4 ]
            3 ... [ 3 ]
            2 ... [ 2, 2, 2 ]
            1 ... [ 1, 1, 1, 1 ]

        Step 3)
            sum(4)          => 4
            sum(3)          => 3
            sum(2, 2, 2)    => 6
            sum(1, 1, 1, 1) => 4
        
        Step 4)
            return max(4, 3, 6, 4)
        
        Answer : 6
    """

    """
    def count_first_bits(lst):
        count = 0
        for i in lst:
            if i == 1:
                count += 1
            else:
                return count
        return count
    """
    def count_first_bits(lst):
        if lst and lst[0] == 1:
            return 1 + count_first_bits(lst[1:])
        return 0

    """
    def search_length_square(lst, num):
        ret = []
        for n in lst:
            if n >= num:
                ret.append(num)
            else:
                return ret
        return ret
    """
    def search_length_square(lst, num):
        """
        >>> count_greater([3,2,4,1,4], 2)
        ... [2, 2, 2]
        """
        if lst and lst[0] >= num:
            return [num] + search_length_square(lst[1:],num)
        return []

    """
    def map_first(func, lst):
        ret = []
        for xs in lst:
            x = func(xs)
            if x:
                ret.append(x)
            else:
                return ret
        return ret
    """
    def map_first(func, lst):
        if lst:
            item = func(lst[0])
            if item:
                return [item] + map_first(func, lst[1:])
        return []
            
    # If the element is a false, then stop iteration of recursive.
    # that also can be pattern, to make higher-order function.
    
    
    answer = []
    """
    for y in xrange(len(field)):
        for x in xrange(len(field[y])):
            if not field.get(x,y ):
                continue
    """
    for x,y in ((x,y) for y in xrange(len(field))
                      for x in xrange(len(field[y]))
                      if field.get(x,y)):

            lstA = map_first(
                    count_first_bits,
                    [ field.getRow(i,start=x) for i in xrange(y,len(field)) ])
            lstB = map(lambda n:search_length_square(lstA,n), xrange(1,5+1))
            answer.append( max(map(sum,lstB)) )

    return max(answer)


if __name__ == "__main__":

    field = Field()
    print "-----------------------"
    print field.dump()
    print "======================="
    print "Answer is: %d" % solve(field)