Algorithm for transiting in the Cartesian plane

Question

I’m trying to codify the solution to the classic problem of walking around the Cartesian plane, starting from the origin, based on a user-given input string. Being:

• And: anti-clockwise rotation of 90°;
• D: rotation time of 90°;
• F: moves one position forward;
• T: moves a rearward position;

The initial direction and direction are, respectively, east and right.

The exit to the String DFD is (-1,0) for example.

import java.util.Locale;
import java.util.Scanner;

public class Program {

    public static void main(String[] args) {
        Locale.setDefault(Locale.US);
        Scanner sc = new Scanner(System.in);
        String entrada = sc.nextLine();
        int x = 0, y = 0;
        int tamEntrada = 0;
        for(int i = 0; i <entrada.length(); i++) {
            if(entrada.charAt(i)=='D') {
                if(x!=0) {
                    int aux = y;
                    y=-x;
                    x=-aux;
                }
                else {
                    int aux=y;
                    y=x;
                    y=aux;
                    
                }   
            }
            else if(entrada.charAt(i)=='E') {
                if(x!=0) {
                    int aux=y;
                    y=x;
                    y=aux;
                    
                }
                else {
                    x=-y;
                    y=0;
                }   
            }
            else if(entrada.charAt(i)=='F') 
                x++;
            else if(entrada.charAt(i)=='T') 
                y--;
                
            
        }       
                
        
        System.out.println("(" + x +"," + y +")");
 
        sc.close();
    }

}

It works with rotations around the origin, but not with rotations of the origin. I can’t see a possible correction. Can you help me?

Answer 1

Initially I had understood that the rotation is only a change of direction, without leaving the place. But there is also the possibility to rotate relative to the origin, changing the position. Below are solutions for both cases.

---

Rotation without leaving the place

If the idea of rotation is only to change the direction, do not need to keep changing the values of x and y. Instead, you could have a variable to control the current direction and change it when you find a "D" or "E", and to advance or reverse a position, you simply change the values of x or y according to the direction:

Scanner sc = new Scanner(System.in);
String entrada = sc.nextLine();
int x = 0, y = 0;
int direcao = 0; // 0 - norte, 1 - leste, 2 - sul, 3 - oeste
for (int i = 0; i < entrada.length(); i++) {
    char c = entrada.charAt(i);
    switch (c) {
        case 'D':
            direcao = (direcao + 1) % 4;
            break;
        case 'E':
            direcao = (direcao + 3) % 4;
            break;
        case 'F':
        case 'T': // para frente ou para trás, a lógica é a mesma
            int passo = 1;
            if (c == 'T') { // se for para trás, o passo é negativo
                passo = -1;
            }
            switch (direcao) {
                case 0: // norte, muda só y
                    y += passo;
                    break;
                case 1: // leste, muda só x
                    x += passo;
                    break;
                case 2: // sul, muda só y
                    y -= passo;
                    break;
                case 3: // oeste, muda só x
                    x -= passo;
                    break;
            }
            break;
        default:
            // opção inválida, não faz nada (ou pode colocar alguma mensagem de erro, ou lançar exceção, etc)
    }
}

System.out.printf("(%d, %d)\n", x, y);

Note that when finding "D" or "E", I only change direction, without juggling "juggling" with the values of x and y. I only change the values of these when going to walk (checking the current direction and whether I should walk forward or backward).

The directions I considered as the "cardinal points", so "north" would be to advance on the y axis, "east" to advance on the x axis, "south" to recede on the y axis and "west" to recede on the x axis:

        norte
          |
          |
oeste ----|---- leste
          |
          |
         sul

For this I used the operator %, that returns the rest of the division. That is, if the current direction is 3 (west), to rotate clockwise I add 1 and take the rest of the division by 4, which results in zero (north). So if you rotate several times, I’ll have the directions 0, 1, 2, 3, 0, 1, 2, 3 and so on.

Already to rotate counterclockwise, I advance 3 positions (so I change from zero to 3, ie from north to west, and then to south, east, north, west, etc). I added up 3 times to subtract 1 because for negative values would go wrong (if I start from zero, I would have -1 % 4, which results in -1, which would be an invalid direction).

I also use printf to format the position instead of concatenating strings (it’s just to show another way to do).

Finally, you don’t need to close the System.in (as a general rule, we should close every resource we open, but the System.in is exception - read more about this here and here).

---

As already said at the beginning, I made "F" be "forward" and "T" be "backward" (the opposite of what is in the question), so the result of the above code for "DFD" is (1, 0). But if the idea is to be the other way around ("F" be "backwards"), just change the if up to:

if (c == 'F') { // "F" é "para trás"
    passo = -1;
}

---

Another alternative is to have an array with the steps:

int x = 0, y = 0;
int direcao = 0; // 0 - norte, 1 - leste, 2 - sul, 3 - oeste
int[][] passos = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
for (int i = 0; i < entrada.length(); i++) {
    char c = entrada.charAt(i);
    switch (c) {
        case 'D':
            direcao = (direcao + 1) % 4;
            break;
        case 'E':
            direcao = (direcao + 3) % 4;
            break;
        case 'F':
            x += passos[direcao][0];
            y += passos[direcao][1];
            break;
        case 'T':
            x -= passos[direcao][0];
            y -= passos[direcao][1];
            break;
        default:
            // opção inválida, não faz nada (ou pode colocar alguma mensagem de erro, ou lançar exceção, etc)
    }
}

Thus, the direction also serves as the index of the array passos, then passos[direcao] returns another array containing the increment to be done both in x how much in y.

In the above example I made "F" to be "forward", but if you want, just invert "F" and "T" in the code if you want "F" to be "backward".

---

Finally, another alternative (thanks to Bacchus by the algorithm) is to have two variables for the steps on the x and y axis, and go changing their values according to the direction:

int x = 0, y = 0;
int dx = 0, dy = -1;
int s;
for (int i = 0; i < entrada.length(); i++) {
    switch (entrada.charAt(i)) {
        case 'E':
            s = dx;
            dx = -dy;
            dy = s;
            break;
        case 'D':
            s = dx;
            dx = dy;
            dy = -s;
            break;
        case 'F':
            x += dx;
            y += dy;
            break;
        case 'T':
            x -= dx;
            y -= dy;
            break;
    }
}

---

Rotation in relation to origin

Now, if the idea of rotating is to change the position relative to the source, just add the position change in the above case:

int x = 0, y = 0, aux;
int direcao = 1; // 0 - norte, 1 - leste, 2 - sul, 3 - oeste
for (int i = 0; i < entrada.length(); i++) {
    char c = entrada.charAt(i);
    switch (c) {
        case 'D':
            direcao = (direcao + 1) % 4;
            // rotaciona 90 graus no sentido horário
            aux = x;
            x = y;
            y = -aux;
            break;
        case 'E':
            direcao = (direcao + 3) % 4;
            // rotaciona 90 graus no sentido anti-horário
            aux = x;
            x = -y;
            y = x;
            break;
        case 'F':
        case 'T': // para frente ou para trás, a lógica é a mesma
            int passo = 1;
            if (c == 'T') { // se for para trás, o passo é negativo
                passo = -1;
            }
            switch (direcao) {
                case 0: // norte, muda só y
                    y += passo;
                    break;
                case 1: // leste, muda só x
                    x += passo;
                    break;
                case 2: // sul, muda só y
                    y -= passo;
                    break;
                case 3: // oeste, muda só x
                    x -= passo;
                    break;
            }
            break;
        default:
            // opção inválida, não faz nada (ou pode colocar alguma mensagem de erro, ou lançar exceção, etc)
    }
}