एल्गोरिदम एक स्ट्रिंग को अच्छा या बदसूरत बनाने के लिए

Question

मुझे निम्नलिखित पहेली के लिए एल्गोरिदम खोजने में कठिनाई हो रही है- एक स्ट्रिंग को बदसूरत कहा जाता है यदि इसमें पंक्ति में 3 स्वर हैं, या पंक्ति में 5 व्यंजन हैं, या दोनों। एक स्ट्रिंग को अच्छा कहा जाता है अगर यह बदसूरत नहीं है। आपको एक स्ट्रिंग एस दिया जाता है, जिसमें अपरकेस अक्षरों ('ए' - 'जेड') और प्रश्न चिह्न ('?') होते हैं। क्या आप एक एल्गोरिदम खोज सकते हैं जो बताता है कि स्ट्रिंग को वर्णमाला के साथ प्रश्न चिह्नों को प्रतिस्थापित करके अच्छा बनाया जा सकता है?

उदाहरण -

1. "ईई FFFF?" - नहीं कर सकते अच्छा बनाया जा। एक व्यंजन या स्वर को डालने से यह बदसूरत हो जाएगा।

2. "एच ?? लोअर ??" - अच्छा बनाया जा सकता है।

पीएस - होमवर्क नहीं, बल्कि इंटरनेट पर प्रोग्रामिंग पहेली का एक हिस्सा है।

Answer 1

ध्यान दें कि केवल एक ही तार जो संभावित रूप से बदसूरत हो सकता है वे हैं जो पहले से ही दिए गए अक्षरों के आधार पर बदसूरत हैं या जिनके पास केवल सिंगलटन प्रश्न चिह्न हैं। यहां सबूत का स्केच है:

• दो प्रश्न चिह्नों के किसी भी सेट के लिए, बाएं प्रश्न को बाएं पड़ोसी के विपरीत चिह्नित करें और सही प्रश्न सही पड़ोसी के विपरीत चिह्नित करें। जैसे वी? सी सी वीसीवीसी बनना चाहिए। इस तरह के एक प्रतिस्थापन कभी भी बदसूरत नहीं हो सकता है अगर यह पहले से बदसूरत नहीं था।
• तीन या अधिक प्रश्न चिह्नों के किसी भी सेट के लिए, ऊपर के रूप में बाएं और दाएं प्रश्न चिह्न सेट करें और फिर वी और सी के बीच मध्य प्रश्न चिह्नों को वैकल्पिक करें। इसके परिणामस्वरूप लगातार दो वी या सी का परिचय हो सकता है, लेकिन कभी भी तीन नहीं।

तो, हमें दो साधारण मामलों के साथ छोड़ दिया गया है।

• जांचना कि क्या स्ट्रिंग पहले से ही बदसूरत है, एक सीधा रेगेक्स है।
• एकमात्र परिदृश्य जिसमें एक सिंगलटन एक स्ट्रिंग बदसूरत बदल सकता है, यदि प्रश्न चिह्न में एक तरफ दो स्वर हैं और दूसरी तरफ चार व्यंजन हैं; लेकिन आप केवल उन लोगों की जांच नहीं कर सकते, क्योंकि प्रतिस्थापन ऐसे पैटर्न पेश कर सकता है (ईई? एफएफएफ? ईई पर विचार करें)। लेकिन इस बिंदु पर, आप सही पड़ोसी के विपरीत डालने से प्रत्येक सिंगलटन प्रश्न चिह्न को हल करके, बाएं से दाएं काम करके जांच कर सकते हैं, जब तक कि दो स्वर/चार व्यंजन पैटर्न मौजूद न हो तो स्ट्रिंग बदसूरत हो जाती है और रोकती है।

Answer 2

क्या आपने पूरे वर्णमाला के माध्यम से पुनरावृत्ति करने की कोशिश की है और यह देखने के लिए हर संयोजन की कोशिश कर रहा है कि यह 'बदसूरत' है या नहीं?

