Ketika saya masih muda, saya biasa memainkan permainan kata yang disebut rantai kata . Itu sangat sederhana. Pemain pertama memilih sebuah kata; pemain berikutnya mengatakan kata lain yang dimulai dengan huruf yang sama dengan kata sebelumnya berakhir. Ini berlangsung selamanya sampai seseorang menyerah! Triknya adalah, Anda tidak dapat menggunakan kata yang sama dua kali (kecuali semua orang lupa bahwa kata itu bahkan digunakan!). Biasanya kami bermain dengan topik tertentu untuk membuatnya lebih sulit. Tapi sekarang, saya ingin Anda membuat program untuk melakukan ini untuk saya.

Tantangan

Tulis program atau fungsi lengkap untuk menemukan semua rantai kata yang paling panjang menggunakan serangkaian kata dan mulai kata.

Ini kode-golf , jadi kode terpendek menang!

Memasukkan

Ada dua input: daftar dan kata awal. Kata awal tidak akan ada dalam daftar. Masukan semua huruf kecil ASCII, dan daftar tidak akan berisi kata-kata rangkap.

Keluaran

Semua urutan kata dari daftar sedemikian rupa sehingga:

• Kata awal adalah kata pertama dalam urutan.

• Setiap kata berikutnya dimulai dengan huruf yang sama dengan huruf terakhir dari kata sebelumnya.

• Panjang urutannya adalah yang terpanjang .

Jika ada beberapa urutan terpanjang, hasilkan semuanya.

Urutan tidak harus mengandung semua kata daftar. Terkadang itu tidak mungkin (lihat testcases). Sekali lagi, tidak ada kata yang dapat digunakan dua kali!

Testcases

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 byte

.MlZfqhMtTeMPT+Lzs.pMyQ

Suite uji

Solusi brute force. Terlalu lambat untuk beberapa kasus uji yang lebih besar.

Masukan dalam bentuk:

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

Output dalam bentuk:

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

Penjelasan:

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

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

Penjelasan

Fungsi rekursif yang memeriksa berapa lama daftar output akan untuk semua pilihan yang mungkin.

Mengembalikan array array kata.

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

Uji

Parameter default tidak digunakan dalam pengujian untuk membuatnya lebih kompatibel lintas-browser.

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

Saya pikir itu harus berfungsi sekarang ...

Cobalah online .

Perl 5, 275 byte

Mungkin tidak bermain golf sebanyak itu, tapi, hei, toh itu bukan kemenangan, kan?

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

Gunakan sebagai berikut:

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

Peringatan! Penggunaan skrip ini pada daftar panjang membutuhkan banyak memori! Ini bekerja sangat baik untuk saya pada tujuh (enam plus satu tambahan) tetapi tidak pada tiga belas (dua belas ditambah satu).

Ini menghapus input akhir, menghasilkan array dari arrayrefs, di mana arrayrefs adalah semua permutasi, dan menambahkan kata awal kembali di awal. Kemudian ia mendorong setiap permutasi seperti itu ke arrayref lain yang merupakan nilai hash dengan kunci jumlah array yang memiliki properti rantai yang diinginkan. Ia kemudian menemukan kunci maksimum seperti itu dan mencetak semua array.

C, 373 byte

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

Saya percaya mungkin ada lebih banyak golf yang bisa saya lakukan di sini jadi saya mungkin akan memperbaruinya.

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

Tautan ideone - Jika saya tidak melakukan ini dengan benar, beri tahu saya: D