O trocador de palavras é um jogo em que você está tentando transformar uma palavra em outra através de edições de um único caractere, sendo cada etapa sua própria palavra. Para esse desafio, as edições podem ser substituições, inserções ou exclusões. Por exemplo, WINNER → LOSER pode ser feito com esta rota (pode haver outras):

WINNER
DINNER
DINER
DINE
LINE
LONE
LOSE
LOSER

Em outro sentido, você deve conseguir alcançar uma palavra da outra, passando apenas por outras palavras a uma distância de Levenshtein de 1 a cada vez.

Codificação

Você receberá uma lista de palavras e duas palavras e deverá gerar uma rota válida de uma palavra para outra se existir uma rota ou um valor constante distinto ou um comportamento consistente se não houver uma rota.

• Você pode assumir que as palavras de entrada estão na lista de palavras
• A lista de palavras pode ser obtida através de qualquer formato plano conveniente.
  • Listas, conjuntos, tentativas, seqüências separadas por espaço e arquivos separados por linha são todos válidos (por exemplo), mas um gráfico pré-calculado da adjacência de Levenshtein não é.
• A rota de saída deve incluir as duas palavras de entrada, mas que começa e termina não importa.
• Se nenhuma rota for encontrada, você poderá gerar uma constante específica, um valor falso, uma lista vazia, lançar uma exceção, sair com um código diferente de zero ou qualquer outro comportamento que ocorra em tempo finito.
• A rota não precisa ser ótima e não há exigência de qual rota deve ser seguida.
• A complexidade computacional não importa, no entanto, seu programa deve ter a garantia de término em um período finito de tempo. (mesmo que fosse além da morte por calor do universo)
• Você pode assumir que todas as palavras são compostas inteiramente de letras no mesmo caso

Casos de teste de exemplo

• CAT → CÃO; [CAT, CÃO, COG, COT, SAPO, GRÃO, BOG]
  • GATO, COT, COG, CÃO
• BANHO → CHUVEIRO; [BANHO, CHUVEIRO, CHAPÉU, CHAPÉU, BAT, SAT, SERRA, SOW, MOSTRA, COMO]
  • Nenhuma rota encontrada
• BREAK → CORRIGIR; .
  • QUEBRA, PÃO, CARGA, RUIM, FAD, FAX, CORRIGIR
• CONSTRUIR → DESTRUIR; [CONSTRUIR, DESTRUIR, CONSTRUIR, CULPAR, CULPA, GILD, GILL, BILL, DILL, PILL, Preencher, DESTRUIR, ESTRUTURA, CONSTRUIR]
  • Nenhuma rota encontrada
• CARTÃO → PLACA; [CARTÃO, PLACA, BARRA]
  • CARTÃO, BARBA, PLACA
• DEMÔNIO → ANJO; [Demônio, anjo]
  • Nenhuma rota encontrada
• ÚLTIMO → PASSADO; [ÚLTIMO, PASSADO, EXPLOSÃO, MOLDE, PRETO, FANTASMA, PÓS, BOAST]
  • ÚLTIMO, PASSADO
• INSERIR → EXCLUIR; Esta lista de palavras
  • INSERIR, INVERSAR, INVENTAR, INVENTAR, INVENTAR, DESVENDAR, DESVENDER, DESENVOLVER, DESBATAR, INKING, IRKING, SUBIR, ESCURECER, ESCREVER, ARLING, PRESTAR, SIRING, SERING, SERINE, NERINE, NERITE, CERITE, CERETE, DERTE EXCLUIR

05AB1E , 23 21 20 bytes

Imprime uma lista de rotas válidas.
Economizou 2 bytes graças a Kevin Cruijssen .

