Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dynamic Programming solution in Speedy category for The Square Chest by PositronicLlama
"""Compute the number of squares formed by edges in a grid."""
import itertools
import operator
GRID_LEN = 4
GRID_SIZE = GRID_LEN * GRID_LEN
def index(x, y):
"""Return the index of a coordinate pair."""
return x + GRID_LEN * y
def vector_add(p, q):
"""
Return the sum of two vectors.
The result is returned as a tuple.
"""
return tuple(itertools.starmap(operator.add, zip(p, q)))
def build_length_grid(lines, start, dir1, dir2):
"""
Return an array of the length of each contiguous line in the given direction.
"""
grid = [0] * GRID_SIZE
curr1 = start
while 0 <= curr1[0] < GRID_LEN and 0 <= curr1[1] < GRID_LEN:
curr2 = curr1
ix = index(*curr2)
count = 0
while 0 <= curr2[0] < GRID_LEN and 0 <= curr2[1] < GRID_LEN:
grid[ix] = count
next2 = vector_add(curr2, dir2)
next_ix = index(*next2)
if (next_ix + 1, ix + 1) in lines:
count += 1
else:
count = 0
ix = next_ix
curr2 = next2
curr1 = vector_add(curr1, dir1)
return grid
def checkio(lines_list):
"""Return the quantity of squares."""
# Use dynamic programming to reduce this problem to O(N^3).
# First, for each vertex, compute the total number of horizontal
# and vertical segments to the left or below respectively.
line_set = set(map(tuple, map(sorted, lines_list)))
len_horz = build_length_grid(line_set, (3, 0), (0, 1), (-1, 0))
len_vert = build_length_grid(line_set, (0, 3), (1, 0), (0, -1))
# Now, it is easy to check how many squares are present at each point.
squares = 0
for y, x in itertools.product(range(GRID_LEN), repeat=2):
ix = index(x, y)
test = min(len_horz[ix], len_vert[ix])
for i in range(1, test + 1):
if len_horz[index(x, y + i)] >= i and \
len_vert[index(x + i, y)] >= i:
squares += 1
return squares
if __name__ == '__main__':
assert (checkio([[1,2],[3,4],[1,5],[2,6],[4,8],[5,6],[6,7],
[7,8],[6,10],[7,11],[8,12],[10,11],
[10,14],[12,16],[14,15],[15,16]]) == 3) , "First, from description"
assert (checkio([[1,2],[2,3],[3,4],[1,5],[4,8],
[6,7],[5,9],[6,10],[7,11],[8,12],
[9,13],[10,11],[12,16],[13,14],[14,15],[15,16]]) == 2), "Second, from description"
assert (checkio([[1,2], [1,5], [2,6], [5,6]]) == 1), "Third, one small square"
assert (checkio([[1,2], [1,5], [2,6], [5,9], [6,10], [9,10]]) == 0), "Fourth, it's not square"
assert (checkio([[16,15], [16,12], [15,11], [11,10],
[10,14], [14,13], [13,9]]) == 0), "Fifth, snake"
Dec. 9, 2012
Comments:
