Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Cheating solution in Clear category for Four To The Floor by azqueshu
def is_covered(room, sensors):
# Initial idea: check if all segments of the room's edge satisfy (distance to some center < circle radius)
# for each circle, find the intersections with the extrapolated edges
# if the intersections include the totality of the edge, then passed.
# correction: the above method may cause area in the middle to be missed.
# for correct result: need to find sensor/room overlap area, and subtract overlap with all previous sensors??
#alternate method: just use sampling: if don't pass, then tighten the grid. A bit cheesy.
W = room[0]
H = room[1]
for x in range_float(0,W,max(0.2,(W/1000))):
for y in range_float(0,H,max(0.2,(H/1000))):
passed = False
for s in sensors:
xs = s[0]
ys = s[1]
r = s[2]
if (x-xs)**2 + (y-ys)**2 <= r**2:
passed = True
break
if not passed:
return False
return True
def range_float(start,stop,step):
while start < stop+step:
if start <= stop:
yield start
else:
yield stop
start+=step
if __name__ == '__main__':
# These "asserts" are used for self-checking and not for an auto-testing
assert is_covered([200, 150], [[50, 75, 100], [150, 25, 50], [150, 125, 50]]) == False
assert is_covered([200, 150], [[100, 75, 100], [0, 40, 60], [0, 110, 60], [200, 40, 60], [200, 110, 60]]) == True
assert is_covered([200, 150], [[100, 75, 100], [0, 40, 50], [0, 110, 50], [200, 40, 50], [200, 110, 50]]) == False
assert is_covered([200, 150], [[100, 75, 110], [105, 75, 110]]) == False
assert is_covered([200, 150], [[100, 75, 110], [105, 75, 20]]) == False
assert is_covered([3, 1], [[1, 0, 2], [2, 1, 2]]) == True
assert is_covered([30, 10], [[0, 10, 10], [10, 0, 10], [20, 10, 10], [30, 0, 10]]) == True
assert is_covered([30, 10], [[0, 10, 8], [10, 0, 7], [20, 10, 9], [30, 0, 10]]) == False
print("Coding complete? Click 'Check' to earn cool rewards!")
# up = 0
# down = 0
# left = 0
# right = 0
# for s in sensors:
# upints = find_int((s[0],s[1],s[2]),'h',H)
# downints= find_int((s[0],s[1],s[2]),'h',0)
# leftints= find_int((s[0],s[1],s[2]),'v',0)
# rightints= find_int((s[0],s[1],s[2]),'v',W)
# #find contribution somehow
# return False
#def find_int((x,y,r),dir,pos,existing):
# intersection with horizontal edge: solve for (x-xs)^2 + (h-ys)^2 = r^2
# intersection with vertical edge: solve for (w-ws)^2 + (y - ys)^2 = r^2
# if dir == 'v':
# ytemp = r**2 - (pos-x)**2
# if ytemp >= 0:
# ints = (y-sqrt(ytemp),y+sqrt(temp))
# elif dir=='h'
# xtemp = r**2 - (pos-y)**2
# if xtemp >= 0:
# ints = (x-sqrt(xtemp),x+sqrt(xtemp))
# return ints if ints else ()
March 11, 2021