caminho no gráfico de palavras

Question

O gráfico do Word $W_n$ é o gráfico cujo conjunto de vértices consiste em todos $n$- letras em inglês, cujo conjunto de arestas consiste em todos os vértices que diferem exatamente por uma letra em uma posição. Por exemplo, em$W_4, \{hard, card\}$é uma vantagem. Encontre um caminho do errado para o certo em$W_5.$

Deve haver uma maneira de deslocar o r no lugar errado para a esquerda, embora eu não tenha certeza de como fazer isso. Uma palavra adjacente a errado que pode ser útil inclui torcer. Um caminho de torcer para preço seria torcer, trazer, salmoura, noiva, orgulho, preço, prêmio, prosa, inclinado, zangão. No entanto, isso não parece muito útil.

Answer 1

Não tenho certeza se você está nas marcas certas, ou mesmo necessariamente se isso deve ser em matemática, mas tenho uma resposta para você. As palavras na resposta são bastante incomuns, mas pesquisar no Google me mostrou que são de fato palavras. Mais tarde, tentarei fazer o mesmo usando apenas palavras mais comuns e ver se consigo encontrar uma resposta mais "real". Em qualquer caso, aqui está:

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

Editar: usando apenas palavras no Dicionário Scrabble , temos:

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

Eu fiz isso com o seguinte programa python que usa o algoritmo 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")))

Se quiser usar o acima para resolver problemas semelhantes, você precisará instalar os pacotes. Os comandos para fazer isso variam com base no seu sistema operacional e na instalação do Python, mas em geral eles se parecem com isto:

$ pip3 install tqdm $ pip3 install dijkstra

Eu juntei isso em alguns lugares, então provavelmente não é tão elegante quanto poderia - definitivamente não é tão rápido quanto poderia ser.

Os dicionários de palavras que usei podem ser encontrados aqui e aqui .