👩🏼‍🎨 👨🏾‍🔧 🥉 शब्द के खेल के लिए समाधान ढूँढना। बोरान आवेदन 📼 👨🏿‍⚖️ 🤱🏾

प्रविष्टि

ऐसे कई खेल हैं जहां खिलाड़ी को अक्षरों के एक विशिष्ट सेट से शब्दों की खोज करने की आवश्यकता होती है। यहाँ दो सबसे लोकप्रिय हैं।
1.4 Pics 1 शब्द (4 Pics 1 शब्द) AppStore , Google Play
इस खेल में बहुत सारे कार्यान्वयन हैं, लेकिन हर किसी के पास एक विचार है।
2. स्लोवेनिया (वर्ड्समैनिया) ऐपस्टोर, गूगल प्ले

पहले गेम का सार: 4 चित्र दिए गए हैं, एक अनुमानित शब्द की लंबाई और अक्षरों का एक सेट, आप किसी भी क्रम में पत्र चुन सकते हैं।

दूसरे का सार यह है कि अक्षरों से भरे 4x4 क्षेत्र में, आपको यथासंभव अधिक से अधिक शब्द खोजने की आवश्यकता है, प्रत्येक सेल से आप अगले लंबवत, क्षैतिज और तिरछे स्थानांतरित कर सकते हैं।

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

समस्या का बयान

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

क्यों बोरान?

मानक C ++ पुस्तकालयों में, संरचनाएं पहले से ही कार्यान्वित की जाती हैं जो मानचित्र और unordered_map (हैश मैप) जैसे एकल अनुरोधों का तुरंत जवाब दे सकती हैं। लेकिन इन संरचनाओं की मदद से कार्य का कार्यान्वयन बोरमोन के लिए विषम दवाओं में हीन होगा, क्योंकि यह कार्य की विशेषताओं को ध्यान में रखेगा। मूल्यों की गणना एक पेड़ होगी, क्योंकि यह प्रत्येक पत्र से अगले एक को पुनरावर्ती खोजने की कोशिश करेगा। बोर भी एक पेड़ है, इसलिए शब्दों की खोज सभी शब्दों की कुल लंबाई के लिए सबसे खराब स्थिति में होगी, साथ ही पुनरावृत्तियों की संख्या, जब तक कि एल्गोरिथ्म शब्दकोश में एक संक्रामक संक्रमण तक नहीं पहुंचता है, व्यवहार में, ऐसा संक्रमण काफी जल्दी प्राप्त होता है। एल्गोरिथ्म अधिक कुशलता से काम करेगा जब एक स्ट्रिंग एस युक्त होता है, उपसर्ग के रूप में, एक स्ट्रिंग पी शब्दकोश से संबंधित होता है, इस मामले में खोज एस लंबाई पर जाएगी, और अन्य सभी पीएस को खोज एस के जवाब में जोड़ा जाएगा।

इसके बाद, आपको शब्दों को क्रमबद्ध रूप में प्रदर्शित करना होगा।

कार्यान्वयन

भागों में समस्या के समाधान के कार्यान्वयन पर विचार करें।

समावेशन

कंसोल और फ़ाइल I / O, iostream, fstream प्रदान करना आवश्यक है। हमें मानक एसटीएल टेम्पलेट की आवश्यकता है: वेक्टर - एक बोरान, स्ट्रिंग और सेट के निर्माण के लिए - परिणामों को संग्रहीत करने और समान शब्दों को काटने के लिए मिला, छंटाई के लिए एल्गोरिथ्म।

समावेशन

#include <iostream> #include <fstream> #include <vector> #include <string> #include <set> #include <algorithm>

