स्लोवोमनिआ - शब्दों का अनुमान लगाएं। भाग 1, रूबी

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

सबसे पहले, यह समझने के लिए एक प्रोटोटाइप बनाना आवश्यक था कि उपलब्ध कंप्यूटिंग शक्ति (मैकबुक कोर 2 डुओ 2.2Ghz 2007 के 4 जीबी मेमोरी और लाइनोड 1024 सर्वर के साथ 2007 के अंत तक) क्षेत्र पर शब्द खोजने का कार्य कितना संभव है। चूंकि मैं हाल ही में रूबी ऑन रेल्स को सक्रिय रूप से विकसित कर रहा हूं, इसलिए रूबी को एक परीक्षण वातावरण के रूप में लेने का निर्णय लिया गया। जाहिर है, हमारे कार्य को बड़ी कंप्यूटिंग शक्ति की आवश्यकता होती है, और रूबी के मामले में, हमारे पास लगभग हर ऑपरेशन के लिए एक बड़ा ओवरहेड है, इसलिए एक मुकाबला स्थिति (उदाहरण के लिए, सी, लेकिन उस पर बाद में और अधिक) के लिए कुछ और उपयोग करने की आवश्यकता है। हालांकि, कोई निश्चित प्लस को अनदेखा नहीं कर सकता है - यह विकास की गति है।

तो चलिए चलते हैं। हमारा कार्यक्रम निम्नानुसार काम करेगा:

1. हम पत्रों के लिए सभी संभव लेआउट विकल्पों के माध्यम से सॉर्ट करते हैं
2. शब्दकोश के साथ परिणामों का मिलान करें
3. यदि शब्दकोश में विकल्प पाया गया - शब्द का अनुमान लगाया गया है, तो आप इसे खिलाड़ी को दिखा सकते हैं

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

मेरे सिर में विकसित क्रियाओं के निम्नलिखित एल्गोरिदम:

1. हम निर्देशांक (x, y) के साथ सेल में आते हैं (मैंने मूल के लिए नीचे बाएं कोने को लिया)। हम निर्देशांक (पथ) की एक विशेष सूची में वर्तमान सेल की स्थिति को याद करते हैं।
2. हम प्रत्येक दिशा (उत्तर, दक्षिण, पश्चिम, पूर्व, उत्तर-पूर्व, दक्षिण-पूर्व, दक्षिण-पश्चिम और उत्तर-पश्चिम) में एक सेल लेते हैं।
3. प्रत्येक पथ के लिए हम निर्देशांक की एक नई सूची बनाते हैं
4. निर्देशांक की सूचियों का उपयोग करके हम शब्द बनाते हैं
5. जांचें कि क्या शब्दकोश में शब्द हैं (यदि कोई है, तो खिलाड़ी को दिखाएं)
6. प्रत्येक नई स्थिति के लिए, चरण 2 पर जाएं जब तक कि हम एक निश्चित शब्द लंबाई (यानी समन्वय सूची की लंबाई) तक नहीं पहुंच जाते। लंबाई दो कारकों द्वारा निर्धारित की जाती है: खेल में अधिकतम संभव शब्द लंबाई, या हमारी कंप्यूटिंग शक्ति।
7. अगली सेल पर जाएं और शुरुआत से ही सभी शुरू करें।

इस प्रकार, हम पुनरावर्ती सभी संभावित संयोजनों के माध्यम से पूरे क्षेत्र में घूमते हैं। उसी समय, किसी को यह नहीं भूलना चाहिए कि प्रत्येक कोशिका प्रत्येक शब्द में केवल एक बार शामिल हो सकती है, इसलिए, पैराग्राफ (2) में, यह जांचना आवश्यक है कि क्या हमारी सूची में इस सेल के कोई निर्देशांक हैं या नहीं। इसके अलावा, यह सुनिश्चित करना न भूलें कि हम खेल के मैदान से आगे नहीं गए हैं।
और एक और जाँच: हम शब्द में शब्द की तलाश तभी करते हैं जब उसकी लंबाई (यानी पथ की लंबाई) दो से अधिक हो, क्योंकि खेल के नियमों के अनुसार शब्द में कम से कम 3 अक्षर हो सकते हैं।

यहाँ यह कैसा दिखता है:

खेल नेट

@@w = [ "", "", "", "" ] 

समन्वित वर्ग

 class Coord attr_accessor :x, :y def initialize(x,y) self.x = x self.y = y end end 

पड़ोसी बाईपास

 def lookup(coords, deep) print_word coords if deep >= 3 last = coords[-1] #up lookup_next coords, Coord.new(last.x + 1, last.y), deep #up-right lookup_next coords, Coord.new(last.x + 1, last.y + 1), deep #right lookup_next coords, Coord.new(last.x, last.y + 1), deep #right-down lookup_next coords, Coord.new(last.x + 1, last.y - 1), deep #down lookup_next coords, Coord.new(last.x, last.y - 1), deep #left-down lookup_next coords, Coord.new(last.x - 1, last.y - 1), deep #left lookup_next coords, Coord.new(last.x - 1, last.y), deep #left-up lookup_next coords, Coord.new(last.x - 1, last.y + 1), deep end def lookup_next(coords, new_coord, deep) return if deep > 6 return if new_coord.x < 0 or new_coord.y < 0 or new_coord.x > 3 or new_coord.y > 3 unless coords.find{|c|cx == new_coord.x and cy == new_coord.y} lookup coords.dup + [new_coord], deep + 1 end end 

एक शब्दकोष में शब्द खोजें और उसे प्रिंट करें

 def print_word coords word = "" coords.each do |c| word += @@w[3 - cy].split('')[cx] end return if @@words.include?(word) @@db.execute( "select * from words where (word)=('#{word}')" ) do |row| return if @@words.include?(word) @@words << word puts word end end 

सभी पाए गए शब्द वैश्विक चर @@ शब्दों में संगृहीत हैं जो स्क्रीन पर समान शब्दों को प्रदर्शित करने से बचने के लिए हैं।

हम खोज शुरू करते हैं

 0.upto(3) do |x| 0.upto(3) do |y| lookup [Coord.new(x, y)], 0 end end 

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

 Thread.new { 3.downto(0) do |x| 3.downto(0) do |y| lookup [Coord.new(x, y)], 0 end end } 

भले ही हम अपेक्षाकृत धीमी रूबी का उपयोग करते हैं, हमारा कार्यक्रम व्यवहार्य है और शब्दों को पूरी तरह से खोजता है। अगले लेख में, मैं ncurses, वितरित स्मृति, semaphores, और लाठी के साथ एक C कार्यान्वयन पर चर्चा करूंगा।

स्रोत कोड
शब्दकोश

न्याय ने जीत हासिल की है: अब जो सबसे अच्छा कंप्यूटर है वह जीत जाएगा!