Word Changer Reachability

Question

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 and there is no requirement of which route should be taken
• 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

Answer 1

05AB1E, 23 21 20 bytes

Prints a list of valid routes.
Saved 2 bytes thanks to Kevin Cruijssen.

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

Try it online!

Answer 2

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

Answer 3

Wolfram Language (Mathematica), 59 bytes

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

Try it online!

Answer 4

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.

Answer 5

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!

Answer 6

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!

Answer 7

Python 3, 217 214 212 201 bytes

-11 bytes thanx to a hint from 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)

Try it online!

Answer 8

Jelly, 38 bytes

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

Try it online!

A full program accepting three arguments. The first is the starting word and is supplied as [["START"]]. The second argument is the final word, supplied as "END". The third argument is the word list, supplied as quoted, comma-separated words.

The program returns a list of lists, with each list representing a valid path from the start to the end. If there is no valid route, the response is an empty list.

In the TIO link, there is footer text to display the result nicely with each word separated by spaces and each list of words separated by newlines. If a printout underlying list representation is preferred, this could be done as ÇŒṘ.

Unlike 05ABIE, there’s no built-in for Levenshtein distance, so this program compares outfixes with a single character missing, somewhat similar to @ChasBrown’s solution, although with a Jelly twist.

Explanation

Helper link: monadic link that takes a list of words and returns a list of possible extended lists, or an empty list if no further extension is 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)

Main link

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

Answer 9

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

Try it online!