Zagraj w łańcuch słów

15

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 , 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]
TanMath
źródło
4
@ downvoters, czy możesz wyjaśnić, jak mogę poprawić swoje pytanie?
TanMath
@ user81655 na pewno
TanMath
2
Czy możesz dodać przypadek testowy z wieloma sekwencjami wyjściowymi?
isaacg
@isaacg Pewnie! nad tym pracuje
TanMath
@isaacg Dodano! (Limit 15 znaków spełniony ...)
TanMath

Odpowiedzi:

8

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.
isaacg
źródło
2
Czy możesz dodać wyjaśnienie?
TanMath,
Twój kod działa wiecznie dla przykładu sekwencji wielu wyjść
TanMath
3
@TanMath nie, to tylko wykładniczy czas, więc jest bardzo wolny.
isaacg
5
Code golf: Sztuka tworzenia skądinąd szybkiego programu uruchamianego w wykładniczym czasie, aby zaoszczędzić kilka bajtów: P
Arcturus
1
@RikerW Myślę, że warto też przypomnieć komentarz Martina z „Code Review: Making code nieco mniej nieprawidłowy / Code Golf: Making code nieco mniej długi” komentarz z czatu tutaj.
Arcturus
4

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.

użytkownik 81655
źródło
Myślę, że możesz użyć pop zamiast splice i o[r.length]?zamiast o.length>r.length?.
grc
@grc Dzięki, naprawdę podoba mi się o[r.length]wskazówka! Nie wiem jednak, jak mógłbym użyć pop.
user81655
Ah nvm - myślałem, że pop może wziąć indeks jako swój pierwszy argument jak w Pythonie.
grc
To rozwiązanie jest nieprawidłowe dla wielu sekwencji wyjściowych
TanMath
@TanMath Naprawiono, chociaż psuje jeden z przypadków testowych.
user81655
3

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 .

grc
źródło
1

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.

msh210
źródło
0

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

Danwakeem
źródło
czy możesz dodać link do ideone do testowania?
TanMath,
Tak, zaktualizuję swoją odpowiedź @TanMath
Danwakeem
Link powinien zawierać kod do gry w golfa, a nie wersję bez golfa. W ten sposób możemy potwierdzić wersję gry w golfa, którą przesyłasz do konkursu.
TanMath,