Zmieniacz słów to gra, w której próbujesz zamienić jedno słowo w drugie za pomocą edycji pojedynczych znaków, przy czym każdy krok jest własnym słowem. W przypadku tego wyzwania edycjami mogą być zastąpienia, wstawienia lub usunięcia. Na przykład, WINNER → LOSER można wykonać na tej trasie (mogą być inne):

WINNER
DINNER
DINER
DINE
LINE
LONE
LOSE
LOSER

Inaczej mówiąc, musisz być w stanie dotrzeć do jednego słowa od drugiego, przechodząc tylko przez inne słowa w odległości Levenshteina równej 1 za każdym razem.

Kodowanie

Otrzymasz listę słów i dwa słowa i musisz podać prawidłową trasę z jednego słowa do drugiego, jeśli istnieje trasa lub wyraźna stała wartość lub spójne zachowanie, jeśli nie ma trasy.

• Możesz założyć, że słowa wejściowe znajdują się na liście słów
• Listę słów można pobrać w dowolnym wygodnym formacie płaskim.
  • Listy, zestawy, próby, łańcuchy rozdzielone spacjami i pliki rozdzielone wierszem są poprawne (na przykład), ale wstępnie obliczony wykres przylegania Levenshteina nie jest.
• Ścieżka wyjściowa powinna zawierać oba słowa wejściowe, ale to, który początek i koniec nie ma znaczenia.
• Jeśli nie zostanie znaleziona żadna trasa, możesz wyprowadzić określoną stałą, wartość fałszowania, pustą listę, wyrzucić wyjątek, wyjść z niezerowym kodem lub inne zachowanie, które dzieje się w skończonym czasie.
• Trasa nie musi być optymalna i nie ma wymogu wyboru trasy
• Złożoność obliczeniowa nie ma znaczenia, jednak należy zagwarantować, że Twój program zakończy działanie w skończonym czasie. (nawet gdyby uciekł poza śmierć z powodu upałów we wszechświecie)
• Możesz założyć, że wszystkie słowa składają się w całości z liter w tym samym przypadku

Przykładowe przypadki testowe

• KOT → Pies; [KOT, PIES, KOG, ŁÓŻKO, ŻABA, GROG, BOG]
  • CAT, COT, COG, DOG
• KĄPIEL → PRYSZNIC; [KĄPIEL, PRYSZNIC, HATH, HAT, BAT, SAT, SAW, SOW, SHOW, HOW]
  • Nie znaleziono trasy
• PRZERWA → POPRAWKA; [PRZERWA, FIX, BEAK, CHLEB, CZYTANIE, KORALIK, CZERWONY, ŁÓŻKO, ZŁY, BID, FAD, FAKS]
  • PRZERWA, CHLEB, BEAD, BAD, FAD, FAKS, NAPRAWA
• BUDOWA → ZNISZCZENIE; [BUDOWLANY, ZNISZCZONY, BUDOWANY, WILGOCI, GILDIA, GILD, BILL, BILL, KOPALNY, WYPEŁNIJ, ZNISZCZENIE, STRUKTURA, KONSTRUKCJA]
  • Nie znaleziono trasy
• KARTA → TABLICA; [KARTA, TABLICA, BARD]
  • KARTA, BARD, TABLICA
• DEMON → ANIOŁ; [DEMON, ANIOŁ]
  • Nie znaleziono trasy
• OSTATNI → PRZESZŁOŚĆ; [LAST, PAST, BLAST, CAST, BLACK, GHOST, POST, BOAST]
  • OSTATNI, PRZESZŁOŚĆ
• WSTAW → USUŃ; Ta lista słów
  • WSTAW, ODWRÓCONY, WYNALAZKOWY, WEWNĘTRZNY, NIEWYGRANY, NIEZGIĘTY, ODŁĄCZ, ODŁĄCZ, ODBIERZANIE, WTUROWANIE, IRKOWANIE, SPALANIE, CIEMNOŚĆ, ROZWINIĘCIE, USUWANIE, LECZENIE, SIRING, SEROWANIE, SERINE, NERINE, NERITE, CERITE, CERATE, DELATE, DERATE USUNĄĆ

05AB1E , 23 21 20 bajtów

Drukuje listę prawidłowych tras.
Zaoszczędzono 2 bajty dzięki Kevinowi Cruijssenowi .

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

Wypróbuj online!

JavaScript (V8) ,  177  176 bajtów

Pobiera dane wejściowe jako (target)(source, list). Drukuje wszystkie możliwe trasy. Lub nic nie drukuje, jeśli nie ma rozwiązania.

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

Wypróbuj online!

Skomentował

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 bajtów

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

Wypróbuj online!

Python 2 , 155 bajtów

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)

Wypróbuj online!

Pobiera na wejściu dwa słowa i zestaw słów; zwraca (nieoptymalną) trasę, jeśli istnieje jako lista ciągów, w przeciwnym razie zwraca False.

Ten fragment:

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

jest Truewtedy i tylko wtedy, a==wczy ama Levenshteina odległości 1od w.

Wolfram Language (Mathematica) , 124 bajty

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

Wypróbuj online!

Python 2 , 163 bajty

Jeśli trasa zostanie znaleziona, jest ona wysyłana do stderr, a program kończy działanie z kodem wyjścia 1.
Jeśli nie ma trasy, nie ma wyjścia, a program kończy się kodem wyjścia 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:]]

Wypróbuj online!

Python 3 , 217 214 212 201 bajtów

-11 bajtów dzięki za wskazówkę od 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)

Wypróbuj online!

Galaretka , 38 bajtów

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

Wypróbuj online!

Pełny program akceptujący trzy argumenty. Pierwsze jest słowem początkowym i jest dostarczane jako [["START"]]. Drugi argument to ostatnie słowo, podane jako "END". Trzecim argumentem jest lista słów, dostarczana jako cytowane, rozdzielane przecinkami słowa.

Program zwraca listę list, przy czym każda lista reprezentuje prawidłową ścieżkę od początku do końca. Jeśli nie ma prawidłowej trasy, odpowiedzią jest pusta lista.

W łączu TIO znajduje się tekst stopki, który ładnie wyświetla wynik przy każdym słowie oddzielonym spacjami i każdej liście słów oddzielonych nowymi liniami. Jeśli preferowany jest wydruk reprezentacji listy, można to zrobić jako ÇŒṘ.

W przeciwieństwie do 05ABIE, nie ma wbudowanego dystansu Levenshteina, więc ten program porównuje outfiksy z brakującym pojedynczym znakiem, nieco podobny do rozwiązania @ ChasBrown , choć z akcentem Jelly.

Wyjaśnienie

Łącze pomocnicze: łącze monadyczne, które pobiera listę słów i zwraca listę możliwych rozszerzonych list lub pustą listę, jeśli dalsze rozszerzenie nie jest możliwe

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

Główny 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)

Swift 4.2 / Xcode 10.2.1 , 387 bajtów

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

Wypróbuj online!