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)
Generated by GNU enscript 1.6.3.