स्थानीयकरण को सक्षम किए बिना, रूसी वर्णों का उपयोग करने के लिए, ताकि इस तरह के कोड को आसानी से अन्य एन्कोडिंग में समायोजित किया जा सके, इनपुट और आउटपुट के लिए एक साधारण नमूना स्ट्रिंग का उपयोग करने का निर्णय लिया गया। यह एक नमूना है जब रूसी वर्णमाला कंसोल में प्रवेश करते हैं और एक नमूना प्राप्त किया जाता है, जब FstreamSample फ़ाइल से पढ़ता है।
अगला बोरॉन के प्रत्येक शीर्ष के लिए संरचना का वर्णन है, यह प्रत्येक अक्षर द्वारा संक्रमणों को संग्रहीत करेगा, या 0 यदि कोई संक्रमण नहीं है, तो संरचना में isLeaf चर का उपयोग करके यह भी संकेत दिया जाता है कि इस शीर्ष में एक निश्चित शब्द समाप्त होता है।
हम बोरान भंडारण के लिए कंटेनरों की घोषणा करते हैं, परिणामों के लिए एक बफर, और स्वरूपित आउटपुट।

विज्ञापन

 #define ALPHABET_SIZE 33 const char ConsoleSample[ALPHABET_SIZE] = { -96, -95, -94, -93, -92, -91, -15, -90, -89, -88, -87, -86, -85, -84, -83, -82, -81, -32, -31, -30, -29, -28, -27, -26, -25, -24, -23, -20, -21, -22, -19, -18, -17 }; const char FstreamSample[ALPHABET_SIZE] = { -32, -31, -30, -29, -28, -27, -72, -26, -25, -24, -23, -22, -21, -20, -19, -18, -17, -16, -15, -14, -13, -12, -11, -10, -9, -8, -7, -4, -5, -6, -3, -2, -1 }; typedef struct { unsigned child[ALPHABET_SIZE]; bool isLeaf; } node; node NullNode = {NULL}; vector<node> Trie; set<string> Res; vector<string> Output;

शब्दों को बोर में जोड़ें

फ़ंक्शन इनपुट के रूप में एक रेखा प्राप्त करता है, इसके माध्यम से जाता है, साथ ही बोरान के साथ चलता है, यदि शीर्ष से कोई संक्रमण नहीं होता है, तो बोरान में एक नया वर्टेक्स जोड़ा जाता है, और जोड़ा वर्टेक्स में संक्रमण इंडेक्स का उपयोग करके वर्तमान शीर्ष पर लिखा जाता है। अंतिम संक्रमण जोड़ने के बाद, अंतिम शीर्ष पर isLeaf चर का मान सही में बदल जाता है, यहाँ शब्द समाप्त होता है।

शब्द जोड़ें

 void TrieAddWord(string &S) { unsigned CurrentNode(0); for (auto i(S.begin()); i != S.end(); ++i) { if (Trie[CurrentNode].child[*i] == 0) { Trie.push_back(NullNode); Trie[CurrentNode].child[*i] = Trie.size() - 1; CurrentNode = Trie.size() - 1; } else { CurrentNode = Trie[CurrentNode].child[*i]; } } Trie[CurrentNode].isLeaf = true; }

शब्दकोश डाउनलोड करें

सुविधा के लिए, सभी शब्दों के लिए, अनुरोध के प्रसंस्करण के दौरान, प्रतीक संख्याओं को स्थानांतरित कर दिया जाएगा, अर्थात, प्रतीक 'a' का मान 0 होगा, और प्रतीक 'i' का मान 32 होगा। सांकेतिक वर्ण नमूने में एक वर्ण के लिए एक तुच्छ खोज का उपयोग करके इसे प्रतिस्थापित करेगा। । ऐसा कार्यान्वयन सरल है, लेकिन शब्दकोश को लोड करने में अतिरिक्त समय लगता है, लेकिन यह इतना महत्वपूर्ण नहीं है, शब्दकोश एक बार लोड होता है, और फिर आप कई बार कार्यक्रम के लिए अनुरोध सबमिट कर सकते हैं।

