Как работают алгоритмы для Expo go (Google Code Jam 2020 Round 1B)?

Question

Google Code Jam 2020, раунд 1B только что закончился, и я был довольно озадачен заданием «Экспо go» :

Вам нужно набрать (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 и предположим, что оно положительное. Затем есть один путь к go путем получения двоичного представления. Для каждой позиции, где она имеет 1, нужно от go до E. В других случаях нужно делать что-то еще.

Вместо одного E на шаге i можно также взять E при i+1 и W при 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
  = ...

Answer 1

Мы не можем получить одинаковый паритет, потому что только первый ход нечетен, поэтому он применяется либо к оси X, либо к оси Y, но не к обоим.

В этом случае деление на два просто удобный способ изучения каждого бита от наименее до наиболее значимого. Поскольку мы обязаны использовать каждый бит либо как вычитание (юг и запад), либо как сложение (север и восток), между двумя координатами могут возникнуть две проблемы, обнаруженные с помощью ошибки обоих этих операторов. :

(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 как степени двух, где 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)