Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Amortized O(1) solution in Speedy category for Ore In The Desert by Renelvon
from math import hypot
from collections import defaultdict
"""
Probing from these two spots guarantees no more than 2 squares
have the exact pair of distances. 3rd probe is used as tie-breaker.
"""
i1, j1 = 0, 0
i2, j2 = 0, 7
dist = lambda i, j: (round(hypot(i-i1, j-j1)), round(hypot(i-i2, j-j2)))
"""
Map from distances to candidate ore squares.
Needn't be calculated more than once.
"""
inverseMap = defaultdict(list)
for i in range(10):
for j in range(10):
inverseMap[dist(i, j)].append([i, j])
def checkio(tries):
l = len(tries)
if l == 0:
return [i1, j1]
elif l == 1:
return [i2, j2]
elif l == 2:
return inverseMap[(tries[0][2], tries[1][2])][0] # 1st candidate
return inverseMap[(tries[0][2], tries[1][2])][1] # 2nd candidate
June 5, 2014