स्ट्रिंग एन्कोडिंग

 void EncodeString(string &S, const char Sample[]) { for (auto i(S.begin()); i != S.end(); ++i) { for (char j(0); j != ALPHABET_SIZE; ++j) { if (*i == Sample[j]) { *i = j; break; } } } }

डिक्शनरी लोडिंग फ़ंक्शन फ़ाइल नाम प्राप्त करता है और उसमें से सभी शब्दों को पढ़ता है, लाइनों को एन्कोडिंग करता है और फिर उन्हें जंगल में जोड़ता है। यदि आप इसे सभी फ़ाइलों के लिए चलाते हैं, तो फ़ंक्शन एक साथ कई शब्दकोशों को लोड कर सकता है।

शब्दकोश डाउनलोड करें

 void LoadDictonary(char *Filename) { ifstream in(Filename); string Buff; while (!in.eof()) { in >> Buff; EncodeString(Buff, FstreamSample); TrieAddWord(Buff); } in.close(); }

आउटपुट छँटाई

स्लोवोमेनिया गेम में सबसे लंबे शब्दों को प्राप्त करने के लिए, सबसे पहले, आपको रिवर्स ऑर्डर में लंबाई द्वारा लाइनों को क्रमबद्ध करना होगा, क्योंकि कंसोल में आउटपुट करते समय, टेक्स्ट नीचे से ऊपर तक स्क्रॉल करता है, इसलिए सबसे लंबे शब्दों को अंत में प्रदर्शित करने की आवश्यकता होती है। एक खेल में, शब्द जितना बड़ा होता है, जाहिर है इसके लिए अधिक अंक दिए जाते हैं। ऐसा करने के लिए, आपको एल्गोरिदम से इसे सॉर्ट करने के लिए एक साधारण तुलनित्र फ़ंक्शन लिखना होगा।

तुलनित्र

 bool cmp(string A, string B) { if (A.size() >= B.size()) { return false; } else return true; }

शब्द समाधान लगता है

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

चक्कर

 void GuessWordBypass(unsigned N, __int8 X, bool Used[], string &S, string W, short &L) { if (W.size() > L) return; for (__int8 i(0); i != S.size(); ++i) { if (i == X) continue; if (!Used[i]) { if (Trie[N].child[S[i]] != 0) { Used[i] = true; GuessWordBypass(Trie[N].child[S[i]], i, Used, S, W + S[i], L); Used[i] = false; } } if (Trie[N].isLeaf && W.size() == L) { Res.insert(W); } } }

और फिर एक ऐसा फ़ंक्शन जो शब्द के सभी अक्षरों के एक ट्रावेल्स की प्रारंभिक शुरुआत को लागू करता है।

लांच

 void GuessWord(string &S, short &L) { bool *Used = new bool [S.size()]; memset(Used, 0, S.size()); for (__int8 i(0); i != S.size(); ++i) { if (Trie[0].child[S[i]] != 0) { Used[i] = true; GuessWordBypass(Trie[0].child[S[i]], i, Used, S, S.substr(i, 1), L); Used[i] = false; } } delete [] Used; }

खेल स्लोवेनिया के लिए समाधान का कार्यान्वयन

सामान्य तौर पर, बाईपास स्वयं कोई अलग नहीं होगा, लेकिन अंतर यह होगा कि यहां आप केवल पड़ोसी कोशिकाओं में जा सकते हैं, और किसी भी पर नहीं, और खोज को किसी भी लम्बाई के शब्दों का पता लगाना चाहिए। चूंकि 4x4 फ़ील्ड को एक-आयामी सरणी द्वारा दर्शाया गया है, इसलिए यह स्पष्ट नहीं है कि पड़ोसी कोशिकाओं में कैसे जाना है, हम इस पर विचार करेंगे कि इसे कैसे लागू किया जाए।
यदि सेल क्षेत्र की सीमाओं पर नहीं खड़ा है, तो -5 से 5 तक संख्याओं को जोड़कर, उन्हें -2, 0 और 2 को छोड़कर।