प्रत्येक प्रश्न चिह्न को एक अक्षर के साथ प्रतिस्थापित करने का प्रयास करें, फिर वैधता की जांच करें, यह सबसे आसान, कम से कम इष्टतम तरीका है। उदाहरण के लिए:

ईईएफ? डी ??

मैं भरना शुरू कर दूंगा? इन संयोजनों के साथ:

एएए AAB एएसी एएडी

आदि

संपादित करें: नहीं आप पूरी वर्णमाला से अधिक पुनरावृति करने के लिए, बस ए और बी पर्याप्त हैं नहीं है। या वास्तव में, बस कोई स्वर और कोई व्यंजन।

Answer 3

यहां कुंजी है: बदसूरत से अच्छे में परिवर्तनशीलता या तो व्यंजनों या स्वरों की एक निश्चित लंबाई पर आधारित है। तो यदि एक ब्लॉक को अच्छे में बदलने के लिए आवश्यक रूप से किसी अन्य ब्लॉक की कुरूपता की भविष्यवाणी की जाती है, तो यह नहीं किया जा सकता है।

कार्यान्वयन व्यक्ति के लिए अपना स्वयं का होमवर्क करने के लिए बहुत आलसी अभ्यास के रूप में छोड़ दिया गया है। :-)

Answer 4

आप क्या कर सकते हैं प्रत्येक प्रश्न चिह्न पर पुनरावृत्ति है, और एक स्वर या प्रश्न चिह्न डालने के हर संभव संयोजन का परीक्षण करें।

उदाहरण के लिए (वी => स्वर, सी => व्यंजन)

1. "ई? FFFF"
   VVVCCCC
   VVCCCCC
   दो संभावनाएं हैं, और जैसा कि आप पहले से ही पता है, वे दोनों कर रहे हैं बदसूरत।

   [aeiouAEIOU]{3}|[a-zA-Z&&[^aeiouAEIOU]]{5} 
   

   अब, एक ? स्वरों के एक दृश्य के अंदर होता है अगर, आप इसे एक व्यंजन में बदल सकते हैं:

Answer 5

एक regex पैटर्न है कि बदसूरत से मेल खाएगी नहीं है। यदि यह व्यंजनों के अनुक्रम के अंदर होता है, तो आप इसे एक स्वर में बदल सकते हैं।समस्या तब होती है जब प्रश्न चिह्न सीमा पर दिखाई देता है:

[aeiouAEIOU]{2}\?[a-zA-Z&&[^aeiouAEIOU]]{4} 
[a-zA-Z&&[^aeiouAEIOU]]{4}\?[aeiouAEIOU]{2} 

इनमें से प्रत्येक मामले में, कोई समाधान नहीं है। अब, यदि दो प्रश्न चिह्न हैं, तो एक दूसरे के बाद, समस्या होती है यदि अनुक्रम हैं:

[aeiouAEIOU]{2}\?\?[aeiouAEIOU]{2} 
[a-zA-Z&&[^aeiouAEIOU]]{4}\?\?[a-zA-Z&&[^aeiouAEIOU]]{4} 

इनका कोई समाधान नहीं है। यदि दो से अधिक प्रश्न चिह्न हैं, तो आप इसे हल कर सकते हैं।

तो, पैटर्न के लिए उन लोगों के लिए खोजें, साथ ही "शुद्ध" बदसूरत पैटर्न। यदि उनमें से कोई भी होता है, तो आप बदल नहीं सकते हैं। अन्यथा, यह ठीक है।

Answer 6

हास्केल में एक समाधान:

import System (getArgs) 

nicePart :: Int -> Int -> String -> Bool 
nicePart 3 _ _ = False 
nicePart _ 5 _ = False 
nicePart _ _ "" = True 
nicePart v c ('?':as) = nicePart (v+1) 0 as || nicePart 0 (c+1) as 
nicePart v c (a:as) 
    | a `elem` "AEIOU" = nicePart (v+1) 0 as 
    | otherwise  = nicePart 0 (c+1) as 

nice :: String -> Bool 
nice as = nicePart 0 0 as 

main = getArgs >>= print . nice . unwords 

