Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
test corners & split undecided solution in Clear category for Four To The Floor by juestr
from functools import lru_cache, reduce
def is_covered(room, sensors):
covered, uncovered, undecided = 1, 2, 3
@lru_cache(maxsize=1000)
def sensors_in_range(x, y):
return set(i for i, (xs, ys, rs) in enumerate(sensors) if (xs - x)**2 + (ys - y)**2 <= rs**2)
def check_area(x0, y0, x1, y1):
corners = ((x0, y0), (x1, y0), (x1, y1), (x0, y1))
sensors_for_corners = [sensors_in_range(x, y) for x, y in corners]
return \
not all(sensors_for_corners) and uncovered or \
reduce(set.intersection, sensors_for_corners) and covered or \
undecided
def split_area(x0, y0, x1, y1):
xm, ym = (x0 + x1) / 2, (y0 + y1) / 2
return ((x0, y0, xm, ym), (x0, ym, xm, y1), (xm, y0, x1, ym), (xm, ym, x1, y1))
stack = [(0, 0, *room)]
while stack:
area = stack.pop()
coverage = check_area(*area)
if coverage == uncovered:
return False
elif coverage == undecided:
stack.extend(split_area(*area))
return True
Dec. 27, 2019
Comments:
