python - 拼图 : how many ways can you hit a target with a laser beam within four reflective walls

Question

你在一个长方形的房间内与敌人对峙，你只有一把激光束武器，房间内没有任何障碍物，墙壁可以完全反射激光束。然而，激光在变得无用之前只能行进一定距离，如果它碰到一个角落，它会沿与它来自的相同方向反射回来。

谜题就是这样进行的，你会得到你所在位置的坐标和目标的位置、房间尺寸以及光束可以传播的最大距离。例如，如果房间是 3 x 2，您的位置是 (1, 1)，目标是 (2, 1)，那么可能的解决方案是:

我尝试了以下方法，从源 (1, 1) 开始并创建一个角度为 0 弧度的矢量，跟踪矢量路径和反射，直到它击中目标或矢量的总长度超过允许的最大长度长度，以 0.001 弧度间隔重复，直到完成一个完整的循环。这是我到目前为止的代码:

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)

代码以某种方式工作但它没有找到所有可能的解决方案，我在其中有一个很大的精度问题，我不知道在比较距离或角度时我应该考虑多少小数。我不确定这是正确的方法，但这是我能做到的最好的方法。

如何修复我的代码以提取所有解决方案？我需要它来提高效率，因为房间会变得很大 (500 x 500)。是否有更好的方法或某种算法来执行此操作？

Answer 1

如果您首先在所有墙壁上镜像目标会怎样？然后在所有墙壁上镜像镜像等等，直到距离变得太大以至于激光无法到达目标？以这种方式向目标的任何方向发射的任何激光都会击中该目标。 (这是我从上面的评论；在这里重复以使答案更加独立......)

这是答案的镜像部分:get_mirrored 将返回 point 的四个镜像，镜像框受 BOTTOM_LEFT 限制和 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))

这将返回给定点的 4 个镜像:

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

这是镜像一次的目标。

然后您可以迭代直到所有镜像目标都超出范围。范围内的所有镜像将为您提供激光指向的方向。

---

这是一种在给定 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 现在是包含所有可达点的集合。

(这些都没有经过彻底测试...)

---

您的反例的小更新:

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