Kiedy byłem młodszy, grałem w grę słowną o nazwie Łańcuch słów . To było bardzo proste. Pierwszy gracz wybiera słowo; następny gracz mówi inne słowo, które zaczyna się od tej samej litery, którą kończyło poprzednie słowo. Trwa to wiecznie, dopóki ktoś się nie poddaje! Sztuczka polega na tym, że nie możesz użyć tego samego słowa dwa razy (chyba że wszyscy zapomnieli, że to słowo zostało użyte!). Zwykle gramy z pewnym tematem, aby było trudniej. Ale teraz chcę, żebyś stworzył program, aby to dla mnie zrobić.

Wyzwanie

Napisz pełny program lub funkcję, aby znaleźć jak najdłuższe łańcuchy słów, używając danego zestawu słów i rozpocznij słowo.

To jest kod-golf , więc wygrywa najkrótszy kod!

Wejście

Istnieją dwa dane wejściowe: lista i słowo początkowe. Słowa początkowego nie będzie na liście. Wszystkie dane wejściowe są małymi literami ASCII, a lista nie będzie zawierać zduplikowanych słów.

Wynik

Wszystkie sekwencje słów z listy takie, że:

• Słowo początkowe jest pierwszym słowem w sekwencji.

• Każde kolejne słowo zaczyna się od tej samej litery, co ostatnia litera poprzedniego słowa.

• Długość sekwencji jest najdłuższa z możliwych .

Jeśli istnieje wiele najdłuższych sekwencji, wyślij je wszystkie.

Sekwencja niekoniecznie musi zawierać wszystkie słowa z listy. Czasami nie jest to możliwe (patrz przypadki testowe). Znów żadne słowo nie może być użyte dwukrotnie!

Przypadki testowe

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 bajtów

.MlZfqhMtTeMPT+Lzs.pMyQ

Zestaw testowy

Rozwiązanie brutalnej siły. Zdecydowanie za wolny dla niektórych większych przypadków testowych.

Dane wejściowe w formularzu:

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

Dane wyjściowe w postaci:

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

Wyjaśnienie:

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

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

Wyjaśnienie

Funkcja rekurencyjna, która sprawdza, jak długo lista wyników będzie dostępna dla wszystkich możliwych wyborów.

Zwraca tablicę tablic słów.

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

Test

Domyślny parametr nieużywany w teście, aby uczynić go bardziej kompatybilnym z różnymi przeglądarkami.

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

Myślę, że powinno działać teraz ...

Wypróbuj online .

Perl 5, 275 bajtów

Prawdopodobnie nie grał w golfa tak bardzo, jak to możliwe, ale, hej, i tak nie wygrywa, prawda?

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

Użyj go w ten sposób:

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

Ostrzeżenie! Użycie tego skryptu na długiej liście wymaga dużej ilości pamięci! Działa świetnie dla mnie na siedem (sześć plus jeden dodatkowy), ale nie na trzynaście (dwanaście plus jeden).

Usuwa końcowe dane wejściowe, generuje tablicę tablic, w której tablice są wszystkimi permutacjami, i dodaje początkowe słowo z powrotem na początku. Następnie wypycha każdą taką permutację na inny odnośnik tablicowy, który jest wartością skrótu z kluczem, ilość tablicy, która ma pożądaną właściwość łączenia. Następnie wyszukuje maksimum takiego klucza i drukuje wszystkie tablice.

C, 373 bajtów

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

Sądzę, że mógłbym tutaj grać w golfa o wiele więcej, więc prawdopodobnie go zaktualizuję.

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

Link Ideone - jeśli nie zrobiłem tego dobrze, daj mi znać: D