怜€`ʒü.LP}ʒ¬²Qsθ³Q*

Experimente online!

JavaScript (V8) ,  177  176 bytes

Toma entrada como (target)(source, list). Imprime todas as rotas possíveis. Ou imprime nada se não houver solução.

t=>F=(s,l,p=[],d)=>s==t?print(p):l.map((S,i)=>(g=(m,n)=>m*n?1+Math.min(g(m-1,n),g(m,--n),g(--m,n)-(S[m]==s[n])):m+n)(S.length,s.length)^d||F(S,L=[...l],[...p,L.splice(i,1)],1))

Experimente online!

Comentado

t =>                            // t = target string
F = (                           // F is a recursive function taking:
  s,                            //   s = source string
  l,                            //   l[] = list of words
  p = [],                       //   p[] = path
  d                             //   d = expected Levenshtein distance between s and the
) =>                            //       next word (initially undefined, so coerced to 0)
  s == t ?                      // if s is equal to t:
    print(p)                    //   stop recursion and print the path
  :                             // else:
    l.map((S, i) =>             //   for each word S at index i in l[]:
      ( g =                     //     g = recursive function computing the Levenshtein
        (m, n) =>               //         distance between S and s
        m * n ?                 //       if both m and n are not equal to 0:
          1 + Math.min(         //         add 1 to the result + the minimum of:
            g(m - 1, n),        //           g(m - 1, n)
            g(m, --n),          //           g(m, n - 1)
            g(--m, n) -         //           g(m - 1, n - 1), minus 1 if ...
            (S[m] == s[n])      //           ... S[m - 1] is equal to s[n - 1]
          )                     //         end of Math.min()
        :                       //       else:
          m + n                 //         return either m or n
      )(S.length, s.length)     //     initial call to g with m = S.length, n = s.length
      ^ d ||                    //     unless the distance is not equal to d,
      F(                        //     do a recursive call to F with:
        S,                      //       the new source string S
        L = [...l],             //       a copy L[] of l[]
        [...p, L.splice(i, 1)], //       the updated path (removes S from L[])
        1                       //       an expected distance of 1
      )                         //     end of recursive call
    )                           //   end of map()

Wolfram Language (Mathematica) , 59 bytes

Select[Rule@@@#~Tuples~2,EditDistance@@#<2&]~FindPath~##2&;

Experimente online!

Python 2 , 155 bytes

f=lambda a,b,W,r=[]:a==b and r+[a]or reduce(lambda q,w:q or any({a,a[:i]+a[i+1:]}&{w,w[:i]+w[i+1:]}for i in range(len(a+w)))and f(w,b,W-{a},r+[a]),W-{a},0)

Experimente online!

Leva duas palavras e um conjunto de palavras como entrada; retorna uma rota (não ótima) se existir como uma lista de cadeias, caso contrário, retorna False.

Este fragmento:

any({a,a[:i]+a[i+1:]}&{w,w[:i]+w[i+1:]}for i in range(len(a+w)))

é Truese e somente se a==wou atem Levenshtein distância de 1partir w.

Wolfram Language (Mathematica) , 124 bytes

Join[#,Select[Flatten[Permutations/@Subsets@#3,1],s=#;t=#2;Union[EditDistance@@@Partition[Join[s,#,t],2,1]]=={1}&][[1]],#2]&

Experimente online!

Python 2 , 163 bytes

Se uma rota for encontrada, ela será enviada para o stderr e o programa sairá com o código de saída 1.
Se não houver uma rota, não haverá saída e o programa será finalizado com o código de saída 0.

s,e,d=input();r=[[s]]
for x in r:t=x[-1];t==e>exit(x);r+=[x+[w]for w in d-set(x)for a,b in(t,w),(w,t)for i in range(len(b)*2)if a==b[:i/2]+a[i/2:][:i%2]+b[i/2+1:]]

Experimente online!

Python 3 , 217 214 212 201 bytes

-11 bytes thanx a uma dica do xnor

d=lambda a,b:min(d(a[1:],b[1:])+(a[0]!=b[0]),d(a[1:],b)+1,d(a,b[1:])+1)if b>""<a else len(a+b)
def g(a,b,l,p=[]):
	if a==b:yield[a]+p
	for c in(a!=b)*l:
		if(c in p)+d(a,c)==1:yield from g(c,b,l,[a]+p)

Experimente online!

Gelatina , 38 bytes

⁵ḟ,€0ị$ṭ¹-Ƥ$€e€/ẸƊƇḢ€
Wṭ@ⱮÇßƊe@⁴oṆƲ?€Ẏ

Experimente online!

Um programa completo que aceita três argumentos. A primeira é a palavra inicial e é fornecida como [["START"]]. O segundo argumento é a palavra final, fornecida como "END". O terceiro argumento é a lista de palavras, fornecida como palavras entre aspas e separadas por vírgula.

O programa retorna uma lista de listas, com cada lista representando um caminho válido do início ao fim. Se não houver uma rota válida, a resposta será uma lista vazia.

No link TIO, há um texto de rodapé para exibir o resultado com cada palavra separada por espaços e cada lista de palavras separadas por novas linhas. Se uma impressão subjacente à representação da lista for preferida, isso pode ser feito como ÇŒṘ.

Ao contrário do 05ABIE, não há nenhum recurso interno para a distância de Levenshtein, então este programa compara outfixes com um único caractere ausente, um pouco semelhante à solução do @ ChasBrown , embora com um toque de geléia.

Explicação

Link auxiliar: link monádico que pega uma lista de palavras e retorna uma lista de possíveis listas estendidas ou uma lista vazia se nenhuma outra extensão for possível

⁵ḟ                      | Filter the word list to remove words already used
  ,€0ị$                 | Pair each word with the last word in the current path
                  ƊƇ    | Filter these pairs such that
              e€/Ẹ      |   there exists any
       ṭ¹-Ƥ$€           |   match between the original words or any outfix with a single character removed
                    Ḣ€  | Take the first word of each of these pairs (i.e. the possible extensions of the route)

Link principal

              €         | For each of the current paths
            Ʋ?          | If:
       e@⁴              |   The path contains the end word
          oṆ            |   Or the path is empty (i.e. could not be extended)
W                       | Return the path wrapped in a list (which will be stripped by the final Ẏ)
 ṭ@ⱮÇ                   | Otherwise, look for possible extensions using the helper link, and add onto the end of the path
     ßƊ                 | And then feed all of these paths back through this link
               Ẏ        | Strip back one layer of lists (needed because each recursion nests the path one list deeper)

Swift 4.2 / Xcode 10.2.1 , 387 bytes

func d(l:String,m:String)->Bool{return (0..<l.count).contains{var c=l;c.remove(at:c.index(c.startIndex,offsetBy:$0));return c==m}};func f(r:[String])->[String]{if b==r.last!{return r};return w.lazy.map{!r.contains($0)&&(d(l:r.last!,m:$0)||d(l:$0,m:r.last!)||(r.last!.count==$0.count&&zip(r.last!,$0).filter{$0 != $1}.count==1)) ? f(r:r+[$0]):[]}.first{!$0.isEmpty} ?? []};return f(r:[a])

Experimente online!