जांचें कि कोई सर्कल

Question

मौजूद है, तो मुझे Google साक्षात्कार के दौरान यह पूछा गया था। हमें एक स्ट्रिंग दी गई है जिसमें अक्षर- एफ, एल, आर शामिल हैं। - निर्देश है कि एक रोबोट

F- एक चरण से आगे बढ़ता है।

एल-टर्न बाएं।

आर-दाएं मुड़ें।

स्ट्रिंग लंबाई 2500 वर्ण तक हो सकती है।

स्ट्रिंग स्वयं को अनंत काल चलाती है। हमें यह बताने की जरूरत है कि त्रिज्या के साथ एक सर्कल मौजूद है, आर (आर कोई असली संख्या हो सकती है), जैसे कि रोबोट कभी सर्कल छोड़ देता है। मैं इस बिंदु पर फंस गया था। मैंने उत्तल हॉल का उपयोग करने के बारे में सोचा था, लेकिन अनंत काल के लिए इसे कैसे जांचें। कोड के साथ विस्तार की सराहना की जाएगी। कृपया मदद करे। अग्रिम धन्यवाद

Answer 1

1. प्रत्येक रन (एक रन दिया स्ट्रिंग के सभी आदेशों को क्रियान्वित कर रहा है एक बार) दो चीजों को बदलता है: जिस दिशा में रोबोट दिखता है और उसकी स्थिति (यानी, प्रत्येक रन इसे कुछ वेक्टर द्वारा बदलता है (इस वेक्टर की दिशा दौड़ से पहले इसकी प्रारंभिक दिशा पर निर्भर करती है) और इसे घुमाती है)।

2. संभावित दिशाओं की संख्या 4 है। इस प्रकार, अनुकरण को चलाने के बाद 4 बार यह उसी दिशा में दिखता है जैसा कि प्रारंभ में हुआ था (प्रत्येक रगड़ उसी कोण से घूमता है)।

3. यही कारण है कि लगातार 4 रनों को बिना किसी घुमाव के कुछ वेक्टर द्वारा इसे स्थानांतरित किया जाता है।

4. इस प्रकार, हम केवल पंक्ति में 4 बार सिमुलेशन चला सकते हैं और देख सकते हैं कि यह मूल बिंदु में बंद हो गया है या नहीं। यदि ऐसा होता है, तो हम उस न्यूनतम सर्कल को पा सकते हैं जिसमें उसका पथ होता है। अन्यथा, ऐसा कोई सर्कल मौजूद नहीं है।

Answer 2

स्ट्रिंग चलाएं, देखें कि रोबोट इसके अंत में कहां है और किस दिशा में यह दिखता है।

यदि यह मूल पर वापस आ गया है, तो निष्पादन के दौरान मूल से अधिकतम दूरी लें और आर की तुलना करें।

ताकि कोई इस तरह के आर यदि यह अनिश्चित काल के लिए एक ही उन्मुखीकरण के रूप में यह शुरुआत में था, तो यह मूल से दूर स्थानांतरित होगा,:

यह मूल में वापस नहीं है, तो अपने उन्मुखीकरण जाँच मौजूद।

यदि इसकी शुरुआत में इसकी तुलना में अलग-अलग अभिविन्यास है, तो यह स्ट्रिंग के 4 या 2 पुनरावृत्तियों के बाद मूल पर वापस आ जाएगा, इस पर निर्भर करता है कि यह मूल मूल अभिविन्यास के बाएं/दाएं ओर उन्मुख है या नहीं, इसके विपरीत, क्रमशः। अब स्ट्रिंग के 2 निष्पादन के बाद अधिकतम दूरी लें। (सरल मामले भेद दिखा देंगे कि यह 2 फांसी के बाद इसकी अधिकतम दूरी का दौरा किया है जाएगा, फिर चाहे अवधि 2 या 4 फांसी है।)

Answer 3

आप नई स्थिति की गणना करने के लिए 1 पुनरावृत्ति चलाएंगे, नया, नया कहें। फिर आप 4 और पुनरावृत्तियों की गणना करेंगे ताकि यह देखने के लिए कि रोबोट न्यूएक्स-न्यूज पर वापस आ गया है या नहीं। यदि ऐसा है, तो सर्कल मौजूद है, अन्यथा नहीं।

