How to find shortest path in both directions of a number with over wrapping?

Question

Let's say I have to pick a number from 0-10.

The number I pick is 6.

The next number I want to pick is 0.

Now the rules are I have to keep incrementing the number by 1 or decrementing it by 1, the number can also wrap around the last number.

Now whats most important is to find which direction is shortest to take.

So

6-5-4-3-2-1-0 = 7 moves.
6-7-8-9-10-0 = 6 moves.

So incrementing wins in this case.

Well I came up with this code (probably broken)

int movesInc = 1;
int movesDec = 1;
int curNumber = 6;
int nextNumber = 0;
while((curNumber-- % 11) != nextNumber)
    movesDec++;

while((curNumber++ % 11) != nextNumber)
    movesInc++;

Now instead of using a while loop in both directions.. and finding out which takes less moves..

any way to do this without a while loop? just maybe some kind of mathematical equation?

Answer 1

Your code doesn't in fact work properly for two reasons:

You should be working modulo 11 instead of 10 (I see you've now fixed this per my earlier comment).

The % operator in Java and C++ doesn't deal with signs the way you think.

This does work, though it's not pretty, and it doesn't need loops.

It is tested for the start at 6 and end at 0, and I expect it works generally. For a different range, you'd of course need to change the number added when the result goes negative.

    int curNumber = 6;
    int nextNumber = 0;
    int movesInc = (nextNumber - curNumber) + 1
                    + ((nextNumber > curNumber)? 0: 11);
    int movesDec = (curNumber - nextNumber) + 1
                    + ((nextNumber < curNumber)? 0: 11);

The + 1 here is because you're counting both endpoints. The ternary expression is what handles going around 0.

Answer 2

int curNumber;
int nextNumber;
//calculate the modulo size by the highest number
int module = 10 + 1;
//calculate the direct distance to the nextNumber
int directDist = nextNumber - curNumber;

int nextNumberWrapped;
//calculate the wrapped distance, deciding the direction which wraps
if(directDist < 0)
    //wrapping in positive direction: 10 -> 0
    nextNumberWrapped = nextNumber + module;
else
    //wrapping in negative direction 0 -> 10
    nextNumberWrapped = nextNumber - module;
//calculating the wrapped distance
int wrappedDist = nextNumberWrapped - curNumber;
//assume the directDist to be shortest
int shortestDist = directDist;
//proof wrong if neccessary (compare the distances absolute values)
if(abs(wrappedDist) < abs(directDist))
   //save the signed distance
   shortestDist = wrappedDist;

The absolute value of shortestDist tells you the length of the shortest distance and the sign gives you the direction. So when the sign is negative you have to decrement and when it is positive you must increment to go the shortest way.

http://ideone.com/0yCDw

Also your example seems wrong. Each - between the numbers is one step, leaving you with one step less than you counted:

6-5-4-3-2-1-0
 ^ ^ ^ ^ ^ ^
 1 2 3 4 5 6  -> 6 moves
6-7-8-9-10-0
 ^ ^ ^ ^  ^ 
 1 2 3 4  5 -> 5 moves