tło

Trzy lata temu ten facet Tom Murphy wpadł mu do głowy, aby rozszerzyć ideę portmanteau na wszystkie słowa w języku i nazwał to portmantout ( portmanteau plus tout [francuski dla wszystkich ]). Definiując angielski jako listę 108 709 słów, udało mu się znaleźć sekwencję 611,820 liter o następujących dwóch właściwościach:

• Każde angielskie słowo jest zawarte w ciągu.
• Niektóre sąsiedztwo zawierające dowolne dwie sąsiadujące litery w ciągu to słowo angielskie.

Oto link do strony, na której można znaleźć ten portmantout (wraz z objaśnieniem wideo).

Portmantout

Pierwsza z dwóch właściwości portmantout jest łatwa do zrozumienia. Drugi może wymagać wyjaśnienia.

Zasadniczo słowa muszą się pokrywać. „golfcode” nigdy nie pojawi się w angielskiej wersji językowej, ponieważ nie ma tam słowa zawierającego „fc”. Jednak możesz znaleźć „codegolf” w portmantout, ponieważ „ego” wypełnia lukę (a wszystkie inne pary liter są w „kodzie” lub „golfie”).

Twoje zadanie:

Napisz program lub funkcję, która pobiera listę ciągów znaków i zwraca dowolny portmantout listy.

Ten kod Python 3 zweryfikuje portmantout.

Przypadki testowe

Wszystkie listy są nieuporządkowane; to jest,

{"code", "ego", "golf"} -> "codegolf"
{"more", "elm", "maniac"} -> "morelmaniac" or "morelmorelmaniac" or "morelmorelmorelmaniac" or...
    Would a morelmaniac be some sort of mycologist?
{"ab", "bc", "cd", "de", "ef", "fg", "gh", "hi", "ij", "jk", "kl", "lm", "mn", "no", "op", "pq", "qr", "rs", "st", "tu", "uv", "vw", "wx", "xy", "yz", "za"} -> "abcdefghijklmnopqrstuvwxyza" or "rstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" or any 27+ letters in order

Czemu nie? Ogromny na stronie Murphy'ego, jeśli kod zostanie wykonany w rozsądnym czasie.

Zasady

• Twój kod musi zostać zatrzymany.
• Nie musisz zwracać tego samego portmantout przy każdym wykonaniu.
• Możesz założyć wszystkie ciągi składać się tylko z małych liter apoprzez z.
• Jeśli żaden portmantout nie jest możliwy, twój program może zrobić wszystko. Dawny:{"most", "short", "lists"}
• Obowiązują standardowe zasady we / wy i luki .

To jest golf golfowy , więc wygrywa najkrótsze rozwiązanie (w bajtach) w każdym języku! Miłej gry w golfa!

Python 2 , 204 202 bajty

def f(l,s=''):
 if all(w in s for w in l):return s
 for i,w in enumerate(l):
	a=next((s+w[i:]for i in range(len(w)-1,0,-1)if s[-i:]==w[:i]),0)if s else w;x=a and f(l[:i]+l[i+1:]+[l[i]],a)
	if x:return x

Wypróbuj online!

Zapisano

• -2 bajty, dzięki rekurencyjnemu

Pyth, 39 bajtów

JQW}_1mxbdQ=+J|=b*qKOQ<=T+OP._KOJlKTY)b

Wypróbuj tutaj

Wyjaśnienie

JQW}_1mxbdQ=+J|=b*qKOQ<=T+OP._KOJlKTY)b
JQ                                        Get a copy of the input.
  W}_1mxbdQ                          )    While there are words in the input
                                          that aren't in b (initially space)...
                   KOQ    OP._KOJ         ... get a random input word, a random
                                          prefix, and a random joined word...
                       =T+                ... stick them together...
                  q   <          lKT      ... and check if joining them together
                                          is valid...
               =b*                        ... then update b accordingly...
           =+J|                     Y     ... and stick the new word into J.
                                      b   Output the final result.

Stax , 39 36 bajtów

ä▬│•.k=╠lƒ☺╜00║¿~,▓╕╠7ÉΔB<e┼>☼Θ²└ô┴\

Uruchom i debuguj

Uruchamia wszystkie przypadki testowe deterministycznie w około sekundę.

Jest to algorytm rekurencyjny.

• Zacznij od każdego słowa wejściowego jako kandydata
• Na każdym kroku uporządkuj słowa według liczby wystąpień jako podciągów kandydata.
• Dla każdego słowa zgodnego z końcem bieżącego kandydata dołącz do niego, aby utworzyć nowego kandydata i nawiąż połączenie rekurencyjne.

