Чейнджер слов - это игра, в которой вы пытаетесь превратить одно слово в другое с помощью односимвольных правок, причем каждый шаг - это свое слово. Для этой задачи изменения могут быть заменами, вставками или удалениями. Например, WINNER → LOSER может быть сделано с этим маршрутом (могут быть другие):

WINNER
DINNER
DINER
DINE
LINE
LONE
LOSE
LOSER

Иными словами, вы должны быть в состоянии найти одно слово из другого, проходя только через другие слова на расстоянии Левенштейна 1 каждый раз.

кодирование

Вам будет предоставлен список слов и два слова, и вы должны вывести действительный маршрут от одного слова к другому, если маршрут существует, или отдельное постоянное значение или согласованное поведение, если маршрут не существует.

• Вы можете предположить, что оба входных слова находятся в списке слов
• Список слов может быть взят через любой удобный плоский формат.
  • Списки, наборы, попытки, строки, разделенные пробелами, и файлы, разделенные строками, являются действительными (например), но предварительно вычисленный граф смежности Левенштейна - нет.
• Выходной маршрут должен включать оба входных слова, но начало и конец не имеют значения.
• Если маршрут не найден, вы можете вывести определенную константу, ложное значение, пустой список, выбросить исключение, выйти с ненулевым кодом или выполнить любое другое поведение за конечное время.
• Маршрут не обязательно должен быть оптимальным, и нет требования о том, какой маршрут выбрать.
• Сложность вычислений не имеет значения, однако ваша программа должна быть гарантированно завершена за конечное время. (даже если это выйдет за пределы тепловой смерти вселенной)
• Вы можете предположить, что все слова полностью состоят из букв в одном и том же случае

Примеры тестовых случаев

• КПП → СОБАКА; [CAT, DOG, COG, COT, FROG, GROG, BOG]
  • CAT, COT, COG, DOG
• ВАННА → ДУШ; [ВАННА, ДУШ, ХАТ, ШАП, БАТ, САТ, ПИЛА, СОУ, ШОУ, КАК]
  • Маршрут не найден
• BREAK → FIX; [BREAK, FIX, BEAK, BREAD, READ, BAD, RED, BED, BAD, BID, FAD, FAX]
  • ПЕРЕРЫВ, ХЛЕБ, БУС, ПЛОХО, ФАД, ФАКС, ИСПРАВИТЬ
• СТРОЙ → УНИЧТОЖЕНИЕ; [СТРОИТЬ, УНИЧТОЖИТЬ, СТРОИТЬ, ВИНОВАТЬ, ГИЛЬДИЯ, ЗОЛОТО, ГИЛЛ, БИЛЛ, УКЛ, ЗАПОЛНИТЬ, УНИЧТОЖИТЬ, СТРУКТУРУ, СТРОИТЕЛЬСТВО]
  • Маршрут не найден
• КАРТА → СОВЕТ; [КАРТА, СОВЕТ, БАРД]
  • КАРТА, БАРД, ДОСКА
• ДЕМОН → АНГЕЛ; [ДЕМОН, АНГЕЛ]
  • Маршрут не найден
• ПОСЛЕДНО → ПРОШЛОЕ; [ПОСЛЕДНЕЕ, ПРОШЛОЕ, БЛАСТ, БЫСТРО, ЧЕРНЫЙ, ПРИЗРАК, ПОСТ, БАСТ
  • ПОСЛЕДНО, ПРОШЛОЕ
• ВСТАВИТЬ → УДАЛИТЬ; Этот список слов
  • INSERT, INVERT, INVENT, INBENT, UNBENT, UNBEND, UNBIND, UNKIND, UNKING, INKING, IRKING, DIRKING, DARING, ARLING, AILING, SIRING, SERING, SERINE, NERINE, NERITE, CERITE, CERATE, DERATE, DELATE, DELATE, DELATE УДАЛЯТЬ

05AB1E , 23 21 20 байт

Распечатывает список действительных маршрутов.
Сохранено 2 байта благодаря Кевину Круйссену .

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

Попробуйте онлайн!

JavaScript (V8) ,  177  176 байт

Принимает вход как (target)(source, list) . Печатает все возможные маршруты. Или ничего не печатает, если нет решения.

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

Попробуйте онлайн!

комментарии

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 байт

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

Попробуйте онлайн!

Python 2 , 155 байт

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)

Попробуйте онлайн!

Принимает два слова и набор слов в качестве входных данных; возвращает (неоптимальный) маршрут, если он существует в виде списка строк, в противном случае возвращает False.

Этот фрагмент:

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

это Trueесли и только если a==wили aимеет расстояние Левенштейна 1от w.

Wolfram Language (Mathematica) , 124 байта

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

Попробуйте онлайн!

Python 2 , 163 байта

Если маршрут найден, он выводится в stderr, и программа завершает работу с кодом выхода 1.
Если маршрута нет, выход не выводится, и программа завершается с кодом выхода 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:]]

Попробуйте онлайн!

Питон 3 , 217 214 212 201 байт

-11 байт спасибо подсказке от 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)

Попробуйте онлайн!

Желе , 38 байт

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

Попробуйте онлайн!

Полная программа, принимающая три аргумента. Первое - это начальное слово, которое предоставляется как [["START"]]. Второй аргумент - последнее слово, поставляемое как "END". Третий аргумент - это список слов, представленный в кавычках, через запятую.

Программа возвращает список списков, каждый из которых представляет действительный путь от начала до конца. Если действительного маршрута нет, ответом будет пустой список.

В ссылке TIO есть текст нижнего колонтитула, чтобы аккуратно отобразить результат с каждым словом, разделенным пробелами, и каждым списком слов, разделенных символом новой строки. Если распечатка в виде представления списка предпочтительна, это можно сделать какÇŒṘ .

В отличие от 05ABIE, здесь нет встроенного расстояния Левенштейна, поэтому эта программа сравнивает наложения с отсутствующим одиночным символом, что несколько похоже на решение @ ChasBrown , хотя и с поворотом Jelly.

объяснение

Вспомогательная ссылка: монадическая ссылка, которая принимает список слов и возвращает список возможных расширенных списков или пустой список, если дальнейшее расширение невозможно

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

Главная ссылка

              €         | 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 байт

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

Попробуйте онлайн!