Antecedentes

Hace tres años, este tipo Tom Murphy se le ocurrió pensar en extender la idea de un acrónimo a todas las palabras en un idioma y llamó a esto un portmantout ( portmanteau plus tout [francés para todos ]). Al definir el inglés como una lista de 108,709 palabras, logró encontrar una secuencia de 611,820 letras con las siguientes dos propiedades:

• Cada palabra en inglés está contenida en la cadena.
• Un vecindario que contiene dos letras adyacentes en la cadena es una palabra en inglés.

Aquí hay un enlace a una página en la que se puede encontrar este portmantout (junto con una explicación en video).

Un portmantout

La primera de las dos propiedades de un portmantout es fácil de entender. El segundo puede requerir alguna explicación.

Básicamente, las palabras deben superponerse. "golfcode" nunca aparecerá en un portmantout de inglés, ya que no hay una palabra que contenga el "fc". Sin embargo, puede encontrar "codegolf" en un portmantout, ya que "ego" cierra la brecha (y todos los demás pares de letras están en "código" o "golf").

Tu tarea:

Escriba un programa o función que tome una lista de cadenas y devuelva cualquier portmantout de la lista.

Este código de Python 3 verificará un portmantout.

Casos de prueba

Todas las listas están desordenadas. es decir,

{"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

¿Y por qué no? El masivo en el sitio de Murphy, si su código se ejecuta dentro de un tiempo razonable.

Reglas

• Tu código debe detenerse.
• No necesita devolver el mismo portmantout con cada ejecución.
• Usted puede asumir todas las cadenas se componen de sólo letras en minúscula aa través z.
• Si no es posible portmantout, su programa puede hacer cualquier cosa. Ex:{"most", "short", "lists"}
• Se aplican las reglas estándar para E / S y lagunas .

Este es el código de golf , por lo que gana la solución más corta (en bytes) en cada idioma. ¡Feliz golf!

Python 2 , 204 202 bytes

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

Pruébalo en línea!

Salvado

• -2 bytes, gracias a recursivo

Pyth, 39 bytes

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

Pruébalo aquí

Explicación

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 bytes

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

Ejecutar y depurarlo

Ejecuta todos los casos de prueba de manera determinista en aproximadamente un segundo.

Este es un algoritmo recursivo.

• Comience con cada palabra de entrada como candidato
• En cada paso, ordene las palabras por la cantidad de veces que aparecen como subcadenas del candidato.
• Para cada palabra que sea compatible con el final del candidato actual, únase a la palabra para formar un nuevo candidato y haga una llamada recursiva.

Aquí está el programa desempaquetado, sin golf y comentado.

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

Ejecute este

Editar: esto falla para una clase de entradas que tiene un bucle, como ["ab", "ba", "ca"], al igual que la mayoría de las otras respuestas publicadas.

JavaScript (ES6), 138 130 bytes

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

Devuelve un error para las listas que no se pueden portar por completo.

Sin golf:

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"

El código es insoportablemente lento en el ejemplo del alfabeto completo (no incluido por esa razón en el fragmento anterior).

Eso se soluciona cambiando los maps a somes, por la pérdida de 2 bytes:

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"