Cuando era más joven, solía jugar un juego de palabras llamado Word chain . Fue muy simple. El primer jugador elige una palabra; el siguiente jugador dice otra palabra que comienza con la misma letra con la que terminó la palabra anterior. ¡Esto continúa para siempre hasta que alguien se rinde! El truco es que no puedes usar la misma palabra dos veces (¡a menos que todos olviden que esa palabra incluso se usó! Por lo general, jugamos con cierto tema para hacerlo más difícil. Pero ahora, quiero que hagas un programa para hacer esto por mí.

Desafío

Escriba un programa o función completa para encontrar todas las cadenas de palabras más largas posibles utilizando un conjunto de palabras dado y comience la palabra.

Este es el código de golf , por lo que gana el código más corto.

Entrada

Hay dos entradas: una lista y una palabra de inicio. La palabra de inicio no estará en la lista. Todas las entradas son minúsculas ASCII y la lista no contendrá palabras duplicadas.

Salida

Todas las secuencias de palabras de la lista de manera que:

• La palabra de inicio es la primera palabra en la secuencia.

• Cada palabra posterior comienza con la misma letra que la última letra de la palabra anterior.

• La longitud de la secuencia es la más larga posible .

Si hay varias secuencias más largas, envíe todas ellas.

La secuencia no necesariamente necesita contener todas las palabras de la lista. A veces eso no es posible (ver casos de prueba). De nuevo, ¡ninguna palabra se puede usar dos veces!

Casos de prueba

In: [hello, turtle, eat, cat, people] artistic
Out:  [artistic, cat, turtle, eat]
In: [lemonade, meatball, egg, grape] ham 
Out: [ham, meatball, lemonade, egg, grape]
In: [cat, cute, ewok] attic
Out: [attic, cute, ewok]
In:[cat, cute, ewok, kilo, to, otter] attic
Out: [attic, cute, ewok, kilo, otter]
In:[cat, today, yoda, attic] ferret
Out: [ferret, today, yoda, attic, cat]
In: [cancel, loitering, gnocchi, improv, vivic, child, despair, rat, tragic, chimney, rex, xylophone] attic
Out: [[attic, child, despair, rat, tragic, cancel, loitering, gnocchi, improv, vivic, chimney], [attic, cancel, loitering, gnocchi, improv, vivic, child, despair, ra', tragic, chimney]]
In: [cat, today, yoda, artistic, cute, ewok, kilo, to, otter] attic
Out: [attic, cat, today, yoda, artistic, cute, ewok, kilo, otter]

Pyth, 25 23 bytes

.MlZfqhMtTeMPT+Lzs.pMyQ

Banco de pruebas

Una solución de fuerza bruta. Demasiado lento para algunos de los casos de prueba más grandes.

Entrada en el formulario:

attic
["cat", "today", "yoda", "to", "otter"] 

Salida en la forma:

[['attic', 'cat', 'today', 'yoda'], ['attic', 'cat', 'to', 'otter']]

Explicación:

.MlZfqhMtTeMPT+Lzs.pMyQ
                           Q = eval(input()) (The list of words)
                           z = input()       (The starting word)
                     yQ    All subsets of the input.
                  .pM      All permutations of the subsets.
                 s         Flatten.
              +Lz          Add the starting word to the front of each list.
                           This is all possible sequences.
    f                      Filter on
     q                     The equality of
      hMtT                 The first character of each word but the first
          eMPT             The last character of each word but the last
.MlZ                       Take only the lists of maximal length.

JavaScript (ES6), 164 bytes

f=(l,s,r=[[]])=>l.map((w,i)=>w[0]==s.slice(-1)&&(x=l.slice(),x.splice(i,1),o=f(x,w),a=o[0].length,b=r[0].length,r=a>b?o:a<b?r:r.concat(o)))&&r.map(q=>[s].concat(q))

Explicación

Una función recursiva que comprueba cuánto tiempo durará la lista de salida para todas las opciones posibles.

Devuelve una matriz de matrices de palabras.

f=(l,s,r=[[]])=>            // l = list, s = starting word, r is not passed (it is
                            //     here so that it is not defined globally)
  l.map((w,i)=>             // for each word w at index i
    w[0]==s.slice(-1)&&(    // if the first letter is the same as the last letter:
      x=l.slice(),          // x = clone of the list of words
      x.splice(i,1),        // remove the current word
      o=f(x,w),             // get the list of words starting from the current word
      a=o[0].length,
      b=r[0].length,
      r=a>b?o:              // if o is longer, set r to o
        a<b?r:              // if o is shorter, keep r
        r.concat(o)         // if o is same, add it to r
    )
  )
  &&r.map(q=>[s].concat(q)) // return a list of longest lists with the starting word

Prueba

El parámetro predeterminado no se utiliza en la prueba para que sea más compatible con todos los navegadores.

f=(l,s,r)=>l.map((w,i)=>w[0]==s.slice(-1)&&(x=l.slice(),x.splice(i,1),o=f(x,w),a=o[0].length,b=r[0].length,r=a>b?o:a<b?r:r.concat(o)),r=[[]])&&r.map(q=>[s].concat(q))

Word list (space separated) = <input type="text" id="list" value="cancel loitering gnocchi improv vivic child despair rat tragic chimney rex xylophone" /><br />
Starting word = <input type="text" id="word" value="attic" /><br />
<button onclick="result.textContent=f(list.value.split(' '),word.value).join('\n')">Go</button>
<pre id="result"></pre>

Python, 104

def f(d,w):
 a=[[w]]
 while a:b=a;a=[x+[y]for x in a for y in set(d)-set(x)if x[-1][-1]==y[0]]
 return b

Creo que debería funcionar ahora ...

Pruébalo en línea .

Perl 5, 275 bytes

Probablemente no haya jugado al golf tanto como sea posible, pero, oye, de todos modos no es ganador, ¿verdad?

use List::Util max;use List::MoreUtils uniq,before;use Algorithm::Permute permute;$i=pop;permute{push@c,[@ARGV]}@ARGV;for$c(@c){unshift@$c,$i;push @{$d{before{(substr$c->[$_],-1)ne(substr$c->[1+$_],0,1)}keys$c}},$c}for$m(max keys%d){say for uniq map{"@$_[0..$m+1]"}@{$d{$m}}}

Úselo así:

$ perl -M5.010 chain.pl cat tin cot arc
arc cat tin
arc cot tin

¡Advertencia! ¡El uso de este script en una lista larga requiere mucha memoria! Me funcionó muy bien en siete (seis más el extra) pero no en trece (doce más uno).

Elimina la entrada final, genera una matriz de arrayrefs, donde los arrayrefs son todas las permutaciones, y agrega la palabra inicial al comienzo. Luego, empuja cada una de esas permutaciones a otra matriz, que es el valor de un hash con clave, la cantidad de la matriz que tiene la propiedad de encadenamiento deseada. Luego encuentra la clave máxima e imprime todas las matrices.

C, 373 bytes

g(char*y){printf("%s, ",y);}z(char*w){int i,k=-1,v=0,j=sizeof(c)/sizeof(c[0]);int m[j],b=0;for(i=0;i<j;i++){m[v++]=c[i][0]==w[strlen(w)-1]?2:1;if(u[i]==6)m[v-1]=1;if(strcmp(w,c[i]))k=i;}printf("%s",w);for(i=0;i<j;i++){if(m[i]!=1){if(v+i!=j){g(s);for(;b<j;b++){if(u[b]==6)g(c[b]);}}else printf(", ");u[i]=6;z(c[i]);u[i]=1;}else v+=-1;}if(k!=-1)u[k]=1;if(v==0)printf(" ; ");}

Creo que probablemente haya mucho más golf que pueda hacer aquí, así que probablemente lo actualizaré.

De-golf

char *c[9]={"cat","today","yoda","artistic","cute","ewok","kilo","to","otter"};
u[9]={-1};
char *s="attic";

g(char*y){printf("%s, ",y);}
z(char*w){
   int i,k=-1,v=0,j=sizeof(c)/sizeof(c[0]);
   int m[j],b=0;
   for(i=0;i<j;i++){
      m[v++]=c[i][0]==w[strlen(w)-1]?i:-1;
      if(u[i]==6)m[v-1]=-1;
      if(strcmp(w,c[i]))k=i;
   }
   printf("%s",w);
   for(i=0;i<j;i++){
      if(m[i]!=-1){
         if(v+i!=j){
            g(s);
            for(;b<j;b++){
                if(u[b]==6)g(c[b]);
             }
         }else printf(", ");
         u[i]=6;
         z(c[i]);
         u[i]=-1;
      } else v+=-1;
   }
   if(k!=-1)u[k]=-1;
   if(v==0)printf(" ; ");
}

main(){
   z(s);
   printf("\n");
   return 0;
}

Enlace de Ideone : si no lo hice bien, hágamelo saber: D