计算最短网格距离

Question

Consider a city where the streets are perfectly laid out to form an infinite square grid. In this city finding the shortest path between two given points (an origin and a destination) is much easier than in other more complex cities. As a new Uber developer, you are tasked to create an algorithm that does this calculation.

Given user's departure and destination coordinates, each of them located on some street, find the length of the shortest route between them assuming that cars can only move along the streets. You are guaranteed that at least one of the coordinates is an integer.

我正在努力弄清楚这里的逻辑。有很多情况，我不知道如何容纳它们。这是我目前所拥有的

double perfectCity(double[] departure, double[] destination) {
    double yDist = Math.abs(destination[1]-departure[1]);
    double xDist = Math.abs(departure[1] - departure[0] + departure[1]-destination[0]);
    return xDist + yDist;
}

Answer 1

如果输入是整数，算法很简单，只需要求出x和y坐标之间的绝对值，然后将它们相加即可。这叫做 Manhattan distance.

int distance = Math.abs(x1 - x2) + Math.abs(y1 - y2);

对于双打，除了一种情况外，几乎完全一样。这里有一些可能性：

两个点都有整数坐标
一个点有整数坐标，另一个点只有一个整数坐标
两点只有一个整数坐标，但在不同的轴上
两点只有一个整数坐标，且在同一轴上

可能性 1-3 使用与用整数查找距离相同的算法都可以正常工作，除了 #4 有可能共同的轴在同一个块上。

例如，如果输入是：{x: 0.5, y: 2} 和 {x: 0.5, y: 3}，您必须水平、垂直移动，然后再次水平向后移动才能到达目的地。这与{x: 0.5, y: 2}和{x: 1.5, y: 3}的输入不同，因为不需要在同一轴上向后移动。

所以你可以在所有情况下使用正常算法除了当Xs或Ys都具有浮点值并且具有相同的情况[=19= ]-编辑值。

您的代码应如下所示。

import static java.lang.Math.*;

public static double perfectCity(double x1, double y1, double x2, double y2) {
    double xDist = abs(x1 - x2);
    double yDist = abs(y1 - y2);
    if (floor(x1) != x1 && floor(x2) != x2 &&        // both Xs are doubles
        floor(x1) == floor(x2) &&                    // on the same block
        y1 != y2) {                                  // not on the same street
        xDist = min(abs(x1 - floor(x1) + x2 - floor(x2)),
                    abs(x1 - ceil(x1)  + x2 - ceil(x2)));
    } else if (floor(y1) != y1 && floor(y2) != y2 && // both Ys are doubles
               floor(y1) == floor(y2) &&             // on the same block
               x1 != x2) {                           // not on the same street
        yDist = min(abs(y1 - floor(y1) + y2 - floor(y2)),
                    abs(y1 - ceil(y1)  + y2 - ceil(y2)));
    }
    return xDist + yDist;
}

这可以通过使用辅助函数分别计算每个轴来进一步简化。

public static double perfectCity(double x1, double y1, double x2, double y2) {
    return travelOnAxis(x1, x2, y1 == y2) + travelOnAxis(y1, y2, x1 == x2);
}

private static double travelOnAxis(double from, double to, boolean travelIsStraight) {
    if (Math.floor(from) == Math.floor(to) && !travelIsStraight) {
        double dist = Math.abs((from % 1) + (to % 1));
        return Math.min(dist, 2 - dist);
    } else {
        return Math.abs(from - to);
    }
}

我在这里使用了 2 - dist 的技巧，因为它与计算

相同

Math.abs((1 - (from % 1)) + (1 - (to % 1)))

与

相同

Math.abs(from - Math.ceil(from) + to - Math.ceil(to))

Answer 2

如果这是正方形网格，可以分别考虑x和y坐标；最小距离是两个方向的最小距离之和。

在 p 方向（x 或 y），您必须从 p1 移动到 p2。从p1，你可以移动到floor(p1)或ceil(p1)到达一条路（如果p1是一个整数，这可能是相等的）；从那里，您可以移动到 floor(p2) 或 ceil(p2)，即 p2 所在的道路；从那里，您可以移动到 p2.

