percorso nel grafico delle parole

Question

Il grafico di Word $W_n$ è il grafo il cui insieme dei vertici è costituito da tutto $n$-lettera parole inglesi e il cui set di bordi è costituito da tutti i vertici che differiscono esattamente di una lettera in una posizione. Ad esempio, in$W_4, \{hard, card\}$è un vantaggio. Trova un percorso da sbagliato a giusto$W_5.$

Deve esserci un modo per spostare la r nel punto sbagliato a sinistra, anche se non sono sicuro di come farlo. Una parola adiacente a wrong che potrebbe essere utile include strizzare. Un percorso dallo strizzare al prezzo sarebbe strizzare, portare, salamoia, sposa, orgoglio, prezzo, premio, prosa, prono, drone. Tuttavia, questo non sembra molto utile.

Answer 1

Non sono davvero sicuro che tu abbia i tag giusti, o anche necessariamente che questo dovrebbe essere sotto la matematica, ma ho una risposta per te. Le parole nella risposta sono piuttosto insolite, ma cercare su Google mi ha mostrato che sono davvero parole. Successivamente proverò lo stesso utilizzando solo parole più comuni e vedrò se riesco a trovare una risposta più "reale". In ogni caso, eccoti qui:

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

Modifica: utilizzando solo parole nel dizionario di Scrabble , abbiamo:

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

L'ho ottenuto con il seguente programma python che utilizza l'algoritmo di 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")))

Se si desidera utilizzare quanto sopra per risolvere problemi simili, sarà necessario installare i pacchetti. I comandi per farlo variano in base al sistema operativo e all'installazione di Python, ma in generale hanno questo aspetto:

$ pip3 install tqdm $ pip3 install dijkstra

L'ho messo insieme da un paio di punti, quindi probabilmente non è così grazioso come potrebbe essere - sicuramente non è veloce come potrebbe essere.

I dizionari di parole che ho usato possono essere trovati qui e qui .