Robot Bounded In Circle

  • "G": go straight 1 unit;
  • "L": turn 90 degrees to the left;
  • "R": turn 90 degrees to the right.
Input: instructions = "GGLLGG"
Output: true
Explanation: The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.
Input: instructions = "GG"
Output: false
Explanation: The robot moves north indefinitely.
Input: instructions = "GL"
Output: true
Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...
  • 1 <= instructions.length <= 100
  • instructions[i] is 'G', 'L' or, 'R'.

var isRobotBounded = function (instructions) {
const origin = [0,0]
let dir = 0;

const moving = () => {
for(let str of instructions){
if(str === "L"){
dir -= 1
if(dir < 0) dir += 4;
} else if (str === 'R') {
dir += 1
if(dir > 3) dir = dir % 4;
} else {
if(dir === 0){
origin[1] += 1
} else if(dir === 1) {
origin[0] -= 1
} else if(dir === 2) {
origin[1] -= 1
} else {
origin[0] += 1
}
}
}
}

let times = 0;
while(times < 4){
moving();
if(origin[0] === 0 && origin[1] === 0) return true
times += 1
}
return false
};

Approach 1: One Pass

  • After at most 4 cycles, the limit cycle trajectory returns to the initial point x = 0, y = 0. That is related to the fact that 4 directions (north, east, south, west) define the repeated cycles' plane symmetry.
  • Let’s use numbers from 0 to 3 to mark the directions: north = 0, east = 1, south = 2, west = 3. In the array directions we could store corresponding coordinates changes, i.e. directions[0] is to go north, directions[1] is to go east, directions[2] is to go south, and directions[3] is to go west.
  • The initial robot position is in the center x = y = 0, facing north idx = 0.
  • Now everything is ready to iterate over the instructions.
  • If the current instruction is R, i.e. to turn on the right, the next direction is idx = (idx + 1) % 4. Modulo here is needed to deal with the situation - facing west, idx = 3, turn to the right to face north, idx = 0.
  • If the current instruction is L, i.e. to turn on the left, the next direction could written in a symmetric way idx = (idx - 1) % 4. That means we have to deal with negative indices. A more simple way is to notice that 1 turn to the left = 3 turns to the right: idx = (idx + 3) % 4.
  • If the current instruction is to move, we simply update the coordinates: x += directions[idx][0], y += directions[idx][1].
  • After one cycle we have everything to decide. It’s a limit cycle trajectory if the robot is back to the center: x = y = 0 or if the robot doesn't face north: idx != 0.
  • Time complexity: O(N), where N is a number of instructions to parse.
  • Space complexity: O(1) because the array directions contains only 4 elements.

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

4 Recommendations of Arduino Types for Beginners

Uno R3 DIP Arduino

Some Amazing Tips to Host Business Mobile Apps

Host Business Mobile Apps

Download OCR Text Scanner Pro 1.7.1 (Patched) For Android — Free — Latest Version

I asked 12 software engineers how to get hired at their companies, and here’s what they said…

Calling Out A0 Devs

How to recover a folder from an old VM disk ( Azure )

The benefits of writing honest code

CSS Basic: Background

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
SunJet Liu

SunJet Liu

More from Medium

Making Convolutions Less Convoluted

Cosmopolitan Pilgrim

Mexican Gothic — A Horrific Treat

Wave Function: an in-depth exploration (Wave function# 3)