Check if a set of moves is circular or not
Check if a given set of moves is circular or not. A move is circular if its starting and ending coordinates are the same. The moves can contain instructions to move one unit in the same direction (M), to change direction to the left of current direction (L), and to change direction to the right of current direction (R). Assume that the initial direction is North.
For example,
Set of moves MRMLMRMRMMRMM is circular
The idea is simple – start with (0, 0) as the starting coordinates and North as the starting direction and linearly read each instruction from the input string. For every instruction, update the coordinates of the current location (x, y) if the instruction is MOVE or update the current direction if the instruction is GO LEFT or GO RIGHT. The move is circular if we are back to the starting coordinates (0, 0) in the end.
Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <iostream> #include <string> using namespace std; // Function to check if the given set of moves is circular or not bool isCircularMove(string str) { // start from coordinates (0, 0) int x = 0, y = 0; // assume that the initial direction is North char dir = 'N'; // read each instruction from the input string for (int i = 0; i < str.length(); i++) { switch (str[i]) { // move one unit in the same direction case 'M': if (dir == 'N') { y++; } else if (dir == 'S') { y--; } else if (dir == 'E') { x++; } else if (dir == 'W') { x--; } break; // change direction to the left of the current direction case 'L': if (dir == 'N') { dir = 'W'; } else if (dir == 'W') { dir = 'S'; } else if (dir == 'S') { dir = 'E'; } else if (dir == 'E') { dir = 'N'; } break; // change direction to the right of the current direction case 'R': if (dir == 'N') { dir = 'E'; } else if (dir == 'E') { dir = 'S'; } else if (dir == 'S') { dir = 'W'; } else if (dir == 'W') { dir = 'N'; } } } // if we are back to starting coordinates (0, 0), // the move is circular return (!x && !y); } int main() { string str = "MMRMMRMMRMM"; if (isCircularMove(str)) { cout << "Circular move"; } else { cout << "Non-circular move"; } return 0; } |
Output:
Circular move
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
class Main { // Function to check if the given set of moves is circular or not public static boolean isCircularMove(String str) { // start from coordinates (0, 0) int x = 0, y = 0; // assume that the initial direction is North char dir = 'N'; // read each instruction from the input string for (char ch: str.toCharArray()) { switch (ch) { // move one unit in the same direction case 'M': if (dir == 'N') { y++; } else if (dir == 'S') { y--; } else if (dir == 'E') { x++; } else if (dir == 'W') { x--; } break; // change direction to the left of the current direction case 'L': if (dir == 'N') { dir = 'W'; } else if (dir == 'W') { dir = 'S'; } else if (dir == 'S') { dir = 'E'; } else if (dir == 'E') { dir = 'N'; } break; // change direction to the right of the current direction case 'R': if (dir == 'N') { dir = 'E'; } else if (dir == 'E') { dir = 'S'; } else if (dir == 'S') { dir = 'W'; } else if (dir == 'W') { dir = 'N'; } } } // if we are back to starting coordinates (0, 0), // the move is circular return (x == 0 && y == 0); } public static void main(String[] args) { String str = "MMRMMRMMRMM"; if (isCircularMove(str)) { System.out.println("Circular move"); } else { System.out.println("Non-circular move"); } } } |
Output:
Circular move
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
# Function to check if the given set of moves is circular or not def isCircularMove(s): # start from coordinates (0, 0) x = y = 0 # assume that the initial direction is North dir = 'N' # read each instruction from the input string for c in s: # move one unit in the same direction if c == 'M': if dir == 'N': y = y + 1 elif dir == 'S': y = y - 1 elif dir == 'E': x = x + 1 elif dir == 'W': x = x - 1 # change direction to the left of the current direction if c == 'L': if dir == 'N': dir = 'W' elif dir == 'W': dir = 'S' elif dir == 'S': dir = 'E' elif dir == 'E': dir = 'N' # change direction to the right of the current direction if c == 'R': if dir == 'N': dir = 'E' elif dir == 'E': dir = 'S' elif dir == 'S': dir = 'W' elif dir == 'W': dir = 'N' # if we are back to starting coordinates (0, 0), # the move is circular return x == 0 and y == 0 if __name__ == '__main__': s = 'MMRMMRMMRMM' if isCircularMove(s): print('Circular move') else: print('Non-circular move') |
Output:
Circular move
The time complexity of the above solution is O(n), where n is the length of the input string and doesn’t require any extra space.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)