所以，p方向的最小距离是

min(abs(p1 - ceil(p1) ) + abs(ceil(p1)  - floor(p2)) + abs(floor(p2) - p2),  # (1)
    abs(p1 - floor(p1)) + abs(floor(p1) - ceil(p2) ) + abs(ceil(p2)  - p2),  # (2)
    abs(p1 - floor(p1)) + abs(floor(p1) - floor(p2)) + abs(floor(p2) - p2),  # (3)
    abs(p1 - ceil(p1) ) + abs(ceil(p1)  - ceil(p2) ) + abs(ceil(p2)  - p2))  # (4)

所以你可以单独计算 x 和 y 方向，然后加上。

为了说明这一点（将 floor 和 ceil 分别缩写为 f 和 p）：

f(p1) p1  c(p1)
  +---O>>>>+>>>>>>>>+
                    .
                    .
                    +>>>O----+
                  f(p2) p2  c(p2)

--------------------------------> p axis

此处用>表示最短路线。 . 位于最短路径上，但由于该部分路径与 p 方向正交，因此它 "doesn't count" 朝向该方向的最小距离。

此处显示的最小路线 p1 -> c(p1) -> f(p2) -> p2 是上面的情况 1。

应该不难想象交换 p1 和 p2，在这种情况下，最小路线是从 p1 ->f(p1) -> c(p2) -> p2 出发（情况 2）。

pN == f(pN) == c(pN)的情况并没有太大的不同；那么，表达式 abs(pN - f(pN)) 或 abs(pN - c(pN)) 的部分只是零。

略有不同的情况是 f(p1) == f(p2):

f(p1) p1  c(p1)          f(p1) p1  c(p1)
  +---O>>>>+               +<<<O----+
           .               .
           .               .
  +-----O<<+               +>>>>>O--+
 f(p2) p2  c(p2)          f(p2) p2  c(p2)

--------------------------------> p axis

在这种情况下，最小路由可以是p1 -> f(p1) -> f(p2) -> p2或p1 -> c(p1) -> c(p2) -> p2（分别是情况3和4）。

Answer 3

正如 4castle 所提到的，如果只考虑输入整数，问题就微不足道了。在那种情况下，您永远不必在 "moved forward" 之后再 "move back"，因为您总是可以一次到达目的地。

但是由于最多每个departure/destination需要考虑一个浮点数，我们需要考虑3种情况，(警告：冗长的解释)。下面是一个 python2 带有解释的实现。

出发地和目的地的x坐标相同，是不是浮点数。在这种情况下，最短距离就是 y 坐标之间的绝对差值。反之亦然。

import math
class Location():
    def __init__(self, cord):
        self.x = cord[0]
        self.y = cord[1]

def perfectCity(departure, destination):
    l1 = Location(departure)
    l2 = Location(destination)

    if l1.x == l2.x and float(l1.x).is_integer() and float(l2.x).is_integer():
        return abs(l1.y-l2.y)
    if l1.y == l2.y and float(l1.y).is_integer() and float(l2.y).is_integer():
        return abs(l1.x-l2.x)

当departure中的其中一个坐标为浮点数时，则：
- 如果x坐标是浮点数，我们可以向后移动（向下舍入）或向前移动（向上舍入）。
- 如果y坐标是浮点数，我们可以向下移动（向下舍入）或向上移动（向上舍入）。
- 即使没有浮点坐标，上述逻辑也应该有效，因为我们在任一方向上移动了零个单位。
- 一旦我们计算出这些，我们就选择下面这些中的最小值，

return min(calc_round_up_dist(l1, l2), cal_round_down_dist(l1, l2))

Lets take an example of (0.4, 1) and (0.9, 3) 用于以下计算。

在计算round_up时我们需要计算3个距离：

