时间戳

首页 > 解决方案 > Expogo 的算法如何工作（Google Code Jam 2020 Round 1B）？

python - Expogo 的算法如何工作（Google Code Jam 2020 Round 1B）？

问题描述

Google Code Jam 2020，第 1B 轮刚刚结束，我对“Expogo”任务感到非常困惑：

您需要(X, Y)从 开始(0, 0)。您可以向北/向东/向南/向西移动。有时i你的步长是2**i（从 i=0 开始，每一步增加一）。

找到通向 (X, Y) 的最短序列，或者如果不可能到达那里。

查看几个解决方案（例如Linguo、ctunoku、roflmoqkz、jaems、chaotic_iak），我经常看到这种解决方案（取自 chaotic_iak，应用黑色）：

def solve(x, y):
    if x % 2 == y % 2:
        return "IMPOSSIBLE"
    s = ""
    while x != 0 or y != 0:
        # Handling the easy cases:
        if abs(x) + abs(y) == 1:
            if x == 1:
                return s + "E"
            if x == -1:
                return s + "W"
            if y == 1:
                return s + "N"
            if y == -1:
                return s + "S"

        # This is what I don't get:
        if x % 2 == 1:
            y //= 2
            if (y % 2 == 1 and x % 4 == 1) or (y % 2 == 0 and x % 4 == 3):
                x = (x - 1) // 2
                s += "E"
            else:
                x = (x + 1) // 2
                s += "W"
        else:
            x //= 2
            if (x % 2 == 1 and y % 4 == 1) or (x % 2 == 0 and y % 4 == 3):
                y = (y - 1) // 2
                s += "N"
            else:
                y = (y + 1) // 2
                s += "S"

我没有得到这个问题的关键见解。首先，为什么同价位就意味着不可能？我可以看到 (1, 1) 是不可能的，因为你可以很容易地得到第一个 1，然后你只能得到 2。但是如何证明它是不可能的呢？

我的主要问题：为什么作者除以 2？步骤的顺序很重要。这些步骤的长度为 2**i，其中 i 是第 i 个步骤（从 0 开始）。他们为什么要加+1？

我所理解的

让我们只关注 X 并假设它是积极的。然后去那里的一条路径是通过获取二进制表示。对于它有的每个位置，都1需要去E。在其他情况下，需要做其他事情。

除了采取一个Eat step 之外i，还可以采取一个Eati+1和一个Wat i。这样，一个人可以有无限多的表示：

5 = 101
  = E0E : 4 + 1
  = EEW : 4 + 2 - 1
  = EW0E : 8 - 4 + 1
  = EWW0E : 16 - 8 - 4 + 1
  = EWWW0E : 32 - 16 - 8 - 4 + 1
  = ...

标签： pythonalgorithm

解决方案

我们无法获得相同的奇偶校验，因为只有第一步是奇数，所以它要么应用于 X 轴，要么应用于 Y 轴，而不是两者。

在这种情况下，除以 2 只是从最低位到最高位检查每个位的便捷方式。由于我们不得不将每个位用作减法（南和西）或加法（北和东），因此两个坐标之间可能会出现两个问题，这两个问题都可以通过这两个语句的失败来检测：

(x % 2 == 0 and y % 4 == 3)

(x % 2 == 1 and y % 4 == 1)

首先，我们可以在两个坐标的下一个位置都有一个未设置的位，这意味着 x 有一个零并且y % 4 = 1，这意味着 y 的下一个位也是零。在这种情况下，我们将 1 添加到 y，这实际上是添加2^p，其中p是指针的当前位置。这会将 y 坐标的当前设置位向左移动，并在当前位置创建一个零（减法）。

示例：(4, 1)

x: 100
y:   1
    ^--- problem

solution: add 2^0 to y, creating a subtraction

110

south, north, east

第二个问题是 x 和 y 都可以在下一个位置设置一个位。那时 x 有一个设置位 和y % 4 == 3，这意味着 y 的当前位和下一个位都已设置。在这种情况下，将2^p（当前位）添加到 y 将翻转 y 中的这两个位（以及所有与左侧相邻的位），因此使用第一位作为减法，并释放第二位供 x 使用。

示例：(6, 3)

x: 110
y:  11
    ^--- problem

solution: add 2^0 to y, creating a subtraction

x: 110
y: 100
   ^--- problem

solution: add 2^1 to x, creating a subtraction

x: 1000
y:  100

   south, west, north, east
x:       - 2            + 8  = 6
y: - 1           + 4         = 3

根据一些示例的代码结果，我想出了这个例程。它表明最小二进制数 ,N表示x + y + s为 2 的幂，其中s等于NOT(N)（即 的减法s，或“西”和“南”运动可以生成x + y），可以通过添加 来生成x + y + (NOT(x + y) >> 1)。

function f(x, y){
  let xy = x + y
  console.log((xy).toString(2))
  let p = 1
  let s = 0
  xy >>= 1
  while (xy){
    if (!(xy & 1))
      s |= p
    xy >>= 1
    p <<= 1
  }
  console.log(s.toString(2))
  console.log((x + y + s).toString(2))
  console.log('')
}

var cs = [
  [8, 9],
  [2, 3],
  [10, 5]
]

for (let [x,y] of cs)
  f(x,y)

推荐阅读