Навигация на торе

Постановка задачи: подать команды управления на карте тора для перемещения бота в заданную точку.

Суть

  • питоновское (x2-x1) % n дает тороидальное расстояние на восток
  • легче думать в терминах «сначала направление»
  • go_best(East, West, (x2-x1)%n, (x1-x2)%n) — рабочее решение

Около трех лет назад я встретил эту задачу на CodinGame. Когда снова решал ее в TFWR, я полностью забыл подход, и тут хочу зафиксировать: что работает хорошо, а что приводит к громоздким конструкциям. Я стараюсь запоминать не готовые решения, а подходы. В этом посте сравниваю несколько способов думать о задаче и смотрю, какие программы из этого получаются.

Мой первый подход

def navigate(x, y):
  dx = x - get_pos_x()
  dy = y - get_pos_y()
  if dx:
    if dx > 0:
      for _ in range(dx):
        move(East)
    else:
      for _ in range(-dx):
        move(West)
  if dy:
    if dy > 0:
      for _ in range(dy):
        move(North)
    else:
      for _ in range(-dy):
        move(South)

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

Следующая идея: разворачивать направление, если оно дает не лучший путь по тору. Трюк забавный, посмотрим поближе:

if (dx > 0) ^ (n - dx < dx):
  go(East, abs(dx))
else:
  go(West, abs(dx))

Здесь используется свойство XOR: если второй параметр истинный, первый как бы инвертируется. Когда я понял, что ^ в TFWR не работает, заменил на ==, поскольку (a ^ b) == (a != b).

Но способ немного криповый, и я потратил время на более ясную формулировку. В итоге:

  1. Работаем с остатками по модулю n. Действительно, возможные координаты: 0,..., (n-1), а n эквивалентно 0.
  2. позиции можно рассматривать как вершины n-угольника
  3. две точки x1 и x2 делят n-угольник на две дуги
  4. в Python длины дуг считаются как (x2 - x1) % n для East и (x1 - x2) % n для West

И это все!


def go_best(dr, dl, nr, nl):
  d, s = [(dr, nr), (dl, nl)][dl<dr]
  for _ in range(s):
    move(d)

def nav(x2, y2):
  n = get_world_size()
  x1, y1 = get_pos_x(), get_pos_y()
  go_best(East, West, (x2 - x1) % n, (x1 - x2) %n)
  go_best(North, South, (y2 - y1) % n, (y1 - y2) %n)

P.S.

Здесь я использую трюк «bool как индекс», потому что в диалекте TFWR нет конструкции (v1 if cond else v2).
Обратите внимание: (x2 - x1) % n в Python критично важно именно в таком виде. Например, в C++ % работает иначе, и там обычно пишут (r % n + n) % n, чтобы получить тот же результат.