Фон

Три года назад этот парень Том Мерфи задумал распространить идею портманто на все слова в языке и назвал это portmantout ( portmanteau plus tout [Французский для всех ]). Определив английский как список из 108 709 слов, он сумел найти последовательность из 611 820 букв со следующими двумя свойствами:

• Каждое английское слово содержится в строке.
• Некоторая окрестность, содержащая любые две соседние буквы в строке, является английским словом.

Вот ссылка на страницу, на которой можно найти этот portmantout (вместе с объяснением видео).

Portmantout

Первое из двух свойств portmantout легко понять. Второе может потребовать некоторого объяснения.

По сути, слова должны совпадать. "golfcode" никогда не появится в portmantout английского языка, так как там нет слова, содержащего "fc". Тем не менее, вы можете найти «codegolf» в portmantout, поскольку «эго» устраняет пробел (а все остальные пары букв находятся либо в «коде», либо в «гольфе»).

Твое задание:

Напишите программу или функцию, которая принимает список строк и возвращает любой портмантут из списка.

Этот код Python 3 проверит вывод порта.

Контрольные примеры

Все списки неупорядочены; то есть,

{"code", "ego", "golf"} -> "codegolf"
{"more", "elm", "maniac"} -> "morelmaniac" or "morelmorelmaniac" or "morelmorelmorelmaniac" or...
    Would a morelmaniac be some sort of mycologist?
{"ab", "bc", "cd", "de", "ef", "fg", "gh", "hi", "ij", "jk", "kl", "lm", "mn", "no", "op", "pq", "qr", "rs", "st", "tu", "uv", "vw", "wx", "xy", "yz", "za"} -> "abcdefghijklmnopqrstuvwxyza" or "rstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" or any 27+ letters in order

И почему бы нет? Огромный на сайте Мерфи, если ваш код выполняется в разумные сроки.

правила

• Ваш код должен остановиться.
• Вам не нужно возвращать один и тот же portmantout при каждом выполнении.
• Вы можете предположить , что все строки состоят только из строчных букв aчерез z.
• Если портмантут не возможен, ваша программа может делать что угодно. Пример:{"most", "short", "lists"}
• Применяются стандартные правила для ввода / вывода и лазеек .

Это код-гольф , поэтому выигрывает самое короткое решение (в байтах) на каждом языке! Удачного игры в гольф!

Python 2 , 204 202 байта

def f(l,s=''):
 if all(w in s for w in l):return s
 for i,w in enumerate(l):
	a=next((s+w[i:]for i in range(len(w)-1,0,-1)if s[-i:]==w[:i]),0)if s else w;x=a and f(l[:i]+l[i+1:]+[l[i]],a)
	if x:return x

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

Сохраненный

• -2 байта, благодаря рекурсивному

Pyth, 39 байт

JQW}_1mxbdQ=+J|=b*qKOQ<=T+OP._KOJlKTY)b

Попробуй здесь

объяснение

JQW}_1mxbdQ=+J|=b*qKOQ<=T+OP._KOJlKTY)b
JQ                                        Get a copy of the input.
  W}_1mxbdQ                          )    While there are words in the input
                                          that aren't in b (initially space)...
                   KOQ    OP._KOJ         ... get a random input word, a random
                                          prefix, and a random joined word...
                       =T+                ... stick them together...
                  q   <          lKT      ... and check if joining them together
                                          is valid...
               =b*                        ... then update b accordingly...
           =+J|                     Y     ... and stick the new word into J.
                                      b   Output the final result.

Stax , 39 36 байт

ä▬│•.k=╠lƒ☺╜00║¿~,▓╕╠7ÉΔB<e┼>☼Θ²└ô┴\

Запустите и отладьте его

Запускает все контрольные примеры детерминистически за секунду.

Это рекурсивный алгоритм.

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

Вот программа распакована, разархивирована и прокомментирована.

