เส้นทางในกราฟคำ

Question

กราฟ Word $W_n$ คือกราฟที่เซตจุดยอดประกอบด้วยทั้งหมด $n$- จดหมายคำภาษาอังกฤษและชุดขอบประกอบด้วยจุดยอดทั้งหมดที่แตกต่างกันโดยตัวอักษรเดียวในตำแหน่งเดียว ตัวอย่างเช่นใน$W_4, \{hard, card\}$เป็นขอบ ค้นหาเส้นทางจากผิดไปถูก$W_5.$

ต้องมีวิธีเลื่อน r ผิดที่หนึ่งไปทางซ้ายแม้ว่าฉันจะไม่แน่ใจว่าจะทำอย่างไร คำที่อยู่ติดกับคำผิดที่อาจมีประโยชน์ ได้แก่ การเขียน เส้นทางจากการบีบราคาจะเป็นการบีบนำน้ำเกลือเจ้าสาวความภาคภูมิใจราคารางวัลร้อยแก้วแนวโน้มเสียงพึมพำ อย่างไรก็ตามสิ่งนี้ดูเหมือนจะไม่มีประโยชน์มากนัก

Answer 1

ฉันไม่แน่ใจจริงๆว่าคุณอยู่ในแท็กที่ถูกต้องหรือแม้กระทั่งจำเป็นว่าสิ่งนี้ควรอยู่ภายใต้หลักคณิตศาสตร์ แต่ฉันมีคำตอบให้คุณ คำในคำตอบค่อนข้างผิดปกติ แต่ googling แสดงให้ฉันเห็นว่าเป็นคำจริง หลังจากนั้นฉันจะลองแบบเดียวกันโดยใช้เฉพาะคำทั่วไปและดูว่าฉันจะพบคำตอบที่ "จริง" มากกว่านี้หรือไม่ ไม่ว่าในกรณีใด ๆ ได้ที่นี่:

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

แก้ไข:การใช้คำในพจนานุกรม Scrabbleเรามี:

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

ฉันทำสิ่งนี้สำเร็จด้วยโปรแกรม python ต่อไปนี้ที่ใช้อัลกอริทึมของ Dijkstra:

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")))

หากคุณต้องการใช้ข้างต้นเพื่อแก้ไขปัญหาที่คล้ายกันคุณจะต้องติดตั้งแพ็คเกจ คำสั่งในการทำจะแตกต่างกันไปตามการติดตั้งระบบปฏิบัติการและ python ของคุณ แต่โดยทั่วไปแล้วจะมีลักษณะดังนี้:

$ pip3 install tqdm $ pip3 install dijkstra

ฉันปะติดปะต่อสิ่งนี้เข้าด้วยกันจากสถานที่สองแห่งดังนั้นมันอาจจะไม่สง่างามเท่าที่ควร - มันไม่เร็วเท่าที่ควร

พจนานุกรมของคำที่ผมใช้สามารถพบได้ที่นี่และที่นี่