त्रिज्या अपने पुनरावृत्ति में रोबोट की अधिकतम दूरी होगी।

कोड कार्यान्वयन -

//North, South, East, West directions 
#define N 0 
#define S 1 
#define E 2 
#define W 3 

// Function to compute the new pos (x, y, dir) after completing one iteration of the string. 
// It will also update the max radius. 
void findNewPos(char *str, int *origdir, int *origx, int *origy, double *maxrad) { 
    int i, len, x, y, dir; 

    dir = *origdir; 
    x = *origx; 
    y = *origy; 

    len = strlen(str); 
    i=0; 

    //Iterate through each character 
    while(i < len) { 
    char c = str[i]; 

    switch(c) { 
    case 'L': // Turn left 
     switch(dir) { 
     case N: 
     x--; 
     dir = W; 
     break; 
     case S: 
     x++; 
     dir = E; 
     break; 
     case E: 
     y++; 
     dir = N; 
     break; 
     case W: 
     y--; 
     dir = S; 
     break; 
     } 
     break; 

    case 'R': // Turn right 
     switch(dir) { 
     case N: 
     x++; 
     dir = E; 
     break; 
     case S: 
     x--; 
     dir = W; 
     break; 
     case E: 
     y--; 
     dir = S; 
     break; 
     case W: 
     y++; 
     dir = N; 
     break; 
     } 
     break; 

    case 'F': // Go forward 
     switch(dir) { 
     case N: 
     y++; 
     dir = N; 
     break; 
     case S: 
     y--; 
     dir = S; 
     break; 
     case E: 
     x++; 
     dir = E; 
     break; 
     case W: 
     x--; 
     dir = W; 
     break; 
     } 
     break; 
    } 

    // Update max radius till now 
    double rad = x*x + y*y; 
    if(rad > *maxrad) 
     *maxrad = rad; 
    i++; 
    } 

    *origx = x; 
    *origy = y; 
    *origdir = dir; 
} 

// Function to compute the max radius of movement, if bounded 
double findCircle(char *str) { 
    int x=0, y=0, dir=N; 
    int refx, refy; 
    double radius = 0, maxrad = 0; 

    // Starting from origin(x=0, y=0), find new pos after single iteration 
    findNewPos(str, &dir, &x, &y, &maxrad); 

    refx = x; 
    refy = y; 

    // Find new positions after 4 more iterations 
    findNewPos(str, &dir, &x, &y, &maxrad); 
    findNewPos(str, &dir, &x, &y, &maxrad); 
    findNewPos(str, &dir, &x, &y, &maxrad); 
    findNewPos(str, &dir, &x, &y, &maxrad); 

    // Are we back to position where we were after 1st iteration? 
    if(x == refx && y == refy) { 
    printf("Circle exists %f!\n", maxrad); 
    radius = sqrt(maxrad); 
    } 
    else { 
    printf("Circle does not exist!\n"); 
    radius = -1; 
    } 

    return radius; 
} 

Answer 4

एक बार दिया स्ट्रिंग के माध्यम से दोहराएं और विस्थापन और जिस दिशा में आप अंत ध्यान दें। यदि विस्थापन गैर-शून्य है और एकल पुनरावृत्ति के लिए रोबोट के लिए प्रारंभिक और समाप्ति दिशाएं समान हैं, तो आपके रोबोट को किसी मंडली में शामिल नहीं किया जा सकता है, अन्यथा यह हो सकता है।

चित्र:
आकृति में, मान लीजिए कि रोबोट दिए गए स्ट्रिंग के एक ही पुनरावृत्ति के बाद बिंदु ए से बिंदु बी पर जाता है। अब, कोण एबीसी (9 0 - थेटा) है, जो 90 डिग्री के बराबर कोण एबीडी बनाता है। सभी पक्षों के बराबर, और प्रत्येक कोण 90 डिग्री के बराबर है, चतुर्भुज एबीडीई एक वर्ग है। यह थेटा (तीव्र या घुमावदार) के किसी भी मूल्य के लिए सच है। एक ही पुनरावृत्ति के बाद अंतिम दिशा छोड़ दी जाती है तो सबूत समान होगा। दक्षिण के लिए, रोबोट अंक ए और बी

