title: Puzzle: how many ways can you hit a target with a laser beam within four reflective walls
body: <p>You are confronted with an enemy within a rectangular shaped room and you've got only a laser beam weapon, the room has no obstructions in it and the walls can completely reflect the laser beam. However the laser can only travels a certain distance before it become useless and if it hit a corner it would reflect back in the same direction it came from.</p>
  
  <p>That's how the puzzle goes and you are given the coordinates of your location and the target's location, the room dimensions and the maximum distance the beam can travel. for example If the room is 3 by 2 and your location is (1, 1) and the target is (2, 1) then the possible solutions are:</p>
  
  <p><a href="https://i.stack.imgur.com/wZK3o.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/wZK3o.jpg" alt="All possible ways to hit the target (2, 1) from (1, 1) in 3x2 room"></a></p>
  
  <p>I tried the following approach, start from the source (1, 1) and create a vector at angle 0 radians, trace the vector path and reflections until either it hits the target or the total length of the vectors exceeds the max allowed length, repeat with 0.001 radians interval until it completes a full cycle. This the code I have so far:</p>
  
  <pre><code>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 &lt; 0 or x &gt; width or y &lt; 0 or y &gt; 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 &gt; 0 and angle &lt; pi / 2: return UPRIGHT
      if angle == pi / 2: return UP
      if angle &gt; pi / 2 and angle &lt; pi: return UPLEFT
      if angle == pi: return LEFT
      if angle &gt; pi and angle &lt; 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's 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(v.n)n
      r = (vx * (1 - 2 * nx * nx), vy * (1 - 2 * ny * ny))
      # calculating the angle of the reflection vector using it's 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] &gt;= 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 &lt; 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 &lt; 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 &lt;= 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 &lt; 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)
  </code></pre>
  
  <p>The code works somehow but it doesn't find all the possible solutions, I have a big precision problem in it, I dont' know how many decimals should I consider when comparing distances or angles. I'm not sure it's the right way to do it but that's the best I was able to do.</p>
  
  <p>How can I fix my code to extract all solutions? I need it to be efficient because the room can get quite large (500 x 500). Is there a better way or maybe some sort of algorithm to do this?</p>