round_up_distance：浮点坐标四舍五入后的值与原始浮点坐标的差值。如果没有浮点坐标，我们return零。 1 - 0.4 = 0.6 in the above example
non_floating_point区别：出发地的非浮点坐标与相应的目的地坐标的区别（注意，这可能是浮点数，也可能不是浮点数 abs(3-1) = 2 in the above example
目的地坐标中的出发浮点对应值0.9 in the above case与出发浮点四舍五入后的新值0.4 + 0.6(this is the round_up distance) = 1.0之差，即abs(0.9 - 1.0) = 0.1
将上面的所有 3 个相加我们得到 0.6 + 2 + .1 = 2.7 这是最短的距离。

四舍五入需要做相应的计算。我们选择两者中的最小值。 round_up和round_down的代码如下，

import math
class Location():
    def __init__(self, cord):
        self.x = cord[0]
        self.y = cord[1]

    def floating_point_round_up(self):
        if not float(self.x).is_integer():
            return math.ceil(self.x) - self.x
        if not float(self.y).is_integer():
            return math.ceil(self.y) - self.y
        return 0

    def floating_point_round_down(self):
        if not float(self.x).is_integer():
            return self.x - math.floor(self.x)
        if not float(self.y).is_integer():
            return self.y - math.floor(self.y)
        return 0

    def non_floating_point_diff(self, obj):
        if not float(self.x).is_integer():
            return abs(self.y - obj.y)
        if not float(self.y).is_integer():
            return abs(self.x - obj.x)
        return abs(self.y - obj.y)

    def floating_point_counterpart(self, obj):
        if not float(self.x).is_integer():
            return obj.x
        if not float(self.y).is_integer():
            return obj.y
        return obj.x

    def floating_point(self):
        if not float(self.x).is_integer():
            return self.x
        if not float(self.y).is_integer():
            return self.y
        return self.x

上下舍入函数如下,

def calc_round_up_dist(l1, l2):
    dist = l1.floating_point_round_up()
    diff = l1.non_floating_point_diff(l2)
    floating_point_counterpart = l1.floating_point_counterpart(l2)
    new_val = dist + l1.floating_point()
    return dist + diff + abs(new_val - floating_point_counterpart)

def cal_round_down_dist(l1, l2):
    dist = l1.floating_point_round_down()
    diff = l1.non_floating_point_diff(l2)
    floating_point_counterpart = l1.floating_point_counterpart(l2)
    new_val = l1.floating_point() - dist
    return dist + diff + abs(floating_point_counterpart - new_val)

终于调用了上面方法的main函数，

def perfectCity(departure, destination):
    l1 = Location(departure)
    l2 = Location(destination)

    if l1.x == l2.x and float(l1.x).is_integer() and float(l2.x).is_integer():
        return abs(l1.y-l2.y)
    if l1.y == l2.y and float(l1.y).is_integer() and float(l2.y).is_integer():
        return abs(l1.x-l2.x)

    return min(calc_round_up_dist(l1, l2), cal_round_down_dist(l1, l2))

Answer 4

这是一道关于 CodeSignal 的练习题： https://app.codesignal.com/company-challenges/uber/gsjPcfsuNavxhsQQ7

def solution(departure, destination):
    # go to the closest integer
    # I can only travel the path of an integer
    # if the number is a float I need to travel to an integer first
    # then travel to the destination

    x1, y1 = departure
    x2, y2 = destination
    res = 0
    
    # check if the coordinations are integers
    a = list(map(isInteger, departure))
    b = list(map(isInteger, destination))
    
    # if all are integers or if the corresponding elements are different
    if a[0] ^ b[0] or (a[0] and a[1] and b[0] and b[1]):
        return abs(x1-x2) + abs(y1-y2)
        
    if a[0]:
        res += abs(x2-x1)
        # cloest distance from y1 to y2
        res += getClosest(y1, y2)
    else:
        res += abs(y2-y1)
        # closes distance from x1 to x2
        res += getClosest(x1, x2)
    
    return res
    
def getClosest(y1, y2):
    cand1 = math.floor(y1)
    cand2 = math.ceil(y1)
    # find the integer closer to y1 to move to
    res1 = abs(y1-cand1) + abs(cand1-y2)
    res2 = abs(y1-cand2) + abs(cand2-y2)
    return min(res1, res2)
    
def isInteger(n):
    return n == round(n)

计算最短网格距离

calculating shortest grid distance

java

grid

distance