Torus navigation

Problem statement: issue control commands on torus map to navigate bot to a given point.

Essence

  • pythonic (x2-x1) % n gives eastward toroidal distance
  • easier to think in "direction first" terms
  • go_bestt(East, West, (x2-x1)%n, (x1-x2)%n) is a solution

About three years ago I met this challenge on codingame platform. Now when I tried to solve it again in TFWR I totally forget the approach and here I want to make a note on what works well and what leads to a cumbersome constructions. I always try not to memorize solutions, but approaches instead. In this post I want to compare different ways of thinking about this problem and check programs we have as a result.

My first approach

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)

It's a straightforward way to think about this problem: to select a direction and to walk in this direction. I think it is not bad, in general, while can be improved using functions. Then I tried to extend this approach to handle torus topology. It worked, but the result (obviously) was so cumbersome, I decided not to publish it.

Next idea was to reverse direction. Logic behind is like "we reverse our decision to go East or West if it gives not the best distance on torus". I think this trick is funny, so, let's check it closer

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

Here we use an interesting property of XOR gate: it gives the inversion of the first parameter, if the second is true. When I realized that ^ doesn't work in TFWR, I used == instead. (a ^ b) == (a != b).

But this way is kinda creepy and I dwelled for a while, what it the best way of thinking about this problem in a right way. The results are:

  1. We are working with remainders modulo n. Indeed, possible coordinates are 0, ..., (n-1) and n is equivalent to 0
  2. we can think about our positions as of positions on vertices of n-gon
  3. if we have two points x1, x2 they divide the n-gon into two arcs
  4. in python we can calculate lengths of arcs using (x2 - x1) % n for east and (x1 - x2) % n for west directions

And that is it!


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.

Here I use "boolean as index" trick because there is no (v1 if cond else v2) construction in the TFWR dialect.
Note that (x2 - x1) % n is Pythonic expression is important because, for example, in C++ operator % works in a little bit different way and there you are to write something like (r%n+n)%n to have the same result.