Find closest path to number in a cycling order

user_15945105 0
Viewed 37

I'm trying to find the closest path to a number which can go in a cycling order, for example:

  • I have the numbers 0 to 4 which could go in both directions(after 4 comes 0, before 0 comes 4).
  • If I'm currently at 1 and I want to go to 2, the closest path would be going forward.
  • If I'm currently at 3 and I want to go to 0, the closest path would be going forward.
  • If I'm currently at 2 and I want to go to 1, the closest path would be going backwards.

That was probably clear enough after the first 1 or 2 examples.

I'd like to implement something similar in code, I can easily do that with a couple of if's etc, but I'm pretty sure there must be a better easier way to determine the closest path using math, not really sure how to though, if someone could help with approaching this that would be very useful,

pseudocode math
1 Answers

Using modular arithmetic, you could define one function to compute forward distances, another function to compute backwards distances, and a third to decide between the two. Here is a python solution which should be easily translatable to other languages (though different languages handle how negative numbers are treated by the mod operator, so some care might be required):

def forward(i,j,n):
    return (j-i) % n

def backwards(i,j,n):
    return (i-j) % n

def best_direction(i,j,n):
    f = forward(i,j,n)
    b = backwards(i,j,n)
    if f < b:
        return 'forward'
    elif b < f:
        return 'backwards'
    else:
        return 'either'

Your test cases (run in a Python shell):

>>> best_direction(1,2,5)
'forward'
>>> best_direction(3,0,5)
'forward'
>>> best_direction(2,1,5)
'backwards'

Another test case, showing the possibility of a tie:

>>> best_direction(3,0,6)
'either'

Obviously, you can inline the two 1-line functions into the definition of best_direction to get it down to a single function definition if you want.

user_49962480
Related