chemin dans le graphe de mots

Question

Le graphique Word $W_n$ est le graphe dont l'ensemble de sommets se compose de tous $n$-lettre mots anglais et dont le jeu d'arêtes se compose de tous les sommets qui diffèrent d'exactement une lettre dans une position. Par exemple, dans$W_4, \{hard, card\}$est un avantage. Trouvez un chemin du mal au bien dans$W_5.$

Il doit y avoir un moyen de déplacer le r au mauvais endroit vers la gauche, même si je ne suis pas sûr de savoir comment faire cela. Un mot adjacent à faux qui pourrait être utile inclut tordre. Un chemin de l'essorage au prix serait essorer, apporter, saumure, mariée, fierté, prix, prix, prose, couché, drone. Cependant, cela ne semble pas très utile.

Answer 1

Je ne suis pas vraiment sûr que vous soyez dans les bonnes balises, ni même nécessairement que cela devrait être sous maths, mais j'ai une réponse pour vous. Les mots dans la réponse sont assez rares, mais googler m'a montré que ce sont effectivement des mots. Plus tard, j'essaierai la même chose en utilisant uniquement des mots plus courants, et je verrai si je peux trouver une réponse plus «réelle». Dans tous les cas, c'est parti:

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

Edit: En utilisant uniquement des mots dans le dictionnaire Scrabble , nous avons:

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

J'ai accompli cela avec le programme python suivant qui utilise l'algorithme de 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")))

Si vous souhaitez utiliser ce qui précède pour résoudre des problèmes similaires, vous devrez installer les packages. Les commandes pour le faire varient en fonction de votre système d'exploitation et de l'installation de python, mais en général, elles ressemblent à ceci:

$ pip3 install tqdm $ pip3 install dijkstra

Je l'ai reconstitué à partir de quelques endroits, donc ce n'est probablement pas aussi gracieux que cela pourrait être - ce n'est certainement pas aussi rapide que cela pourrait être.

Les dictionnaires de mots que j'ai utilisés se trouvent ici et ici .