Look at as few points as possible by dividing the rectangle until it is too small solution in Speedy category for Four To The Floor by Phil15
from collections import namedtuple
from functools import lru_cache
from math import hypot
from typing import List, Tuple, Set
dimensions: Tuple[int, int],
sensors: List[Tuple[int, int, int]],
threshold: float = 1e0,
) -> bool:
Determine efficiently if the sensors covers the room.
It typically looks at as few points as possible with the given threshold.
On basic and extra tests:
With threshold = 1, it looks at between 4 and 307 points.
With threshold = 1e-15, it looks at between 4 and 605 points.
dimensions: width and height of the rectangular room.
sensors: list of (sensor's coordinates x and y, sensor's range).
threshold: an uncovered zone is ignored if it has an area less than threshold.
bool: sensors covers the entire room (with given precision).
w, h = dimensions
room = Rect(Point(0, 0), Point(w, 0), Point(w, h), Point(0, h))
sensors = [(Point(x, y), radius) for x, y, radius in sensors]
def _point_is_covered_by(corner: Point) -> Set[int]:
for index, (center, radius) in enumerate(sensors)
if center.distance(corner) <= radius
def _is_covered(rectangle: Rect) -> bool:
indexes = list(map(_point_is_covered_by, rectangle))
if not all(indexes):
# A corner of the rectangle is not in any circle.
# Here, we know that all four corners are in circles.
if rectangle.area() <= threshold:
# Don't check other points than corners if the rectangle is too
# small. Decrease `threshold` to reduce potential errors here.
# If a same circle contains all the four corners, then
# it necessarily contains the entire rectangle.
# Divide the rectangle into four smaller ones, and check them all.
return all(map(_is_covered, rectangle.divide()))
class Point(namedtuple('Point', 'x y')):
"""Define a Point."""
def center(pt1, pt2):
"""The center of a line segment."""
return Point((pt1.x + pt2.x) / 2, (pt1.y + pt2.y) / 2)
def distance(pt1, pt2) -> float:
"""The distance between two points."""
return hypot(pt1.x - pt2.x, pt1.y - pt2.y)
class Rect(namedtuple('Rect', 'A B C D')):
Define a rectangle by its four corners.
Corners order have to be
D --- C
A --- B
def area(self) -> float:
"""The area of the rectangle."""
return self.A.distance(self.B) * self.A.distance(self.D)
Divide the current rectangle into four smaller sub-rectangles.
Divide ABCD into 4 sub-rectangles.
D --- cd --- C
| 4 | 3 |
ad --- ac --- bc
| 1 | 2 |
A --- ab --- B
A tuple of four rectangles.
a, b, c, d = self
ab, ac, ad, bc, cd = map(
(a, a, a, b, c),
(b, c, d, c, d),
Rect(a, ab, ac, ad),
Rect(ab, b, bc, ac),
Rect(ac, bc, c, cd),
Rect(ad, ac, cd, d),
Dec. 3, 2019