Puzzle: how many ways can you hit a target with a laser beam within four reflective walls

Question

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.

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:

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:

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'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] >= 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 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.

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?

Answer 1

what if you started by mirroring the target at all the walls; then mirror the mirror images at all the walls and so on until the distance gets too big for the laser to reach the target? any laser shot in any direction of a target mirrored that way will hit said target. (this is my comment from above; repeated here to make answer more self-contained...)

this is the mirroring part of the answer: get_mirrored will return the four mirror images of point with the mirror-box limited by BOTTOM_LEFT and TOP_RIGHT.

BOTTOM_LEFT = (0, 0)
TOP_RIGHT = (3, 2)

SOURCE = (1, 1)
TARGET = (2, 1)

def get_mirrored(point):
    ret = []

    # mirror at top wall
    ret.append((point[0], point[1] - 2*(point[1] - TOP_RIGHT[1])))
    # mirror at bottom wall
    ret.append((point[0], point[1] - 2*(point[1] - BOTTOM_LEFT[1])))
    # mirror at left wall
    ret.append((point[0] - 2*(point[0] - BOTTOM_LEFT[0]), point[1]))
    # mirror at right wall
    ret.append((point[0] - 2*(point[0] - TOP_RIGHT[0]), point[1]))
    return ret

print(get_mirrored(TARGET))

this will return the 4 mirror images of the given point:

[(2, 3), (2, -1), (-2, 1), (4, 1)]

which is the target mirrored one time.

then you could iterate that until all the mirrored targets are out of range. all the mirror images within range will give you a direction in which to point your laser.

---

this is a way how you could iteratively get to the mirrored targets within a given DISTANCE

def get_targets(start_point, distance):

    all_targets = set((start_point, ))  # will also be the return value
    last_targets = all_targets          # need to memorize the new points

    while True:
        new_level_targets = set()  # if this is empty: break the loop
        for tgt in last_targets:   # loop over what the last iteration found
            new_targets = get_mirrored(tgt)
            # only keep the ones within range
            new_targets = set(
                t for t in new_targets
                if math.hypot(SOURCE[0]-t[0], SOURCE[1]-t[1]) <= DISTANCE)
            # subtract the ones we already have
            new_targets -= all_targets
            new_level_targets |= new_targets
        if not new_level_targets:
            break
        # add the new targets
        all_targets |= new_level_targets
        last_targets = new_level_targets  # need these for the next iteration

    return all_targets

DISTANCE = 5    

all_targets = get_targets(start_point=TARGET, distance=DISTANCE)
print(all_targets)

all_targets is now the set that contains all the reachable points.

(none of that has been thouroughly tested...)

---

small update for your counter example:

def ray_length(point_list):
    d = sum((math.hypot(start[0]-end[0], start[1]-end[1])
            for start, end in zip(point_list, point_list[1:])))
    return d

d = ray_length(point_list=((1,1),(2.5,2),(3,1.67),(2,1)))
print(d)  # -> 3.605560890844135

d = ray_length(point_list=((1,1),(4,3)))
print(d)  # -> 3.605551275463989