समारोह कितने लगातार स्वर और व्यंजन वर्तमान बिंदु तक देखा गया है की गिनती रहता है। यदि बहुत सारे हैं तो यह False लौटाता है। यदि कोई प्रश्न चिह्न मिलता है, तो दो रिकर्सिव कॉल किए जाते हैं, एक प्रश्न के रूप में प्रश्न चिह्न को गिनती है, एक व्यंजन के रूप में, यह जांचता है कि इनमें से कोई भी बदलाव अच्छा है या नहीं।

Answer 7

जैसा कि बताया गया है, एक क्रूर बल है, जो बेहद अक्षम अक्षम काम करेगा। मज़ा उन क्षमताओं को जोड़ने में है जो संभावनाओं की 2 ** एन सूची को ट्रिम करते हैं।

1. सबसे पहले, किसी भी से पहले मूल स्ट्रिंग के खिलाफ त्वरित "बदसूरत रेगेक्स" मैच करें? प्रतिस्थापन। यदि आपको कोई मैच मिलता है, तो स्ट्रिंग को स्पष्ट रूप से अच्छा नहीं बनाया जा सकता है।

2. अगला के लिए अगला देखें? अवसर, वे? जो कि दोनों तरफ से दूसरी तरफ झुका हुआ है? चार पदों के लिए। देखें कि इनमें से कोई भी वी या सी के रूप में तय किया जाना चाहिए, या फिर वे पूरी तरह से स्ट्रिंग को अयोग्य घोषित कर सकते हैं (जैसे ओपी के उदाहरण 1 में)। अगर उन्हें वी या सी तय किया जाना चाहिए, तो ऐसा करें और जारी रखें।

3. बाद की रणनीतियों में अधिक शामिल हो: डबल? खंडों में बाएं और दाएं दोनों की जांच शामिल है? एक वी/सी उनके संबंधित बायीं/दायीं अगल पात्रों पर आधारित आवश्यकता, आदि

Answer 8

के लिए यहाँ परीक्षण मामलों है कि मैं उस पर फेंक दिया के एक मुट्ठी भर से काम करने के लिए लगता है कि सी # में एक समाधान है। [Regex अभिव्यक्ति के कुछ हिस्सों में पिछले एक उत्तर देने से उधार लिया गया था।]

public static bool IsWordNiceable(string word, int maxVowels, int maxConsonants) 
{ 
    if (IsUgly(word, maxVowels, maxConsonants)) return false; 

    int i = 0; 
    while ((i = word.IndexOf('?', i)) != -1) 
    { 
     string newWord = word.Substring(0, i) + "a" + word.Substring(i+1); 
     bool vowelMakesNice = IsWordNiceable(newWord, maxVowels, maxConsonants); 

     newWord = word.Substring(0, i) + "b" + word.Substring(i + 1); 
     bool consonantMakesNice = IsWordNiceable(newWord, maxVowels, maxConsonants); 

     if (!(vowelMakesNice || consonantMakesNice)) return false; 
     i++; 
    } 

    return true; 
} 


private static bool IsUgly(string word, int maxVowels, int maxConsonants) 
{ 
    string consonants = "bcdfghjklmnpqrstvwxyz"; 
    string vowels = "aeiou"; 
    string uglyRegex = string.Format("([{0}]{{{1},{1}}})|([{2}]{{{3},{3}}})", vowels, maxVowels, consonants, maxConsonants); 

    Match match = Regex.Match(word.ToLower(), uglyRegex); 
    return match.Success; 
} 

यह पहली दिए गए शब्द का परीक्षण करती है अगर यह (प्रश्न चिह्न सहित, यदि कोई हो) बदसूरत है देखने के लिए के रूप में है। फिर यह शब्द के माध्यम से loops, पहले "?" की जगह एक स्वर और एक व्यंजन दोनों के साथ, और नए शब्द का उपयोग कर खुद को बुलाता है। यदि स्वर और व्यंजन प्रतिस्थापन दोनों इसे अच्छा बनाने में असफल होते हैं, तो वह शाखा झूठी (बदसूरत) लौटती है।