यदि सेल सीमा पर है, तो सीमा से परे जाने वाली अन्य कोशिकाओं के लिए संक्रमण को रोकना भी आवश्यक है।

चक्कर

 void WordsmaniaCheatBypass(unsigned N, __int8 X, bool Used[], string &S, string W) { __int8 TransitDenied[11] = {0}; for (__int8 i(-2); i <= 2; i += 2) TransitDenied[i + 5] = true; if (X % 4 == 0) for (__int8 i(-5); i <= 3; i += 4) TransitDenied[i + 5] = true; if (X < 4) for (__int8 i(-5); i <= -3; ++i) TransitDenied[i + 5] = true; if (X % 4 == 3) for (__int8 i(-3); i <= 5; i += 4) TransitDenied[i + 5] = true; if (X >= 12) for (__int8 i(3); i <= 5; ++i) TransitDenied[i + 5] = true; for (__int8 i(-5); i <= 5; ++i) { if(TransitDenied[i + 5]) continue; __int8 tmp = X + i; if (!Used[tmp]) { if (Trie[N].child[S[tmp]] != 0) { Used[tmp] = true; WordsmaniaCheatBypass(Trie[N].child[S[tmp]], tmp, Used, S, W + S[tmp]); Used[tmp] = false; } } if (Trie[N].isLeaf) { Res.insert(W); } } }

लांच

 void WordsmaniaCheat(string &S) { bool Used[16] = {0}; for (__int8 i(0); i != 16; ++i) { if (Trie[0].child[S[i]] != 0) { Used[i] = true; WordsmaniaCheatBypass(Trie[0].child[S[i]], i, Used, S, S.substr(i, 1)); Used[i] = false; } } }

मुख्य समारोह

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

मुख्य

 int main() { Trie.push_back(NullNode); LoadDictonary("Dictonary.txt"); string Word; char mode; while (true) { cin >> mode; switch (mode) { case '1': short L; cin >> Word >> L; EncodeString(Word, ConsoleSample); GuessWord(Word, L); break; case '2': cin >> Word; EncodeString(Word, ConsoleSample); WordsmaniaCheat(Word); break; } cout << "==================" << endl; for (auto i(Res.begin()); i != Res.end(); ++i) { Output.push_back(*i); } Res.clear(); if(mode == '2') sort(Output.begin(), Output.end(), cmp); for (auto i(Output.begin()); i != Output.end(); ++i) { for (auto j((*i).begin()); j != (*i).end(); ++j) { cout << ConsoleSample[*j]; } cout << endl; } cout << "==================" << endl << endl; Output.clear(); } return 0; }

आगे क्या है

यहां पूर्ण कोड है , इसे विंडोज के तहत परीक्षण किया गया है, अन्य प्लेटफार्मों के लिए, आपको इनपुट और आउटपुट नमूनों को बदलना पड़ सकता है।
लेकिन शब्दकोश छोटा और बड़ा शब्दकोश है (यदि आप बड़े शब्दकोश का उपयोग करते हैं तो नाम के अंत में नंबर 2 को हटाना न भूलें)। बड़े शब्दकोश में न केवल प्रारंभिक रूप शामिल हैं, यह माइक्रोसॉफ्ट वर्डामेंट के लिए उपयुक्त है, लेकिन मैदान पर एक सेल में हमेशा एक अक्षर नहीं होता है। ज्यादातर मामलों में, वर्णित दो खेलों के लिए एक छोटा शब्दकोश स्टैंडिंग के शीर्ष पर होने के लिए पर्याप्त है।

मुझे उम्मीद है कि कोई भी इस तरह से नहीं खेलेगा, फिर भी अधिकांश खिलाड़ी निष्पक्ष खेलना जारी रखेंगे।

शब्द के खेल के लिए समाधान ढूँढना। बोरान आवेदन