Check if a given sequence of moves for a robot is circular or not

Question

Given a sequence of moves for a robot, check if the sequence is circular or not. A sequence of moves is circular if first and last positions of robot are same. A move can be on of the following.

G - Go one unit L - Turn left R - Turn right

Input:path[] = "GLGLGLG"

Output: Given sequence of moves is circular

This question can be solved easily:http://www.geeksforgeeks.org/check-if-a-given-sequence-of-moves-for-a-robot-is-circular-or-not/

My Question is what if we are only given a certain path and the robot can move on to that path infinite times. Ex: Input:path[]="GL"

So robot can move on this path 4 times thus a cycle is possible.

Please suggest some approach to check if a cycle is possible or not with the given path.

Answer 1

The result of performing a path from a starting point (x,y) and a starting direction d in {0,1,2,3} is two-fold:

1. Moving from (x,y) to (x',y')
2. Changing the direction from d to d'

Case 1: d == d'

There is no direction change. We either move away from the origin or not. In other words: cyclic if and only if (x,y) == (x',y')

Case 2: d == (d' + 2) mod 4

There is 180° direction change. Performing the path a second time will move the exact same vector back from (x',y') to (x,y). Cyclic.

Case 3 (Last): d == (d' + 1) mod 4 or d == (d' + 3) mod 4

There is a 90° direction change (either clockwise or counter-clockwise). Performing the path four times will move the exact same vector around a "rectangle" from (x,y) to (x + dx, y + dy), to (x + dx - dy, y + dy + dx), to (x + dx - dy - dx, y + dy + dx - dy), to (x + dx - dy - dx + dy, y + dy + dx - dy - dx) = (x, y), where dx = x'-x, dy = y'-y. Cyclic.

Thus the algorithm is fairly straight forward:

• Simulate path once starting with (x,y) == (0,0) and d = 0
• return cyclic iff d' != 0 || (x',y') == (0,0)

Answer 2

You can solve this problem by applying algorithm given in link for given sequence repeated 4 times.

Why?

After each sequence your direction can change:

• One to the left/right (in clockwise). Then after next three times your direction will be same as initial.
• Two to the left/right (in clockwise). Then after next sequence your direction will be same as initial, also after next three.
• Zero. Of Course your direction is same as initial, also after next three.

If after a few sequences your direction is the same as initial it mean the moves you are going to make will be the same as previous and after 4 sequences your direction always will be the same as initial.