Quand j'étais plus jeune, je jouais à un jeu de mots appelé Chaîne de mots . C'était très simple. Le premier joueur choisit un mot; le joueur suivant dit un autre mot qui commence par la même lettre que le mot précédent se terminait par. Cela continue indéfiniment jusqu'à ce que quelqu'un abandonne! L'astuce est que vous ne pouvez pas utiliser le même mot deux fois (sauf si tout le monde a oublié que ce mot a même été utilisé!). Habituellement, nous jouons avec un certain sujet pour le rendre plus difficile. Mais maintenant, je veux que vous fassiez un programme pour le faire pour moi.

Défi

Écrivez un programme ou une fonction complète pour trouver toutes les chaînes de mots les plus longues possibles en utilisant un ensemble de mots donné et commencez le mot.

C'est le code-golf , donc le code le plus court gagne!

Contribution

Il y a deux entrées: une liste et un mot de départ. Le mot de départ ne sera pas dans la liste. Les entrées sont toutes en ASCII minuscule et la liste ne contiendra pas de mots en double.

Production

Toutes les séquences de mots de la liste telles que:

• Le mot de départ est le premier mot de la séquence.

• Chaque mot suivant commence par la même lettre que la dernière lettre du mot précédent.

• La longueur de la séquence est la plus longue possible .

S'il existe plusieurs séquences plus longues, sortez-les toutes.

La séquence ne doit pas nécessairement contenir tous les mots de la liste. Parfois, ce n'est pas possible (voir les tests). Encore une fois, aucun mot ne peut être utilisé deux fois!

Cas de test

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 octets

.MlZfqhMtTeMPT+Lzs.pMyQ

Suite de tests

Une solution de force brute. Beaucoup trop lent pour certains des cas de test les plus importants.

Saisie sous forme:

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

Sortie sous forme:

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

Explication:

.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 octets

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

Explication

Une fonction récursive qui vérifie la durée de la liste de sortie pour tous les choix possibles.

Renvoie un tableau de tableaux de mots.

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

Tester

Paramètre par défaut non utilisé dans le test pour le rendre plus compatible avec tous les navigateurs.

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

Je pense que ça devrait marcher maintenant ...

Essayez-le en ligne .

Perl 5, 275 octets

Probablement pas autant que possible jouer au golf, mais bon, c'est de toute façon non gagnant, non?

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

Utilisez-le ainsi:

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

Avertissement! L'utilisation de ce script sur une longue liste nécessite beaucoup de mémoire! Cela a très bien fonctionné pour moi sur sept (six plus le supplément) mais pas sur treize (douze plus un).

Il supprime l'entrée finale, génère un tableau de références tableau, où les références tableau sont toutes les permutations, et ajoute le mot initial au début. Ensuite, il pousse chaque permutation sur une autre référence de tableau qui est la valeur d'un hachage avec la clé la quantité de tableau qui a la propriété de chaînage souhaitée. Il trouve ensuite le maximum de telles clés et imprime tous les tableaux.

C, 373 octets

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(" ; ");}

Je pense qu'il y a probablement beaucoup plus de golf que je pourrais faire ici, donc je vais probablement le mettre à jour.

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;
}

Lien Ideone - Si je ne l'ai pas fait correctement, faites le moi savoir: D