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.