[13 Feb 2020] Check if a given sequence of moves for a robot is circular or not


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


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 

Input: path[] = "GLLG"
Output: Given sequence of moves is circular
The idea is to consider the starting position as (0, 0) and direction as East (We can pick any values for these). If after the given sequence of moves, we come back to (0, 0), then given sequence is circular, otherwise not.
           N
           |
           |
   W -------------- E
           |
           |
           S
The move ‘G’ changes either x or y according to following rules.
a) If current direction is North, then ‘G’ increments y and doesn’t change x.
b) If current direction is East, then ‘G’ increments x and doesn’t change y.
c) If current direction is South, then ‘G’ decrements y and doesn’t change x.
d) If current direction is West, then ‘G’ decrements x and doesn’t change y.
The moves ‘L’ and ‘R’, do not change x and y coordinates, they only change direction according to following rule.
a) If current direction is North, then ‘L’ changes direction to West and ‘R’ changes to East
b) If current direction is East, then ‘L’ changes direction to North and ‘R’ changes to South
c) If current direction is South, then ‘L’ changes direction to East and ‘R’ changes to West
d) If current direction is West, then ‘L’ changes direction to South and ‘R’ changes to North.
Below is the implementation of above idea :
// A c++ program to check if the given path for a robot is circular or not
#include<iostream>
using namespace std;
  
// Macros for East, North, South and West
#define N 0
#define E 1
#define S 2
#define W 3
  
// This function returns true if the given path is circular, else false
bool isCircular(char path[])
{
  // Initialize starting point for robot as (0, 0) and starting
  // direction as N North
  int x = 0, y = 0;
  int dir = N;
  
  // Traverse the path given for robot
  for (int i=0; path[i]; i++)
  {
      // Find current move
      char move = path[i];
  
      // If move is left or right, then change direction
      if (move == 'R')
        dir = (dir + 1)%4;
      else if (move == 'L')
        dir = (4 + dir - 1)%4;
  
      // If move is Go, then change  x or y according to
      // current direction
      else // if (move == 'G')
      {
         if (dir == N)
            y++;
         else if (dir == E)
            x++;
         else if (dir == S)
            y--;
         else // dir == W
            x--;
      }
  }
  
   // If robot comes back to (0, 0), then path is cyclic
  return (x == 0 && y == 0);
}
  
// Driver program
int main()
{
    char path[] = "GLGLGLG";
    if (isCircular(path))
      cout << "Given sequence of moves is circular";
    else
      cout << "Given sequence of moves is NOT circular";
}
Output:
Given sequence of moves is circular
Time Complexity: O(n) where n is number of moves in given sequence.
// Write Java code here
// A Java program to check if
// the given path for a robot
// is circular or not
class GFG {
   
// Macros for East, North, South and West
  
// This function returns true if
// the given path is circular,
// else false
static boolean isCircular(char path[])
{
  // Initialize starting
  // point for robot as 
  // (0, 0) and starting
  // direction as N North
  int x = 0, y = 0;
  int dir = 0;
   
  // Traverse the path given for robot
  for (int i=0; i < path.length; i++)
  {
      // Find current move
      char move = path[i];
   
      // If move is left or
      // right, then change direction
      if (move == 'R')
        dir = (dir + 1)%4;
      else if (move == 'L')
        dir = (4 + dir - 1) % 4;
   
      // If move is Go, then 
      // change  x or y according to
      // current direction
      else // if (move == 'G')
      {
         if (dir == 0)
            y++;
         else if (dir == 1)
            x++;
         else if (dir == 2)
            y--;
         else // dir == 3
            x--;
      }
  }
   
   // If robot comes back to
   // (0, 0), then path is cyclic
  return (x == 0 && y == 0);
}
   
// Driver program
public static void main(String[] args)
{
    String path_ = "GLGLGLG";
    char path[] = path_.toCharArray();
  
    if (isCircular(path))
      System.out.println("Given sequence" +
      " of moves is circular");
    else
      System.out.println("Given sequence" +
      " of moves is NOT circular");
}
}

# Python program to check if the given path for a robot is circular
# or not
N = 0
E = 1
S = 2
W = 3
  
# This function returns true if the given path is circular,
# else false
def isCircular(path):
  
    # Initialize starting point for robot as (0, 0) and starting
    # direction as N North
    x = 0
    y = 0
    dir = N
  
    # Traverse the path given for robot
    for i in xrange(len(path)):
  
        # Find current move
        move = path[i]
  
        # If move is left or right, then change direction
        if move == 'R':
            dir = (dir + 1)%4
        elif move == 'L':
            dir = (4 + dir - 1)%4
  
        # If move is Go, then change x or y according to
        # current direction
        else:    # if move == 'G'
            if dir == N:
                y += 1
            elif dir == E:
                x += 1
            elif dir == S:
                y -= 1
            else:
                x -= 1
  
    return (x == 0 and y == 0)
  
# Driver program
path = "GLGLGLG"
if isCircular(path):
    print "Given sequence of moves is circular"
else:
    print "Given sequence of moves is NOT circular"
  
# This code is contributed by BHAVYA JAIN

Output:
Given sequence of moves is circular
Time Complexity: O(n) where n is number of moves in given sequence.









Comments

Post a Comment

Popular posts from this blog

Kth most frequent Character in a given String

  Given a string   str   and an integer  K , the task is to find the K-th most frequent character in the string. If there are multiple characters that can account as K-th most frequent character then, print any one of them. Examples: Input:  str = “GeeksforGeeks”, K = 3 Output:  f Explanation: K = 3, here ‘e’ appears 4 times & ‘g’, ‘k’, ‘s’ appears 2 times & ‘o’, ‘f’, ‘r’ appears 1 time. Any output from ‘o’ (or) ‘f’ (or) ‘r’ will be correct. Input:  str = “trichotillomania”, K = 2 Output:  l The idea is to Use the Characters as key in  Hashmap  and store their  occurrences in the string . Sort the Hashmap  and find the K-th character. Below is the implementation of the above approach. // C++ program to find kth most frequent // character in a string #include <bits/stdc++.h> using namespace std;     // Used for sorting by frequency. bool sortByVal( const pair< char , int >& a,                 const pair< char , int >& b) {      return a.second >
Read more

[16 Feb 2020] Given an array where every element occurs three times, except one element which occurs only once.

Find the element that appears once Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space. Examples : Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3} Output: 2 In the given array all element appear three times except 2 which appears once. Input: arr[] = {10, 20, 10, 30, 10, 30, 30} Output: 20 In the given array all element appear three times except 20 which appears once. Following is another O(n) time complexity and O(1) extra space method suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence. Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000 Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0; Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of
Read more

[17 Feb 2020] Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side.

Find the nearest smaller numbers on left side in an array Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side. Examples: Input:  arr[] = {1, 6, 4, 10, 2, 5} Output:         {_, 1, 1,  4, 1, 2} First element ('1') has no element on left side. For 6, there is only one smaller element on left side '1'. For 10, there are three smaller elements on left side (1, 6 and 4), nearest among the three elements is 4. Input: arr[] = {1, 3, 0, 2, 5} Output:        {_, 1, _, 0, 2} Expected time complexity is O(n). // C++ implementation of efficient algorithm to find // smaller element on left side #include <iostream> #include <stack> using namespace std;   // Prints smaller elements on left side of every element void printPrevSmaller(int arr[], int n) {     // Create an empty stack     stack<int> S;       // Traverse all array elements     for (int i=0; i<n; i++)  
Read more