You are faced with an enemy in a rectangular shape, and you only have weapons with a laser beam, there are no obstacles in the room, and the walls can completely reflect the laser beam. However, the laser can only move a certain distance before it becomes useless, and if it hits a corner, it will bounce back in the same direction in which it appeared.
The way the puzzle goes, and you are given the coordinates of your location and the target location, the size of the room and the maximum distance that the beam can move. for example, if room 3 is 2, and your location is (1, 1), and your goal is (2, 1), then possible solutions are:
I tried the following approach, starting from the source (1, 1) and creating a vector at an angle of 0 radians, it traces the vector path and reflections until it reaches the goal or the total length of the vectors exceeds the maximum length, repeat with an interval of 0.001 radian until he completes the full cycle. This is the code that I still have:
from math import * UPRIGHT = 0 DOWNRIGHT = 1 DOWNLEFT = 2 UPLEFT = 3 UP = 4 RIGHT = 5 LEFT = 6 DOWN = 7 def roundDistance (a): b = round (a * 100000) return b / 100000.0 # only used for presenting and doesn't affect percision def double (a): b = round (a * 100) if b / 100.0 == b: return int (b) return b / 100.0 def roundAngle (a): b = round (a * 1000) return b / 1000.0 def isValid (point): x,y = point if x < 0 or x > width or y < 0 or y > height: return False return True def isCorner (point): if point in corners: return True return False # Find the angle direction in relation to the origin (observer) point def getDirection (a): angle = roundAngle (a) if angle == 0: return RIGHT if angle > 0 and angle < pi / 2: return UPRIGHT if angle == pi / 2: return UP if angle > pi / 2 and angle < pi: return UPLEFT if angle == pi: return LEFT if angle > pi and angle < 3 * pi / 2: return DOWNLEFT if angle == 3 * pi / 2: return DOWN return DOWNRIGHT # Measure reflected vector angle def getReflectionAngle (tail, head): v1 = (head[0] - tail[0], head[1] - tail[1]) vx,vy = v1 n = (0, 0) # Determin the normal vector from the tail position on the borders if head[0] == 0: n = (1, 0) if head[0] == width: n = (-1, 0) if head[1] == 0: n = (0, 1) if head[1] == height: n = (0, -1) nx,ny = n # Calculate the reflection vector using the formula: # r = v - 2(vn)n r = (vx * (1 - 2 * nx * nx), vy * (1 - 2 * ny * ny)) # calculating the angle of the reflection vector using it a and b values # if b (adjacent) is zero that means the angle is either pi/2 or -pi/2 if r[0] == 0: return pi / 2 if r[1] >= 0 else 3 * pi / 2 return (atan2 (r[1], r[0]) + (2 * pi)) % (2 * pi) # Find the intersection point between the vector and borders def getIntersection (tail, angle): if angle < 0: print "Negative angle: %f" % angle direction = getDirection (angle) if direction in [UP, RIGHT, LEFT, DOWN]: return None borderX, borderY = corners[direction] x0,y0 = tail opp = borderY - tail[1] adj = borderX - tail[0] p1 = (x0 + opp / tan (angle), borderY) p2 = (borderX, y0 + adj * tan (angle)) if isValid (p1) and isValid (p2): print "Both intersections are valid: ", p1, p2 if isValid (p1) and p1 != tail: return p1 if isValid (p2) and p2 != tail: return p2 return None # Check if the vector pass through the target point def isHit (tail, head): d = calcDistance (tail, head) d1 = calcDistance (target, head) d2 = calcDistance (target, tail) return roundDistance (d) == roundDistance (d1 + d2) # Measure distance between two points def calcDistance (p1, p2): x1,y1 = p1 x2,y2 = p2 return ((y2 - y1)**2 + (x2 - x1)**2)**0.5 # Trace the vector path and reflections and check if it can hit the target def rayTrace (point, angle): path = [] length = 0 tail = point path.append ([tail, round (degrees (angle))]) while length < maxLength: head = getIntersection (tail, angle) if head is None: #print "Direct reflection at angle (%d)" % angle return None length += calcDistance (tail, head) if isHit (tail, head) and length <= maxLength: path.append ([target]) return [path, double (length)] if isCorner (head): #print "Corner reflection at (%d, %d)" % (head[0], head[1]) return None p = (double (head[0]), double (head[1])) path.append ([p, double (degrees (angle))]) angle = getReflectionAngle (tail, head) tail = head return None def solve (w, h, po, pt, m): # Initialize global variables global width, height, origin, target, maxLength, corners, borders width = w height = h origin = po target = pt maxLength = m corners = [(w, h), (w, 0), (0, 0), (0, h)] angle = 0 solutions = [] # Loop in anti-clockwise direction for one cycle while angle < 2 * pi: angle += 0.001 path = rayTrace (origin, angle) if path is not None: # extract only the points coordinates route = [x[0] for x in path[0]] if route not in solutions: solutions.append (route) print path # Anser is 7 solve (3, 2, (1, 1), (2, 1), 4) # Answer is 9 #solve (300, 275, (150, 150), (185, 100), 500)
The code works somehow, but it does not find all possible solutions, I have a big problem with accuracy, I don’t know how many decimal places to consider when comparing distances or angles. I'm not sure if this is the right way to do this, but this is the best I could do.
How can I fix my code to extract all the solutions? I need this to be effective because the room can become quite large (500 x 500). Is there a better way or maybe some kind of algorithm for this?