इसलिए आपकी समस्या के समाधान के रूप में, आप जांच सकते हैं कि प्रारंभिक और समाप्ति दिशा समान है और प्रारंभिक और समापन स्थिति नहीं है वही, रोबोट दिए गए स्ट्रिंग के एक पुनरावृत्ति को पूरा करने के बाद।

Answer 5

string doesCircleExists(string commands) { 
    int dir=1; //1 is east; 2 north etc. 
    pair<int,int> pos; 
    pos = make_pair(0,0); //start at origin 
    for(int i=0;i<4;i++) { 
    for(int i=0;i<commands.size(); i++) 
    { 
     if(commands[i]=='F') 
     { 
     if(dir==1) pos.first++; if(dir==2) pos.second++; 
     if(dir==3) pos.first--; if(dir==0) pos.second--; 
     } 
     if(commands[i]=='L') {dir++; dir = dir%4;} 
     if(commands[i]=='R') {dir--; dir = dir%4;} 
    } 
    } 
    if(pos.first==0 && pos.second==0 && dir=1) return "YES"; else return "NO"; 

}

Answer 6

यह काम हो सकता है:

def encircular(string): 

    ini_pos = [0,0] 
    position = [0,0] 
    direction = 'N' 
    directions = {'NL':'W','NR':'E','EL':'N','ER':'S','SL':'E','SR':'W','WL':'S','WR':'N'} 
    forward = {'N':[0,1],'E':[1,0],'S':[0,-1],'W':[-1,0]} 
    for i in range(4): 
     for i in string: 
      if i == 'F': 
       position = [x+y for x,y in zip(position,forward[direction])] 
      else: 
       #print(direction+i) 
       direction = directions[direction+i] 
       #print (direction) 
    if ini_pos == position: return 'YES' 
    else : return 'NO' 

Answer 7

def robot_bot(string): 
    face= 0 
    pos=[0,0] 
    string= string.upper() 
    dirc={0:[1,0],90:[0,1],180:[-1,0],270:[0,-1],360:[1,0],-90:[0,-1],-180:[-1,0],-270:[0,1]} 
    for ch in string: 
     if ch == "R": face -= 90 
     elif ch == "L": face += 90 
     if ch == "G": 
      pos[0]+=dirc[face][0] 
      pos[1]+=dirc[face][1] 
     print(pos,face) 
     if abs(face) == 360: face=0 
    return(True if pos==[0,0] else False) 

Answer 8

#include <bits/stdc++.h> 
using namespace std; 
struct point 
{ 
    int x; 
    int y; 
    int dir; 
}; 
int mod4(int a) 
{ 
    if(a%4 < 0) 
     return (a%4 + 4); 
    else 
     return a%4; 
} 
int main() 
{ 
    struct point p; 
    p.x = 0; 
    p.y = 0; 
    p.dir = 0; 
    string s;cin>>s; 
    int j; 
    for(int i=0;i<4*s.size();i++) 
    { 
     j = i%s.size(); 
     if(s[j] == 'F') 
     { 
      if(p.dir == 0)//north 
       p.y++; 
      if(p.dir == 1)//east 
       p.x++; 
      if(p.dir == 2)//south 
       p.y--; 
      if(p.dir == 3)//west 
       p.x--; 
     } 
     if(s[j] == 'L') 
     { 
      p.dir--; 
      p.dir = mod4(p.dir); 
     } 
     if(s[j] == 'R') 
     { 
      p.dir++; 
      p.dir = mod4(p.dir); 
     } 
     //cout<<p.x<<" "<<p.y<<" "<<p.dir<<endl; 
    } 
    if(p.x == 0 && p.y ==0 && p.dir == 0) 
     cout<<"YES"<<endl; 
    else 
     cout<<"NO"<<endl; 
}