jalur dalam grafik kata

Question

Grafik Word $W_n$ adalah graf yang himpunan puncaknya terdiri dari semua $n$-kata-kata bahasa Inggris dan set tepi yang terdiri dari semua simpul yang berbeda persis dengan satu huruf dalam satu posisi. Misalnya, dalam$W_4, \{hard, card\}$adalah sebuah keunggulan. Temukan jalan dari salah ke benar$W_5.$

Perlu ada cara untuk menggeser r di satu tempat yang salah ke kiri, meskipun saya tidak yakin bagaimana melakukan ini. Sebuah kata yang berdekatan dengan salah yang mungkin berguna termasuk memeras. Jalan dari memeras ke harga akan menjadi pemerasan, bawa, air garam, pengantin wanita, kebanggaan, harga, hadiah, prosa, rawan, dengung. Namun, ini sepertinya tidak terlalu berguna.

Answer 1

Saya tidak begitu yakin Anda berada di tag yang benar, atau bahkan harus di bawah matematika, tapi saya punya jawaban untuk Anda. Kata-kata dalam jawaban sangat tidak umum, tetapi googling menunjukkan kepada saya bahwa itu memang kata-kata. Nanti saya akan mencoba hal yang sama hanya dengan menggunakan kata-kata yang lebih umum, dan melihat apakah saya dapat menemukan jawaban yang lebih "nyata". Bagaimanapun, ini dia:

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

Sunting: Hanya menggunakan kata-kata dalam Kamus Scrabble , kami memiliki:

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

Saya menyelesaikan ini dengan program python berikut yang menggunakan algoritma 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")))

Jika Anda ingin menggunakan cara di atas untuk menyelesaikan masalah serupa, Anda perlu menginstal paket. Perintah untuk melakukannya bervariasi berdasarkan OS dan instalasi python Anda, tetapi secara umum terlihat seperti ini:

$ pip3 install tqdm $ pip3 install dijkstra

Saya mengumpulkan ini dari beberapa tempat, jadi mungkin tidak seanggun yang seharusnya - ini pasti tidak secepat yang seharusnya.

Kamus kata-kata yang saya gunakan dapat ditemukan di sini dan di sini .