CODEWITHSUNDEEP
javaalgorithm
Arefe
Arefe

Reputation: 1059

How to navigate a spider in a grid system?

I have a problem where it needs to navigate a spider in a grid system (X, Y co-ordinate) with proper instruction. Initially, the spider is in (0,0) and face towards the positive Y axis.

There are 3 possible instructions for the navigation: 'F' for forward (1 grid in the same direction ), 'R' for right turn (90 degree) and 'L' for left turn (90 degree) and initially, the spider faces towards positive Y axis.

Say, if I pass the direction String of "LFF", the position should be (-2,0). I solve the problem and the current state of code is as following,

public static void spiderNavigator(String str ){

    if( str == null || str.length() == 0)
        return;

    int [] initial = {0,0};

    boolean xPos = false, xNeg = false, yPos = true, yNeg = false; 

    char[] ch = str.toCharArray();

    for( char c: ch){

        // the initial position of the spider is towards the positive Y axis 

        if(c == 'L'){

            if(xPos){

                xPos = false;
                yPos = true;
            }

            else if ( xNeg){


                xNeg = false;
                yNeg = true;
            }

            else if(yPos){

                xNeg = true;
                yPos = false; 

            }

            else if (yNeg){

                yNeg = false;
                xPos = true;
            }
        }

        else if ( c == 'R'){

            if(xPos){

                xPos = false;
                yNeg = true;
            }

            else if ( xNeg){

                yPos = true;
                xNeg = false;
            }

            else if(yPos){

                yPos = false;
                xPos = true;
            }

            else if (yNeg){

                yNeg = false;
                xNeg = true;
            }

        }

        else if (c == 'F'){

            if(xNeg){

                initial[0]  -= 1;
            }

            else if (xPos){

                initial[0] += 1;
            }

            else if (yNeg){

                initial[1] -=1;
            }

            else if( yPos){

                initial[1] += 1;
            }

        }
    }

    System.out.println(Arrays.toString(initial));
}

However, the code feels quite ugly even to me. How can I design the algorithm in better way ?

Upvotes: 0

Views: 137

Answers (3)

Andreas
Andreas

Reputation: 159135

Here is a version built on a similar concept to the very nice answer by @MateuszDryzek, but without using trigonometric functions.

public static void spiderNavigator(String str) {
    if (str == null || str.isEmpty())
        return;
    int x = 0, y = 0, dir = 0;
    for (char c : str.toCharArray())
        if (c == 'R')
            dir = (dir + 1) % 4; // dir++: 0 -> 1 -> 2 -> 3 -> 0
        else if (c == 'L')
            dir = (dir + 3) % 4; // dir--: 3 -> 2 -> 1 -> 0 -> 3
        else if (c == 'F')
            if (dir == 0)
                y++; // 0: Up
            else if (dir == 1)
                x++; // 1: Right
            else if (dir == 2)
                y--; // 2: Down
            else
                x--; // 3: Left
    System.out.printf("(%d,%d)%n", x, y);
}

Upvotes: 1

Mateusz Dryzek
Mateusz Dryzek

Reputation: 661

Here's a shorter and more elegant solution:

public static void spiderNavigator(String str) {
    if (str == null || str.length() == 0)
        return;
    int[] initial = {0, 0};
    int angle = 90;
    char[] ch = str.toCharArray();
    for (char c : ch) {
        if (c == 'L') {
            angle = (angle + 90) % 360;
        } else if (c == 'R') {
            angle = (angle - 90) % 360;
        } else if (c == 'F') {
            initial[0] += (int) Math.cos(Math.toRadians(angle));
            initial[1] += (int)  Math.sin(Math.toRadians(angle));
        }
    }

    System.out.println(Arrays.toString(initial));
}

Angle represents the direction spider is facing, and using trigonometric functions you can easily calculate where it should move based on current position and an angle it is facing.

Upvotes: 4

Salvador Dali
Salvador Dali

Reputation: 222761

Here is how I would approach it.

  1. Have a direction variable spider_dir (where your spider is going to go now). It will store 4 different kind of values (like U, R, D, L).

  2. Have a function change_direction which takes a current direction a and value L or R and returns a new direction. Notice that if L is passed you need to take previous circular value in array of values (['U', 'R', 'D', 'L']) of your previous value. If R than the next circular value.

  3. Have a hash that maps your direction to your steps (assume +x, +y). U will be (0, 1), L will be (-1, 0).

Now that you have this simply iterate through your string and if you see F move add value to your current position depending on your spider_dir. If you see anything else - change your spider_dir depending on where to rotate and spider_dir

Upvotes: 1

Related Questions