FG              for each word in input, call target block
}               unbalanced closing brace represents call target
  x{[#o         sort input words by their number of occurrences in the current candidate
  Y             store it in register Y
  h[#{,}M       if all of the words occur at least once, pop from input stack
                input stack is empty, so this causes immediate termination,
                followed by implicitly printing the top of the main stack
  yF            for each word in register y, do the following
    [n|]_1T|[|& intersect the suffixes of the candidate with prefixes of the current word
    z]+h        get the first fragment in the intersection, or a blank array
    Y           store it in register Y
    %t+         join the candidate with the current word, eliminating the duplicate fragment
    y{G}M       if the fragment was non-blank, recursively call to the call target
    d           pop the top of stack

Запустите этот

Изменить: Это не работает для класса входов, который имеет цикл, как ["ab", "ba", "ca"], как и большинство других опубликованных ответов.

JavaScript (ES6), 138 130 байт

f=a=>a[1]?a.map((c,i)=>a.map((w,j,[...b])=>i!=j&&!/0/.test(m=(c+0+w).split(/(.+)0\1/).join``)?t=f(b,b[i]=m,b.splice(j,1)):0))&&t:a

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

Ungolfed:

f = a =>
  a[1] ?                                        //if more than one element ...
    a.map((c, i)=>                              // for each element
      a.map((w, j, [...b])=>                    //  for each element
        i != j &&                               //   if not the same element
        !/0/.test(m=(c+0+w).split(/(.+)0\1/).join``) &&  //   and the elements overlap
        (t = f(b,                               //   and f recursed is true when
               b[i] = m,    //    replacing the ith element with the 2-element portmanteau
               b.splice(j, 1)                   //    and removing the jth element
              )
        )
      )
    ) &&
    t :                                         //return the recursed function value
    a                                           //else return a

f=a=>a[1]?a.map((c,i)=>a.map((w,j,[...b])=>i!=j&&!/0/.test(m=(c+0+w).split(/(.+)0\1/).join``)?t=f(b,b[i]=m,b.splice(j,1)):0))&&t:a

console.log(f(["sic", "bar", "rabbits", "cradle"])+'')             // "barabbitsicradle"
console.log(f(["mauve", "elated", "cast", "electric", "tame"])+'') // "mauvelectricastamelated"

console.log(f(["more", "elm", "maniac"])+'')                       // "morelmaniac"
console.log(f(["elm", "more", "maniac"])+'')                       // "morelmaniac"
console.log(f(["more", "maniac", "elm"])+'')                       // "morelmaniac"

console.log(f(["ego", "code", "golf"])+'')                         // "codegolf"
console.log(f(["code", "ego", "golf"])+'')                         // "codegolf"
console.log(f(["golf", "ego", "code"])+'')                         // "codegolf"

console.log(f(['ab', 'bc', 'cd', 'de'])+'');                       // "abcde"
console.log(f(['de', 'bc', 'cd', 'ab'])+'');                       // "abcde"

console.log(f(["ab", "ba", "ca"])+'');                             // "caba"

Код мучительно медленный на примере полного алфавита (по этой причине не включен в приведенный выше фрагмент).

Это исправляется изменением maps на somes для потери 2 байтов:

f=a=>a[1]?a.some((c,i)=>a.((w,j,[...b])=>i!=j&&!/0/.test(m=(c+0+w).split(/(.+)0\1/).join``)?t=f(b,b[i]=m,b.splice(j,1)):0))&&t:a

f=a=>a[1]?a.some((c,i)=>a.some((w,j,[...b])=>i!=j&&!/0/.test(m=(c+0+w).split(/(.+)0\1/).join``)?t=f(b,b[i]=m,b.splice(j,1)):0))&&t:a

console.log(f(["ab", "bc", "cd", "de", "ef", "fg", "gh", "hi", "ij", "jk", "kl", "lm", "mn", "no", "op", "pq", "qr", "rs", "st", "tu", "uv", "vw", "wx", "xy", "yz", "za"])+'');

console.log(f(["ab", "ba", "ca"])+'');                             // "caba"