Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
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
def is_covered(
dimensions: Tuple[int, int],
sensors: List[Tuple[int, int, int]],
threshold: float = 1e0,
) -> bool:
"""
Determine efficiently if the sensors covers the room.
Note:
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.
Args:
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.
Returns:
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]
@lru_cache(maxsize=None)
def _point_is_covered_by(corner: Point) -> Set[int]:
return {
index
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.
return False
# 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.
return True
# If a same circle contains all the four corners, then
# it necessarily contains the entire rectangle.
if set.intersection(*indexes):
return True
# Divide the rectangle into four smaller ones, and check them all.
return all(map(_is_covered, rectangle.divide()))
return _is_covered(room)
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.
Note:
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)
def divide(self):
"""
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
Returns:
A tuple of four rectangles.
"""
a, b, c, d = self
ab, ac, ad, bc, cd = map(
Point.center,
(a, a, a, b, c),
(b, c, d, c, d),
)
return (
Rect(a, ab, ac, ad),
Rect(ab, b, bc, ac),
Rect(ac, bc, c, cd),
Rect(ad, ac, cd, d),
)
Dec. 3, 2019
Comments:
