NYT Spelling Bee में स्कोरिंग तेज करने का तरीका: बिटमास्क समेकन और प्री-कम्प्यूट

NYT Spelling Bee में सात अक्षरों के सेट की स्कोरिंग को बिटमास्क समेकन और प्री-कम्प्यूटेड स्कोर से तेज करें; Python के साथ 26C7 संयोजनों का कुशल अनुक्रमण सीखें.

NYT Spelling Bee का स्कोर अधिकतम करना सुनने में सीधा लगता है: सात अक्षर चुनिए, केवल उन्हीं अक्षरों से बनने वाले सभी मान्य शब्द गिनिए, उन्हें खेल के स्कोरिंग नियमों के अनुसार वेट दीजिए, और सबसे अच्छा सेट ढूँढ लीजिए। असली फँसाव इस बात में है कि खोज-स्थान में आप कैसे चलते हैं और उसे कैसे स्कोर करते हैं। मास्क पर भोली खोज के साथ पूरी शब्द-सूची को बार-बार फिर से स्कोर करना, इष्टतम उत्तर दिखने से बहुत पहले ही प्रक्रिया को जाम कर देता है।

बेसलाइन तरीका और जहाँ बाधा आती है

नीचे दिया बेसलाइन ऐसे शब्दों की भाषा बनाता है जिनमें अधिकतम सात अलग-अलग अक्षर हों, शब्दों को 26-बिट मास्क के रूप में दर्शाता है, और अक्षर-समूहों को समान-लागत खोज में मास्क के रूप में एक्सप्लोर करता है। स्कोरिंग फ़ंक्शन हर मास्क के लिए सभी शब्द स्कैन करता है। तर्क सही है, पर प्रदर्शन टूट जाता है क्योंकि स्कोरिंग एक जैसा भारी काम बार-बार दोहराती है।

from string import ascii_lowercase
from heapq import heappush, heappop
ALPH = ascii_lowercase  # Σ
with open("words.txt") as fh:
    raw_words = fh.read().splitlines()
# उन शब्दों को रखें जो 7 से अधिक भिन्न अक्षरों का उपयोग नहीं करते
pool = list(filter(lambda w: len(set(w)) <= 7, raw_words))
# हर शब्द को 26-बिट मास्क में बदलें
word_masks = [0] * len(pool)
for idx in range(len(pool)):
    for ch in pool[idx]:
        word_masks[idx] |= 1 << (ord(ch) - ord('a'))
# खेल की स्कोरिंग: 4-अक्षरी शब्द = 1 अंक, लंबे शब्द = लंबाई के बराबर अंक
def score_of(w):
    return 1 if len(w) == 4 else len(w)
# दिए गए अक्षर-सेट मास्क के लिए सभी शब्द स्कैन कर स्कोर निकालें
def tally_for(msk):
    total = 0
    for i in range(len(pool)):
        if (msk | word_masks[i]) == msk:
            total += score_of(pool[i])
    return -total  # min-heap उपयोग के लिए ऋणात्मक
# मास्क पर डाइज्कस्ट्रा-जैसी खोज: हर चरण में एक अक्षर हटाएँ
root_mask = (1 << len(ALPH)) - 1
root_entry = (tally_for(root_mask), root_mask)
frontier = [root_entry]
seen = set()
while True:
    val, msk = heappop(frontier)
    print(val, "".join(ALPH[i] if msk & (1 << i) else ' ' for i in range(26)))
    if msk.bit_count() == 7:
        break
    for i in range(len(ALPH)):
        if msk & (1 << i):
            nxt = msk & ~(1 << i)
            if nxt in seen:
                continue
            heappush(frontier, (tally_for(nxt), nxt))
            seen.add(nxt)

मुख्य बाधा प्रति-मास्क स्कोरिंग है। स्कोरिंग फ़ंक्शन का हर कॉल पूरी शब्द-सूची पर चलता है और हर शब्द का स्कोर फिर से गणता है, जबकि वे स्कोर बदलते ही नहीं। खुद खोज भी बड़े पठारों में फँस जाती है, जहाँ बहुत से मास्कों का स्कोर समान होता है, और इस वजह से अन्वेषित अवस्थाओं की संख्या बढ़ती जाती है।

मुख्य समझ: अद्वितीय बिटमास्क के आधार पर समेकन

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

जैसे abalones और seasonable—दोनों {a, b, e, l, n, o, s} के लिए एक ही बिटमास्क पर मैप होते हैं। हर पास पर इन शब्दों को अलग-अलग स्कोर करने के बजाय, उसी बिटमास्क की चाबी पर एक प्रविष्टि रखें और उनके सम्मिलित अंक जोड़ दें। आम शब्द-सूची (wamerican) में यह 40940 शब्दों को घटाकर 20818 अद्वितीय बिटमास्क तक ले आता है। यही आधी कटौती स्कोरिंग का काम नाटकीय रूप से कम कर देती है, और 26 में से 7 अक्षर चुनने वाले सभी सेटों का साधारण पूर्ण अनुक्रमण भी संभव बनाती है।

इस समेकन के साथ, एक मशीन पर पूरे 26-अक्षर मास्क पर Python द्वारा स्कोरिंग फ़ंक्शन को लगभग 1.4 सेकंड में 1000 बार चलाया जा सकता है—जो सर्वश्रेष्ठ सात-अक्षरी सेट को बलपूर्वक खोजने के लिए पर्याप्त तेज़ है।

परिवर्धित समाधान: पहले से गणना करें और संपीड़ित करें

नीचे का कोड बिटमास्क से उस मास्क वाले सभी शब्दों के कुल स्कोर तक एक मैपिंग बनाता है। स्कोरिंग फ़ंक्शन फिर उसी मैप पर इटरेट करता है। प्रोग्राम का तर्क जस का तस है; बस डेटा की बनावट और स्कोरिंग लूप को अनुकूलित किया गया है।

from string import ascii_lowercase
import timeit
ALPH = ascii_lowercase
with open("words.txt") as fh:
    raw = fh.read().splitlines()
# केवल वे शब्द रखें जो अधिकतम 7 अद्वितीय अक्षरों का उपयोग करते हैं
filtered = list(filter(lambda w: len(set(w)) <= 7, raw))
# हर शब्द को 26-बिट मास्क में बदलें
bm_list = [0] * len(filtered)
for i in range(len(filtered)):
    for ch in filtered[i]:
        bm_list[i] |= 1 << (ord(ch) - ord('a'))
# खेल की स्कोरिंग: 4-अक्षरी शब्द = 1 अंक, अन्यथा शब्द-लंबाई के बराबर अंक
def points(w):
    return 1 if len(w) == 4 else len(w)
# समेकन: बिटमास्क -> उस बिटमास्क वाले सभी शब्दों के अंकों का योग
bm_to_score = {}
for i in range(len(filtered)):
    bm_to_score.setdefault(bm_list[i], 0)
    bm_to_score[bm_list[i]] += points(filtered[i])
print(f"bm_count={len(bm_to_score)}, words_filtered={len(filtered)}, words_total={len(raw)}")
# उपयुक्त बिटमास्क पर योग करके प्रत्याशी अक्षर-सेट मास्क का स्कोर निकालें
def total_for(msk):
    s = 0
    for bm, acc in bm_to_score.items():
        if (msk | bm) == msk:
            s += acc
    return -s
# उदाहरण समय-आकलन: पूरे वर्णमाला मास्क का कई बार स्कोर
print(timeit.timeit("total_for(0b11111111111111111111111111)", number=1000, globals=globals()))

सिर्फ यही बदलाव 657800 सभी सात-अक्षरी मास्कों पर इटरेट कर के सर्वाधिक स्कोर वाले को चुनना व्यावहारिक बना देता है। यही संरचना आगे केंद्र-अक्षर की शर्त और पैनग्राम बोनस जैसी बारीकियों के लिए भी उपयुक्त है; ये समायोजन प्री-एग्रीगेशन के ऊपर परत की तरह जोड़े जा सकते हैं, बिना समग्र तरीके को बदले।

यह क्यों मायने रखता है

हर मास्क पर हर शब्द की स्कोरिंग शब्दों की संख्या के साथ रैखिक रूप से बढ़ती है—खोज के दौरान बार-बार करने पर यह विनाशकारी है। शब्दों को अद्वितीय बिटमास्क में समेटने से डेटा छोटा होता है, अनावश्यक स्कोरिंग हटती है, और समस्या एक क्रम-परिमाण छोटे सेट पर तेज़ बिटवाइज़ जाँचों में बदल जाती है। व्यवहार में, इससे सभी सात-अक्षरी संयोजनों का सीधे अनुक्रमण संभव हो जाता है, रास्ता-निर्भर खोज रणनीतियों की जरूरत नहीं रहती जो विशाल स्कोर पठारों में भटकती हैं।

C++ प्रयोगों से एक व्यावहारिक टिप्पणी: बिटमास्क-से-स्कोर तालिका के लिए 2^26 आकार की समतल int ऐरे, unordered_set से कहीं तेज़ निकल सकती है, भले ही ऐरे बड़ा हो। संभव है कि हैश तालिका की कैश-प्रदर्शन क्षमता कमजोर हो जबकि ऐरे की बहुत अच्छी, या फिर हैशिंग में ही समय लगता हो। इसका प्रोफाइलिंग नहीं किया गया, लेकिन यह इस विचार से मेल खाता है कि पूर्वानुमेय, सतत मेमरी, नाममात्र बड़े आकार के बावजूद जीत सकती है।

मुख्य निष्कर्ष

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

निष्कर्ष

यदि कोई एल्गोरिद्म अपना अधिकांश समय वही तथ्य दोबारा गिनने में लगा देता है, तो पीछे हटकर डेटा की बनावट बदलें। Spelling Bee स्कोरिंग के लिए सही डेटा-रूप है “bitmask -> total score”—इसे एक बार बनाएँ और हर जगह पुनः उपयोग करें। इससे मास्कों पर कठिन खोज, संपीडित संरचनाओं पर एक सरल, तेज़ पास में बदल जाती है—ठीक वही जिसकी आपको सर्वश्रेष्ठ सात-अक्षरी सेट खोजने के लिए जरूरत है।