return to original position commands

[gevCplus]

Hello guys,

I have a problem kinda disturbing. Suppose I am at O(0,0) and I can go one step forward with f, turn 90 degrees right with r and 90degrees left with l. How would I create a function which, given a string of commands, will provide me with the number of remaining commands to return to my initial point?

I tried the following:

int dir(string d){
int m=d.size();
int countF=0, countR=0, countL=0;
for (i=0; i<m; ++i){
if (d[i]=='F') countF++;
else if (d[i]=='R') countR++;
else if (d[i]=='L') countL++;
}
return (countR-countF)+countL;
}

however, when the command is RF (which means turn 90degrees right and go one step forward), it fails because it returns zero but the actual steps to return to original position are 3.

[Duthomhas]

Draw it on a grid. Assuming you have no obstacles that make you detour in a direction AWAY from your starting point, the number of moves will be:

  abs(current_x - original_x) + abs(current_y - original_y)

Do you see why?

If you do have obstacles in your grid you will need an algorithm (like A*) to find your way back in the shortest-possible number of steps, since your journey to where you currently are is not guaranteed to be the shortest path.

Hope this helps.

[gevCplus]

Thanks. However, how the following command "RF" which means right 90 degrees and forward one step, will give three moves to go to the starting point (two right turns and onfe forward step) will print 3 with the above formula you wrote?

[mbozzi]

@Duthomhas gave you a formula for the number of moves, not commands.
Subject to the same condition (no obstacles), there are at most two turns needed to return to the starting position.