Le changeur de mots est un jeu où vous essayez de transformer un mot en un autre via des modifications à un seul caractère, chaque étape étant son propre mot. Pour ce défi, les modifications peuvent être des remplacements, des insertions ou des suppressions. Par exemple, WINNER → LOSER peut être fait avec cet itinéraire (il peut y en avoir d'autres):

WINNER
DINNER
DINER
DINE
LINE
LONE
LOSE
LOSER

Formulé autrement, vous devez être capable d'atteindre un mot de l'autre en ne passant que par d'autres mots à une distance Levenshtein de 1 à chaque fois.

Codage

Vous recevrez une liste de mots et deux mots et vous devez sortir un itinéraire valide d'un mot à l'autre s'il existe un itinéraire ou une valeur constante distincte ou un comportement cohérent si aucun itinéraire n'existe.

• Vous pouvez supposer que les mots saisis sont tous les deux dans la liste de mots
• La liste de mots peut être prise via n'importe quel format plat pratique.
  • Les listes, les ensembles, les essais, les chaînes séparées par des espaces et les fichiers séparés par des lignes sont tous valides (par exemple), mais un graphique précalculé de la contiguïté de Levenshtein ne l'est pas.
• La route de sortie doit inclure les deux mots d'entrée, mais ce qui commence et se termine n'a pas d'importance.
• Si aucune route n'est trouvée, vous pouvez sortir une constante spécifique, une valeur falsifiée, une liste vide, lever une exception, quitter avec un code différent de zéro ou tout autre comportement qui se produit en temps fini.
• L'itinéraire n'a pas besoin d'être optimal et il n'y a aucune exigence de l'itinéraire à suivre
• La complexité informatique n'a pas d'importance, mais votre programme doit être garanti de manière à se terminer dans un laps de temps limité. (même si cela irait au-delà de la mort thermique de l'univers)
• Vous pouvez supposer que tous les mots sont entièrement composés de lettres dans le même cas

Exemples de cas de test

• CHAT → CHIEN; [CHAT, CHIEN, COG, COT, GRENOUILLE, GROG, BOG]
  • CHAT, COT, COG, CHIEN
• BAIN → DOUCHE; [BAIN, DOUCHE, CHAPEAU, CHAPEAU, BAT, SAT, SCIE, TRUIE, AFFICHAGE, COMMENT]
  • Aucun itinéraire trouvé
• BREAK → FIX; [BREAK, FIX, BEAK, BREAD, READ, BEAD, RED, BED, BAD, BID, FAD, FAX]
  • PAUSE, PAIN, PERLE, MAUVAIS, FAD, FAX, FIX
• CONSTRUIRE → DÉTRUIRE; [CONSTRUIRE, DÉTRUIRE, CONSTRUIRE, CONDUIRE, GUILDE, DORÉ, GILL, BILL, DILL, REMPLIR, DÉTRUIRE, STRUCTURE, CONSTRUIRE]
  • Aucun itinéraire trouvé
• CARTE → CONSEIL; [CARTE, CONSEIL, BARD]
  • CARD, BARD, BOARD
• DEMON → ANGEL; [DEMON, ANGEL]
  • Aucun itinéraire trouvé
• DERNIER → PASSÉ; [DERNIER, PASSÉ, BLAST, CAST, NOIR, FANTÔME, POST, BOAST]
  • DERNIER, PASSÉ
• INSÉRER → SUPPRIMER; Cette liste de mots
  • INSÉRER, INVERSER, INVENTER, INBENT, UNBENT, UNBEND, UNBIND, UNKIND, UNKING, INKING, IRKING, DIRKING, DARKING, DARLING, ARLING, AILING, SIRING, SERING, SERINE, NERINE, NERITE, CERITE, CERATE, DERATE, DELATE, SUPPRIMER

05AB1E , 23 21 20 octets

Imprime une liste des itinéraires valides.
Enregistré 2 octets grâce à Kevin Cruijssen .

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

Essayez-le en ligne!

JavaScript (V8) ,  177  176 octets

Prend l'entrée comme (target)(source, list). Imprime tous les itinéraires possibles. Ou n'imprime rien s'il n'y a pas de solution.

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))

Essayez-le en ligne!

Commenté

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 octets

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

Essayez-le en ligne!

Python 2 , 155 octets

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)

Essayez-le en ligne!

Prend deux mots et un ensemble de mots comme entrée; renvoie une route (non optimale) s'il en existe une sous forme de liste de chaînes, sinon renvoie False.

Ce fragment:

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

est Truesi et seulement si a==wou aa la distance de Levenshtein 1de w.

Wolfram Language (Mathematica) , 124 octets

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

Essayez-le en ligne!

Python 2 , 163 octets

Si une route est trouvée, elle est sortie vers stderr
et le programme se termine avec le code de sortie 1. S'il n'y a pas de route, il n'y a pas de sortie et le programme se termine avec le code de sortie 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:]]

Essayez-le en ligne!

Python 3 , 217 214 212 201 octets

-11 octets thanx à un indice de 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)

Essayez-le en ligne!

Gelée , 38 octets

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

Essayez-le en ligne!

Un programme complet acceptant trois arguments. Le premier est le mot de départ et est fourni en tant que [["START"]]. Le deuxième argument est le dernier mot, fourni comme"END" . Le troisième argument est la liste de mots, fournie sous forme de mots séparés par des virgules.

Le programme renvoie une liste de listes, chaque liste représentant un chemin valide du début à la fin. S'il n'y a pas de route valide, la réponse est une liste vide.

Dans le lien TIO, un texte de pied de page affiche le résultat avec chaque mot séparé par des espaces et chaque liste de mots séparés par des retours à la ligne. Si une représentation sous-jacente de liste imprimée est préférée, cela pourrait être fait commeÇŒṘ .

Contrairement à 05ABIE, il n'y a pas de distance intégrée pour Levenshtein, donc ce programme compare les outfixes avec un seul caractère manquant, quelque peu similaire à la solution de @ ChasBrown , bien qu'avec une touche Jelly.

Explication

Lien d'aide: lien monadique qui prend une liste de mots et renvoie une liste de listes étendues possibles, ou une liste vide si aucune autre extension n'est possible

⁵ḟ                      | 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)

Lien 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 octets

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])

Essayez-le en ligne!