LC 1041
--
Problem:
Instruction for a robot movement
L : turn left, R: turn right, G: go straight for 1 step
Given sequence of instruction will be repeated indefinitely.
Goal: given a sequence of instructions, check if robot forming a cycle.
Intuition:
if after one scan of execution, the robot faces different direction than starting direction(north), then won’t form a cycle.
or if the starting position and the ending position is the same, it forms a cycle
Algorithm:
define four directions: [<(0, 1), north>, <(1, 0), east>, <(0, -1), south>, <(-1, 0), west>]
as we know the initial direction is always north, so use a variable to represent the direction, cur = 0, here 0 is the index in the direction array.
loop thru each instruction char, and change the cur accordingly
use (x, y) to represent position, and update the x, y when G is encountered.
Code: