Last Updated: 25 Apr, 2021

Alex And Infinity Circle

Easy

Asked in company

Solve now

Problem statement

Alex wanted to buy a new keyboard, but due to the low battery in his GPS, he had to print his route on paper, now he wants to know if he can return safely to his home following the instructions written by him. The city of Alex can be represented by a 2D plane, and every location is denoted by ('X','Y') coordinates. Alex is currently standing at ( 0, 0 ) facing north.

The printed route contains a string with characters like:

'L' : which denotes he should turn to the left of the direction he is facing.
'R' : which denotes he should turn to the right of the direction he is facing. 
'G' : which denotes he should walk in the same direction by one unit.

Determine whether he can return home safely or not by following his instruction on the printed sheet.

Note:

He can follow the same printed set of instructions as many times as wanted.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ i.e., the length of the string.

The next line of each test case contains a string, ‘STR’ and each character of this 'STR' denotes the direction that Alex should move.

Output Format:

For each test case, print 'True' or 'False' whether he can return safely to his home, which is situated at (0,0), by following the given instructions a finite number of times.

Output for every test case will be printed in a separate line.

Note

You don’t need to print anything; It has already been taken care of.

Constraints:

1 <= T <= 50
1 <= N <= 100
‘STR’ = {‘L’, ‘R’ and ‘G’}.

Where ‘T’ is the number of test cases, 'N' is the length of string ‘STR’  and ‘STR’ is the string that denotes the direction that Alex should move. 

Time limit: 1 sec

Solve now

Approaches

01 Approach

We can observe that, if the person follows the given instructions one time in a printed sheet, if he arrives at his home i.e., his destination, then we can clearly say that our answer is 'True'.

If not, the above case is 'True' , let's simulate the walk of Alex in terms of variables,

Let's say our initial position is ('PosX', 'PosY') in terms of coordinates and denote the change in the direction of x by dx and y by dy.

So dx and dy can be represented by {{0, 1}, {1, 0}, {0, -1}, { -1, 0}}

E.g., initially Alex is facing north. If he walks in the same direction his coordinates will become,

(0,0) -> (0 + 0 , 0 + 1), or we could say ‘PosX’ := ‘PosX’ + dx[dir][0] and ‘PosY’ := ‘PosY’ + dy[dir][1], here dir is denoting direction he is facing, for dir:= 0, 1, 2, 3 it is representing

North, East, South, West, respectively.

Hence we could say that following instruction 'R' i.e., turn towards the right direction, can be called as 'dir' := ('dir' + 1) % 4, and following instruction 'L,' i.e., turn towards the left direction can be called as 'dir' := ('dir' - 1) % 4, we could also write it as 'dir' := ('dir' + 3) % 4

Now we could see that, and if 'dir' is equal to 0, after following the instruction and new coordinates are (NX, NY), both NX and NY denotes change or delta in coordinates of initial position i.e., (0,0), so following the same set of instructions K times, he will end up at (0 + k * NX, 0 + k * NY), so we can clearly see that Alex can never return to his home.

Now, if dir is not equal to 0, i.e., he ends up in a different direction than he was facing initially, we can claim that he will return to his home i.e., we can return 'True' safely, by following the instructions one or three times, let’s try to prove our claim we made.

Case 1: he ended up facing south, or if the value of 'dir' is 2 , so we can see that after following the same set of instructions, change in coordinates after executing instruction one more times we can say that it will be (-NX,-NY), so the total change becomes, (NX + (-NX) , NY + (-NY)) i.e., (0,0) so he will definitely be returning to his home.

Case 2: he ended up facing east or west, in this case, he will require 3 more iterations to return home, and the changes will become (NX + (-NY) + (-NX) + NY), NY + (-NX) + (-NY) + NX), i.e., equal to (0,0), here NX, NY denotes change after the first iteration, and we have denoted all the changes for each iteration together in a consecutive manner.

The steps of simulation can be called as follows:

Declare an 2-D array/list Direction ‘DIR’ = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}}.
Declare three variables and initialize them with ‘currDir’ = 0, ‘PosX’ = 0, ‘PosY’ = 0 that denotes our current direction, current x-coordinate , y-coordinate respectively.
Run a loop for ‘i’ = 0 to length of ‘STR’ -1 :
- ‘curChar’ = ‘STR[i]’.
- If ‘curChar’ is equal to ‘R’:
  - ‘currDir’ = ( ‘currDir’ + 1) % 4.
- Else If ‘curChar’ is equal to ‘L’:
  - ‘currDir’ = ( ‘currDir’ + 3 ) % 4.
- Else:
  - ‘PosX’ += D[‘currDir’][0].
  - ‘PosY’ += D[‘currDir’][1].
If ‘PosX’ is equal to 0 and ‘PosY’ is equal to 0:
- return True.
If ‘currDir’ is not equal to 0 :
- return True.
Finally, return False.

Solve now