from operator import mul from fractions import gcd vec_mul = lambda a, b: tuple(map(lambda x: mul(*x), zip(a, b))) vec_scale = lambda a, b: vec_mul(a, (b, b)) vec_add = lambda a, b: tuple(map(sum, zip(a, b))) vec_sub = lambda a, b: vec_add(a, vec_scale(b, -1)) vec_magnitude = lambda a: sum(map(lambda x: x**2, a))**.5 def get_mirror(pos, coords, dimensions): temp = [ pos[i] if coords[i] % 2 == 0 else dimensions[i] - pos[i] for i in range(2) ] return vec_add(temp, vec_mul(coords, dimensions)) def vec_reduce(a): if 0 in a: return tuple(map(lambda x: x / abs(x) if x > 0 else 0, a)) return tuple(map(lambda x: x / gcd(*map(abs, a)), a)) def answer(dimensions, us, target, distance): selfs = {} hits = set([]) bound = [distance / dimensions[i] + 1 for i in range(2)] possible = [range(-i, i + 1) for i in bound] for x in possible[0]: for y in possible[1]: current = vec_sub(get_mirror(us, (x, y), dimensions), us) d = vec_magnitude(current) current = vec_reduce(current) if d <= distance: if current in selfs and selfs[current] < d: continue selfs[current] = d for x in possible[0]: for y in possible[1]: current = vec_sub(get_mirror(target, (x, y), dimensions), us) d = vec_magnitude(current) current = vec_reduce(current) if d <= distance: if current in selfs and selfs[current] < d: continue hits.add(current) return len(hits) dimensions = [3, 3] your_position = [1, 1] guard_position = [2, 1] distance = 195 # dimensions = [300, 275] # your_position = [150, 150] # guard_position = [185, 100] # distance = 5000 # dimensions = [6, 15] # your_position = [3, 13] # guard_position = [4, 11] # distance = 7455 print answer(dimensions, your_position, guard_position, distance)