Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Building Visibility by yoichi
def intersect(r0, r1):
"""
True if r0 and r1 has intersection.
r0 and r1 are represented as (x0, x1) where x0 < x1.
"""
if r1[1] < r0[0] or r0[1] < r1[0]:
return False
return True
def visible_range(rb, mask_ranges):
"""
True if rb is visible after being masked.
rb and mask_ranges are represented as (x0, x1) where x0 < x1.
"""
if not mask_ranges:
return True
merged = mask_ranges[0]
for r in mask_ranges:
if intersect(merged, r):
merged = (min(merged[0], r[0]), max(merged[1], r[1]))
else:
break
return rb[0] < merged[0] or merged[1] < rb[1]
def visible(b, masks):
"""
True if b(uilding) is visible after being masked.
b and masks are represented as (x0, x1, height) where x0 < x1.
"""
mask_ranges = sorted(list(map(lambda m: m[:2],
filter(lambda m: m[2] >= b[2] and intersect(b[:2], m[:2]),
masks))))
return visible_range(b[:2], mask_ranges)
def checkio(buildings):
masks = list(map(lambda b: (b[0], b[2], b[4]), sorted(buildings, key=lambda b: b[1])))
return sum(visible(masks[i], masks[:i]) for i in range(len(masks)))
if __name__ == '__main__':
assert checkio([
[1, 1, 4, 5, 3.5],
[2, 6, 4, 8, 5],
[5, 1, 9, 3, 6],
[5, 5, 6, 6, 8],
[7, 4, 10, 6, 4],
[5, 7, 10, 8, 3]
]) == 5, "First"
assert checkio([
[1, 1, 11, 2, 2],
[2, 3, 10, 4, 1],
[3, 5, 9, 6, 3],
[4, 7, 8, 8, 2]
]) == 2, "Second"
assert checkio([
[1, 1, 3, 3, 6],
[5, 1, 7, 3, 6],
[9, 1, 11, 3, 6],
[1, 4, 3, 6, 6],
[5, 4, 7, 6, 6],
[9, 4, 11, 6, 6],
[1, 7, 11, 8, 3.25]
]) == 4, "Third"
assert checkio([
[0, 0, 1, 1, 10]
]) == 1, "Alone"
assert checkio([
[2, 2, 3, 3, 4],
[2, 5, 3, 6, 4]
]) == 1, "Shadow"
Jan. 29, 2015
