Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dynamic Programming O(N^3) solution in Clear category for Spaceship Landing Strip by PositronicLlama
"""Compute the size of the largest rectangular region in a grid."""
import itertools
OKAY = set('GS')
def distance_till_blocked(array, okay=OKAY):
"""
Return an array counting the cells until blocked at each element.
Example:
'GGGTGGGGGTTG' -> [3, 2, 1, 0, 5, 4, 3, 2, 1, 0, 0, 1]
"""
result = []
count = 0
for c in reversed(array):
if c in okay:
count += 1
else:
count = 0
result.insert(0, count)
return result
def checkio(grid):
"""Return the area of the largest clearable rectangle in map."""
# The naive solution is O(N^4), but we can use dynamic programming
# to solve this in O(N^3).
# First, build a map that counts the number of spaces per row until
# the next obstacle. Do the same for columns. This is O(N^2).
# Then, for each of O(N^2) cells, it is O(N) to determine the maximal
# rectangle.
row_dist = list(map(distance_till_blocked, grid))
col_dist = list(zip(*map(distance_till_blocked, zip(*grid))))
# n columns, m rows
n = len(grid[0])
m = len(grid)
max_area = 0
for y, x in itertools.product(range(0, m), range(0, n)):
# For each cell, walk along the row and compute the maximal
# rectangle starting at this point.
max_height = m
for i in range(0, row_dist[y][x]):
max_height = min(max_height, col_dist[y][x + i])
max_area = max(max_area, max_height * (i + 1))
return max_area
if __name__ == '__main__':
assert distance_till_blocked('GGGTGGGGGTTG') == \
[3, 2, 1, 0, 5, 4, 3, 2, 1, 0, 0, 1], 'Distance till blocked error'
assert checkio(['G']) == 1, 'First'
assert checkio(['GS','GS']) == 4, 'Second'
assert checkio(['GT','GG']) == 2, 'Third'
assert checkio(['GGTGG','TGGGG','GSSGT','GGGGT','GWGGG','RGTRT','RTGWT','WTWGR']) == 9, 'Fourth'
print('All is ok')
Dec. 8, 2012
Comments:
