शब्द ग्राफ में पथ

Question

शब्द का ग्राफ $W_n$ वह ग्राफ है जिसके शीर्ष सेट में सभी शामिल हैं $n$अंग्रेजी अंग्रेजी शब्दों और जिनके किनारे सेट में सभी कोने होते हैं जो एक स्थिति में बिल्कुल एक अक्षर से भिन्न होते हैं। उदाहरण के लिए, में$W_4, \{hard, card\}$एक छोर है। गलत से सही में एक रास्ता खोजें$W_5.$

गलत तरीके से आर को बाईं ओर शिफ्ट करने का एक तरीका होना चाहिए, हालांकि मुझे यकीन नहीं है कि यह कैसे करना है। गलत से सटे एक शब्द जो उपयोगी हो सकता है, उसमें लेखन शामिल है। राइटिंग से प्राइस तक एक रास्ता होगा राइटिंग, ब्रिंग, ब्राइन, ब्राइड, प्राइड, प्राइस, प्राइज, प्रोज, प्रोन, ड्रोन। हालाँकि, यह बहुत उपयोगी नहीं लगता है।

Answer 1

मुझे यकीन नहीं है कि आप सही टैग में हैं, या यहां तक ​​कि जरूरी है कि यह गणित के तहत होना चाहिए, लेकिन मुझे आपके लिए एक उत्तर मिला है। उत्तर में शब्द बहुत ही असामान्य हैं, लेकिन गुगली ने मुझे दिखाया कि वे वास्तव में शब्द हैं। बाद में मैं केवल और अधिक सामान्य शब्दों का उपयोग करके ऐसा करने का प्रयास करूंगा, और देखूंगा कि क्या मुझे अधिक "वास्तविक" उत्तर मिल सकता है। किसी भी मामले में, आप यहाँ जाते हैं:

wrong
wrung
drung
drunt
daunt
dasnt
dasht
hasht
hacht
hicht
richt
right

संपादित करें: स्क्रैबल शब्दकोश में केवल शब्दों का उपयोग करना , हमारे पास है:

wrong
prong
prone
phone
phons
pions
lions
linns
lines
sines
sinhs
sighs
sight
right

मैंने निम्नलिखित अजगर कार्यक्रम के साथ इसे पूरा किया जो दिज्क्स्ट्रा के एल्गोरिथ्म का उपयोग करता है:

from dijkstra import Graph, DijkstraSPF
from tqdm import tqdm

def load_words():
    with open('words_alpha.txt') as word_file:
        valid_words = set(word_file.read().split())

    return valid_words

def d(word1,word2):
    t = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            t += 1
    return t

def near(word):
    s = set()
    for w in w5:
        if d(w,word) == 1:
            s.add(w)
    return s

w = load_words()
w5 = set([word if len(word) == 5 else '' for word in w])
w5.remove('')
w5 = list(w5)

w5g = Graph()

for i in tqdm(range(len(w5)), "Building Graph"):
    for n in near(w5[i]):
        w5g.add_edge(w5[i],n,1)

d = DijkstraSPF(w5g, "wrong")
print("\n".join(d.get_path("right")))

यदि आप समान समस्याओं को हल करने के लिए उपरोक्त का उपयोग करना चाहते हैं, तो आपको पैकेजों को स्थापित करना होगा। आपके OS और पायथन इंस्टॉलेशन के आधार पर ऐसा करने के आदेश अलग-अलग हैं, लेकिन सामान्य तौर पर वे इस तरह दिखते हैं:

$ pip3 install tqdm $ pip3 install dijkstra

मैंने इसे कुछ स्थानों से एक साथ जोड़ा है, इसलिए यह संभवतः उतना सुंदर नहीं है जितना कि यह हो सकता है - यह निश्चित रूप से उतना तेज़ नहीं है जितना कि हो सकता है।

मेरे द्वारा प्रयुक्त शब्दों के शब्दकोश यहाँ और यहाँ मिल सकते हैं ।