机器人可以到达点 (x, y) 吗？

我在一次求职面试中遇到了这个问题，我无法找到解决方案的正确算法，所以我在这里发布这个问题：

有一个机器人可以通过以下两种方式在坐标平面上移动：

假设机器人当前位置为 (x,y)，如果方向如下，则机器人可以移动等于 x 和 y 之和的距离：

(x,y)  ->  (x+y, y)
(x,y)  ->  (x, x+y)

现在给定一个初始点 (x1, y1) 和一个目标点 (x2, y2)，您需要编写一个程序来检查机器人是否可以通过任意次数的移动到达目的地。

注：x1、y1、x2、y2 > 0

解释：

1. 假设机器人的初始点是(2,3)，目的地是(7,5)

   这种情况下的结果是肯定的，因为机器人可以采取以下路径：

   (2,3) -> (2, 2+3) => (2, 5)

   (2,5) -> (2+5, 5) => (7,5)

2. 假设机器人的起始点是(2,3)，目的地是(4,5)

   这种情况下的结果为“否”，因为无论机器人采取什么路径，它都无法到达 (4,5)

一种天真的暴力方法

一种方法是递归地探索每一个可能的动作，直到达到目标。

需要考虑的一点是，机器人可以无限期地保持移动（永远不会到达目标），因此您需要一个结束案例才能完成该功能。幸运的是，这个职位一直在增加x and y轴，因此当 x 坐标或 y 坐标大于目标时，您可以放弃探索该路径。

所以像这样：

def can_reach_target(pos, target):
    if pos == target: 
        return True
    if pos[0] > target[0] or pos[1] > target[1]: 
        return False
    return can_reach_target((pos[0], sum(pos)), target) or \
           can_reach_target((sum(pos), pos[1]), target)

它有效：

>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False

一个限制是这不适用于负坐标 - 不确定这是否是一个要求，只要让我知道是否是，我会调整答案。

回溯

另一方面，如果不允许负坐标，那么我们也可以将其处理为戴夫建议 https://stackoverflow.com/a/52041439/7434365。这更加高效，因为我们认识到机器人到达每个坐标的方式只有一种。

该方法依赖于能够确定我们迈出的方向：增加 x 坐标或 y 坐标。我们可以通过选择两个坐标中较大的一个来确定最后更改的坐标。以下证明保证了情况确实如此。

状态改变的可能性有：

1. (a, b) => (a+b, b)       a x-coordinate change

and,

2. (a, b) => (a, a+b)       a y-coordinate change

在情况 (1) 中，x 坐标现在更大，因为：

    a > 0
a + b > b  (add b to both sides)

同样地，因为b也是> 0，我们可以推断出a+b is > a.

现在我们可以从目标出发问：哪个坐标引导我们来到这里？答案很简单。如果 x 坐标大于 y 坐标，则从 x 坐标中减去 y 坐标，否则从 y 坐标中减去 x 坐标。

也就是说，对于一个坐标，(x,y), if x > y，那么我们来自(x-y,y)否则(x,y-x).

第一个代码现在可以调整为：

def can_reach_target(pos, target):
    if pos == target: 
        return True
    if target[0] < pos[0] or target[1] < pos[1]: 
        return False
    x, y = target
    return can_reach_target(pos, (x-y,y) if x > y  else (x,y-x))

其按预期工作：

>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False

Timings

>>> timeit.timeit('brute_force((2,3),(62,3))',globals=locals(),number=10**5)
3.41243960801512
>>> timeit.timeit('backtracker((2,3),(62,3))',globals=locals(),number=10**5)
1.4046142909792252
>>> timeit.timeit('brute_force((2,3),(602,3))',globals=locals(),number=10**4)
3.518286211998202
>>> timeit.timeit('backtracker((2,3),(602,3))',globals=locals(),number=10**4)
1.4182081500184722

所以你可以看到回溯器在这两种情况下都快了近三倍。