Word changer adalah gim di mana Anda mencoba mengubah satu kata menjadi yang lain melalui pengeditan karakter tunggal, dengan setiap langkah menjadi kata-katanya sendiri. Untuk tantangan ini, pengeditan dapat berupa penggantian, penyisipan, atau penghapusan. Misalnya, PEMENANG → PECUNDANG dapat dilakukan dengan rute ini (mungkin ada yang lain):

WINNER
DINNER
DINER
DINE
LINE
LONE
LOSE
LOSER

Dengan kata lain, Anda harus dapat mencapai satu kata dari yang lain hanya melalui kata-kata lain pada jarak Levenshtein 1 setiap kali.

Coding

Anda akan diberikan daftar kata dan dua kata dan Anda harus menampilkan rute yang valid dari satu kata ke kata lain jika ada rute atau nilai konstan yang berbeda atau perilaku yang konsisten jika tidak ada rute.

• Anda dapat mengasumsikan bahwa kata-kata input keduanya dalam daftar kata
• Daftar kata dapat diambil melalui format datar yang nyaman.
  • Daftar, set, percobaan, string yang dipisahkan ruang, dan file yang dipisahkan baris semuanya valid (misalnya), tetapi grafik pra-komputasi dari kedekatan Levenshtein tidak.
• Rute output harus mencakup kedua kata input, tetapi yang dimulai dan berakhir tidak masalah.
• Jika tidak ada rute yang ditemukan, Anda dapat menampilkan konstanta tertentu, nilai falsy, daftar kosong, melemparkan pengecualian, keluar dengan kode bukan nol, atau perilaku lain yang terjadi dalam waktu yang terbatas.
• Rute tidak perlu optimal dan tidak ada persyaratan rute mana yang harus diambil
• Kompleksitas komputasi tidak menjadi masalah, namun program Anda harus dapat dibuktikan berakhir dalam waktu yang terbatas. (Bahkan jika itu akan melampaui kematian panas alam semesta)
• Anda dapat menganggap semua kata seluruhnya terdiri dari huruf dalam kasus yang sama

Contoh Kasus Uji

• CAT → DOG; [CAT, DOG, COG, COT, FROG, GROG, BOG]
  • CAT, COT, COG, DOG
• MANDI → MANDI; [BATH, SHOWER, HATH, HAT, BAT, SAT, SAW, SOW, SHOW, CARA]
  • Tidak Ditemukan Rute
• BREAK → FIX; [BREAK, FIX, BEAK, BREAD, BACA, BEAD, RED, BED, BAD, BID, FAD, FAX]
  • BREAK, BREAD, BEAD, BAD, FAD, FAX, FIX
• BUILD → HANCURKAN; [BUILD, DESTROY, BUILT, GUILT, GUILD, GILD, GILL, BILL, DILL, FILL, DESTRUCT, STRUKTUR, KONSTRUKSI]
  • Tidak Ditemukan Rute
• CARD → BOARD; [KARTU, DEWAN, BARD]
  • KARTU, BARD, PAPAN
• DEMON → ANGEL; [DEMON, MALAIKAT]
  • Tidak Ditemukan Rute
• TERAKHIR → MASA LALU; ]
  • TERAKHIR, MASA LALU
• INSERT → DELETE; Daftar kata ini
  • INSERT, INVERT, INVENT, INBENT, UNBENT, UNBEND, UNBIND, UNKING, UNKING, INKING, IRKING, DIRKING, DARKING, DARLING, ARLING, AILING, SIRING, SERING, SERINE, NERINE, NERITE, NERITE, CERATE, DERATE, DATE MENGHAPUS

05AB1E , 23 21 20 byte

Mencetak daftar rute yang valid.
Disimpan 2 byte berkat Kevin Cruijssen .

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

Cobalah online!

JavaScript (V8) ,  177  176 byte

Mengambil input sebagai (target)(source, list). Mencetak semua rute yang mungkin. Atau mencetak apa pun jika tidak ada solusi.

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

Cobalah online!

Berkomentar

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

Bahasa Wolfram (Mathematica) , 59 byte

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

Cobalah online!

Python 2 , 155 byte

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)

Cobalah online!

Mengambil dua kata dan satu set kata sebagai input; mengembalikan rute (tidak optimal) jika ada sebagai daftar string, jika tidak mengembalikan False.

Fragmen ini:

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

adalah Truejika dan hanya jika a==watau amemiliki jarak Levenshtein 1dari w.

Bahasa Wolfram (Mathematica) , 124 byte

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

Cobalah online!

Python 2 , 163 byte

Jika rute ditemukan, itu adalah output ke stderr dan program keluar dengan kode keluar 1.
Jika tidak ada rute, tidak ada output dan program berakhir dengan kode keluar 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:]]

Cobalah online!

Python 3 , 217 214 212 201 byte

-11 byte thanx ke petunjuk dari 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)

Cobalah online!

Jelly , 38 byte

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

Cobalah online!

Program lengkap yang menerima tiga argumen. Yang pertama adalah kata awal dan diberikan sebagai [["START"]]. Argumen kedua adalah kata terakhir, diberikan sebagai "END". Argumen ketiga adalah daftar kata, diberikan seperti dikutip, kata-kata yang dipisahkan koma.

Program mengembalikan daftar daftar, dengan setiap daftar mewakili jalur yang valid dari awal hingga akhir. Jika tidak ada rute yang valid, responsnya adalah daftar kosong.

Di tautan TIO, ada teks footer untuk menampilkan hasilnya dengan baik dengan setiap kata dipisahkan oleh spasi dan setiap daftar kata dipisahkan oleh baris baru. Jika representasi daftar yang mendasari cetakan lebih disukai, ini bisa dilakukan sebagai ÇŒṘ.

Tidak seperti 05ABIE, tidak ada built-in untuk jarak Levenshtein, jadi program ini membandingkan perbaikan dengan satu karakter yang hilang, agak mirip dengan solusi @ ChasBrown , meskipun dengan twist Jelly.

Penjelasan

Tautan bantuan: tautan monadik yang mengambil daftar kata dan mengembalikan daftar daftar yang mungkin diperluas, atau daftar kosong jika tidak ada ekstensi lebih lanjut yang dimungkinkan

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

Tautan utama

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

Cobalah online!