Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Calculate the minimum number of commands to return robot to starting point

I had this interview question :

An input string controls the movement of a robot, "F" means move 1 step forward, "L" means turn 90 degrees to the left and "R" means turn 90 degrees to the right. E.g. "FLF" moves the robot one step forward, then turns it left by 90 degrees, then moves the robot one step forward.

Write a function that returns the minimum number of commands that the robot needs to return to it’s starting point after following all the input commands. You should return any characters that are not capital F, L, or R.

HINT: You may wish to track the robots position using (X,Y) coordinates, assuming it starts at (0,0).

Example:

  • "RF" returns 3 (robot must turn twice and move forward one step (e.g. "RRF")
  • "LFRFRFR" returns 1 (robot must step forward to return )
  • "FxLxLxFx" returns 0 (robot is already back at starting point )

Execution time limit is 3 secs

Input: string directions

Output: integer

I passed 7/10 tests with a long-winded approach (I couldn’t copy my code from their IDE). I tracked the movements successfully, got the right coordinates, and the steps back were easy: the sum of the absolute values of the x and y coordinates.

But then I struggled to figure out how I would factor in the minimum amount of commands when considering the direction changes. Can anyone help please?

Tags:

2

Answers


  1. 0

    The Manhattan distance is the easy part. We need to add to that the turn(s) that might be needed to face the robot in the correct direction for starting the journey back. In the case where the robot is neither on the correct X nor Y coordinate, the robot could either start in vertical direction or horizontal direction and then make one more turn later. We should choose the best of these two options, so to minimize the initial turns the robot might have to make.

    Here is a potential implementation:

    function shortestReturn(robotWalk) {
    let dir = 0; // We call the current robot direction: 0
    /*
           dir  1
             
             Y
             ^
             |
   dir 2 <---*------> X  dir 0
             |
             v
             
           dir 3
    */
    
    let x = 0, y = 0;
    for (const move of robotWalk) {
        if (move == "L") {
            dir = (dir + 3) % 4;
        } else if (move == "R") {
            dir = (dir + 1) % 4;
        } else if (move == "F") {
            x += (dir == 0) - (dir == 2);
            y += (dir == 1) - (dir == 3);
        } else {
            throw "Unexpected robot move: " + move;
        }
    }
    // The easy part: the Manhattan distance:
    const manhattan = Math.abs(x) + Math.abs(y);
    if (!manhattan) return 0; // Nothing to do!
    // Now robot needs to turn with the least turns to start the journey back
    if (!x || !y) { // Only need to move along one axis
        const targetDir = y > 0 ? 3 : y < 0 ? 1 : x > 0 ? 2 : 0;
        return manhattan + (((dir ^ targetDir) & 1) || (dir ^ targetDir));
    }
    // We need to move along two axes, and have 1 turn to make the switch.
    // There are two ways we could start the journey back. If current direction
    //   is not one of those two, then we need to add 1 for an initial turn.
    const quadrant = y > 0 ? (x > 0 ? 2 : 3 ) : (x < 0 ? 0 : 1);
    return manhattan + 1 + (quadrant != dir && (quadrant + 1) % 4 != dir);
}

console.log(shortestReturn("F")); // 3
console.log(shortestReturn("LF")); // 3
console.log(shortestReturn("FLF")); // 4
console.log(shortestReturn("FLFL")); // 3
console.log(shortestReturn("FLFLL")); // 3
console.log(shortestReturn("FLFR")); // 4
console.log(shortestReturn("FLFLFLFL")); // 0
console.log(shortestReturn("LLFRFRFL")); // 3
    Login or Signup to reply.
  2. 0

    I will present a solution in Ruby, which readers unfamiliar with the language should be able to follow.

    The approach I will suggest make uses of three hashes, which I will define as constants.

    The first two are used to determine the ending coordinates of the traveller’s journey.

    NEW_DIRECTION = {
  'N'=>{ 'L'=>'W', 'R'=>'E' },
  'E'=>{ 'L'=>'N', 'R'=>'S' },
  'S'=>{ 'L'=>'E', 'R'=>'W' },
  'W'=>{ 'L'=>'S', 'R'=>'N' }
}

    NEW_DIRECTION['N']['L'] #=> 'W', for example, means that if the traveller had been facing north and turned left they would then be facing west.

    COORDINATE_CHANGE = {
  'N'=>[0,1], 'W'=>[-1,0], 'S'=>[0,-1], 'E'=>[1,0]
}

    COORDINATE_CHANGE['W'] #=>[-1,0], for example, means that by moving one unit west the X coordinate of the current location is changed by -1 and the Y coordinate is left unchangced.

    We then have the following method to determine, at the end of the walk, the traveller’s coordinates and the direction they are facing, assuming they began the walk at the origin. I assume the traveller is initially facing north.

    def walk(str)  
  curr_dir = 'N'
  x_curr = 0
  y_curr = 0
  str.each_char do |op|
    raise ArgumentError, op unless ['F', 'L', 'R'].include?(op)
    if op == 'F'
      x_chg, y_chg = COORDINATE_CHANGE[curr_dir]
      x_curr += x_chg
      y_curr += y_chg
    else # op = 'L' or 'R'
      curr_dir = NEW_DIRECTION[curr_dir][op]
    end
  end
  [x_curr, y_curr, curr_dir]
end

    For example, if the walk were described by the string "FLFFRFL",

    walk("FLFFRFL") #=> [-2, 2, "W"]

    meaning the traveller would end at [-2, 2] and at that time would be facing West.

    The minimum number number of commands needed to return to the origin is the Manhattan distance plus the minimum number of turns required. The latter depends on which quadrant the traveller is in, or which axis they on, and the direction they are facing.

    That is given by the following hash, where the outer key is 0 if x = 0, else is x/|x| and the inner key is 0 if y=0, else is y/|y|.

    PENALTY = { 
   1 =>{  1=>{ "N"=>2, "E"=>2, "S"=>1, "W"=>1 },   # first quadrant, not on axis
         -1=>{ "N"=>1, "E"=>2, "S"=>2, "W"=>1 },   # fourth quadrant, not on axis
          0=>{ "N"=>1, "E"=>2, "S"=>1, "W"=>0 } }, # on positive x-axis
  -1 =>{  1=>{ "N"=>2, "E"=>1, "S"=>1, "W"=>2 },   # second quadrant, not on axis
         -1=>{ "N"=>1, "E"=>1, "S"=>2, "W"=>2 },   # third quadrant, not on axis
          0=>{ "N"=>1, "E"=>0, "S"=>1, "W"=>2 } }, # on negative x-axis
   0 =>{  1=>{ "N"=>2, "E"=>1, "S"=>0, "W"=>1 },   # on y-axis, positive x-axis
         -1=>{ "N"=>0, "E"=>1, "S"=>2, "W"=>0 },   # on y-axis, negative x-axis
          0=>{ "N"=>0, "E"=>0, "S"=>0, "W"=>0 } }  # at origin
}

    PENALTY[1][1]["N"] #=>2, for example, indicates that when located in the first quadrant, not on an axis (x > 0, y > 0), and facing north, two turns are required, one to turn left to face the positive Y axis and then when reaching the Y axis, another left turn to face the origin.

    PENALTY[-1][-1]["E"] #=>1, means when in the third quadrant and facing east, towards the Y axis, only one left turn is needed upon reaching that axis. Other values are determined similarly.

    We may then write a simple method to return the minimum number of commands to get back to the origin.

    def get_back(str)
  x_curr, y_curr, curr_dir = walk(str)
  x_curr.abs + y_curr.abs + PENALTY[x_curr<=>0][y_curr<=>0][curr_dir]
end

    x_curr.abs + y_curr.abs is, of course, the Manhattan distance. x_curr<=>0 returns -1 if x < 0, 0 if x = 0 and 1 if x > 0.

    For example,

    get_back("FLFFRFL") #=> 6
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search