Check If there exists a Circle
I was asked this during a Google Interview. We are given a string consisting of letters- F,L,R. - which is the instruction a robot follows
F- goes forward by one step.
L-turn left.
R- turn right.
String length can be upto 2500 characters.
The string runs itself infinite times. We need to tell if there exists a circle with a radius, r( r can be any real number), such that the robot never leaves the circle. I was stuck at this point.I thought of using convex hull, but how to check it for infinite times.Explanation with code will be appreciated. Please help. Thanks in advance
Answer
- Each run(one run is executing all commands of the given string once) changes two things: the direction which the robot looks to and its position(that is, each run shifts it by some vector(the direction of this vector depends on the its initial direction before the run) and rotates it).
The number of possible directions is 4. Thus, after running the simulation 4 times it looks in the same direction as it did initially(each rub rotates it by the same angle).
That's why 4 consecutive runs just shift it by some vector without any rotation.
Thus, we can just run the simulation 4 times in a row and see if it stopped in the original point. If it did, we can find the minimum circle that contains its path. Otherwise, no such circle exists.