Word changer is a game where you are trying to turn one word into another via single-character edits, with each step being its own word. For this challenge, edits may be replacements, insertions, or deletions. For example, WINNER → LOSER can be done with this route (there may be others):

WINNER

DINNER

DINER

DINE

LINE

LONE

LOSE

LOSER

Phrased another way, you must be able to reach one word from the other going only through other words at a Levenshtein distance of 1 each time.

Coding

You will be given a word list and two words and you must output a valid route from one word to the other if a route exists or a distinct constant value or consistent behavior if no route exists.

• You may assume that the input words are both in the word list


• The word list can be taken in via any convenient flat format.
  
  
  
  
  • Lists, sets, tries, space-separated strings, and line-separated files are all valid (for instance), but a pre-computed graph of Levenshtein adjacency is not.
  
  
  
  


• The output route should include both input words, but which starts and ends doesn't matter.


• If no route is found, you can output a specific constant, a falsy value, empty list, throw an exception, exit with a nonzero code, or any other behavior that happens in finite time.


• The route does not need to be optimal


• Computational complexity does not matter, however your program must be provably guaranteed to terminate in a finite amount of time. (even if it would run beyond the heat death of the universe)


• You may assume all words are entirely composed of letters in the same case

Example Test Cases

• CAT → DOG; [CAT, DOG, COG, COT, FROG, GROG, BOG]
  
  
  
  
  • CAT, COT, COG, DOG
  
  
  
  


• BATH → SHOWER; [BATH, SHOWER, HATH, HAT, BAT, SAT, SAW, SOW, SHOW, HOW]
  
  
  
  
  • No Route Found
  
  
  
  


• BREAK → FIX; [BREAK, FIX, BEAK, BREAD, READ, BEAD, RED, BED, BAD, BID, FAD, FAX]
  
  
  
  
  • BREAK, BREAD, BEAD, BAD, FAD, FAX, FIX
  
  
  
  


• BUILD → DESTROY; [BUILD, DESTROY, BUILT, GUILT, GUILD, GILD, GILL, BILL, DILL, FILL, DESTRUCT, STRUCTURE, CONSTRUCT]
  
  
  
  
  • No Route Found
  
  
  
  


• CARD → BOARD; [CARD, BOARD, BARD]
  
  
  
  
  • CARD, BARD, BOARD
  
  
  
  


• DEMON → ANGEL; [DEMON, ANGEL]
  
  
  
  
  • No Route Found
  
  
  
  


• LAST → PAST; [LAST, PAST, BLAST, CAST, BLACK, GHOST, POST, BOAST]
  
  
  
  
  • LAST, PAST
  
  
  
  


• INSERT → DELETE; This word list
  
  
  
  
  • INSERT, INVERT, INVENT, INBENT, UNBENT, UNBEND, UNBIND, UNKIND, UNKING, INKING, IRKING, DIRKING, DARKING, DARLING, ARLING, AILING, SIRING, SERING, SERINE, NERINE, NERITE, CERITE, CERATE, DERATE, DELATE, DELETE
  
  
  
  

JavaScript (V8),  177  176 bytes

Takes input as (target)(source, list). Prints all possible routes. Or prints nothing if there's no 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))

Try it online!

Commented

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

05AB1E, 23 21 bytes

Saved 2 bytes thanks to Kevin Cruijssen

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

Try it online!

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

Try it online!

Python 2, 163 bytes

If a route is found, it is output to stderr and the program exits with exit code 1.

If there is no route, there is no output and the program terminates with exit code 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:]]

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

Try it online!

Takes two words and a set of words as input; returns a (non-optimal) route if one exists as a list of strings, otherwise returns False.

This fragment:

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

is True if and only if a==w or a has Levenshtein distance of 1 from w.