Oto program rozpakowany, nieposortowany i skomentowany.

FG              for each word in input, call target block
}               unbalanced closing brace represents call target
  x{[#o         sort input words by their number of occurrences in the current candidate
  Y             store it in register Y
  h[#{,}M       if all of the words occur at least once, pop from input stack
                input stack is empty, so this causes immediate termination,
                followed by implicitly printing the top of the main stack
  yF            for each word in register y, do the following
    [n|]_1T|[|& intersect the suffixes of the candidate with prefixes of the current word
    z]+h        get the first fragment in the intersection, or a blank array
    Y           store it in register Y
    %t+         join the candidate with the current word, eliminating the duplicate fragment
    y{G}M       if the fragment was non-blank, recursively call to the call target
    d           pop the top of stack

Uruchom ten

Edycja: Nie udaje się to w przypadku klasy wejść z pętlą, podobnie ["ab", "ba", "ca"]jak większość innych opublikowanych odpowiedzi.

JavaScript (ES6), 138 130 bajtów

f=a=>a[1]?a.map((c,i)=>a.map((w,j,[...b])=>i!=j&&!/0/.test(m=(c+0+w).split(/(.+)0\1/).join``)?t=f(b,b[i]=m,b.splice(j,1)):0))&&t:a

Zwraca błąd dla list, których nie można całkowicie ukryć.

Nie golfowany:

f = a =>
  a[1] ?                                        //if more than one element ...
    a.map((c, i)=>                              // for each element
      a.map((w, j, [...b])=>                    //  for each element
        i != j &&                               //   if not the same element
        !/0/.test(m=(c+0+w).split(/(.+)0\1/).join``) &&  //   and the elements overlap
        (t = f(b,                               //   and f recursed is true when
               b[i] = m,    //    replacing the ith element with the 2-element portmanteau
               b.splice(j, 1)                   //    and removing the jth element
              )
        )
      )
    ) &&
    t :                                         //return the recursed function value
    a                                           //else return a

f=a=>a[1]?a.map((c,i)=>a.map((w,j,[...b])=>i!=j&&!/0/.test(m=(c+0+w).split(/(.+)0\1/).join``)?t=f(b,b[i]=m,b.splice(j,1)):0))&&t:a

console.log(f(["sic", "bar", "rabbits", "cradle"])+'')             // "barabbitsicradle"
console.log(f(["mauve", "elated", "cast", "electric", "tame"])+'') // "mauvelectricastamelated"

console.log(f(["more", "elm", "maniac"])+'')                       // "morelmaniac"
console.log(f(["elm", "more", "maniac"])+'')                       // "morelmaniac"
console.log(f(["more", "maniac", "elm"])+'')                       // "morelmaniac"

console.log(f(["ego", "code", "golf"])+'')                         // "codegolf"
console.log(f(["code", "ego", "golf"])+'')                         // "codegolf"
console.log(f(["golf", "ego", "code"])+'')                         // "codegolf"

console.log(f(['ab', 'bc', 'cd', 'de'])+'');                       // "abcde"
console.log(f(['de', 'bc', 'cd', 'ab'])+'');                       // "abcde"

console.log(f(["ab", "ba", "ca"])+'');                             // "caba"

Kod jest rozdzierająco powolny na pełnym przykładzie alfabetu (z tego powodu nie został uwzględniony w powyższym fragmencie).

Można temu zaradzić, zmieniając maps na somes, dla utraty 2 bajtów:

f=a=>a[1]?a.some((c,i)=>a.((w,j,[...b])=>i!=j&&!/0/.test(m=(c+0+w).split(/(.+)0\1/).join``)?t=f(b,b[i]=m,b.splice(j,1)):0))&&t:a

f=a=>a[1]?a.some((c,i)=>a.some((w,j,[...b])=>i!=j&&!/0/.test(m=(c+0+w).split(/(.+)0\1/).join``)?t=f(b,b[i]=m,b.splice(j,1)):0))&&t:a

console.log(f(["ab", "bc", "cd", "de", "ef", "fg", "gh", "hi", "ij", "jk", "kl", "lm", "mn", "no", "op", "pq", "qr", "rs", "st", "tu", "uv", "vw", "wx", "xy", "yz", "za"])+'');

console.log(f(["ab", "ba", "ca"])+'');                             // "caba"