Hintergrund

Vor drei Jahren hatte sich der Typ Tom Murphy vorgenommen , die Idee eines Portmanteaus auf alle Wörter einer Sprache auszudehnen und nannte dies Portmantout ( Portmanteau plus tout [Französisch für alle ]). Er definierte Englisch als Liste von 108.709 Wörtern und fand eine Folge von 611.820 Buchstaben mit den folgenden zwei Eigenschaften:

• Jedes englische Wort ist in der Zeichenfolge enthalten.
• Eine Nachbarschaft, die zwei benachbarte Buchstaben in der Zeichenfolge enthält, ist ein englisches Wort.

Hier ist ein Link zu einer Seite, auf der dieses Portmantout zu finden ist (zusammen mit einer Videoerklärung).

Ein Portmantout

Die erste der beiden Eigenschaften eines Portmantouts ist leicht zu verstehen. Die zweite kann eine Erklärung erfordern.

Grundsätzlich müssen sich Wörter überlappen. "golfcode" wird niemals in einem englischen Portmantout erscheinen, da es dort kein Wort gibt, das das "fc" enthält. Es kann jedoch vorkommen, dass Sie in einem Portmantout "Codegolf" finden, denn "Ego" überbrückt die Lücke (und alle anderen Buchstabenpaare sind entweder in "Code" oder "Golf" enthalten).

Deine Aufgabe:

Schreiben Sie ein Programm oder eine Funktion, die eine Liste von Zeichenfolgen aufnimmt und einen beliebigen Portmantout der Liste zurückgibt.

Dieser Python 3-Code überprüft einen Portmantout.

Testfälle

Alle Listen sind ungeordnet. das ist,

{"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

Und warum nicht? Die massive auf Murphys Website, wenn Ihr Code innerhalb angemessener Zeit ausgeführt wird.

Regeln

• Ihr Code muss anhalten.
• Sie müssen nicht bei jeder Ausführung dasselbe Portmantout zurückgeben.
• Sie können alle Saiten bestehen aus nur Kleinbuchstaben annehmen adurch z.
• Wenn kein Portmantout möglich ist, kann Ihr Programm alles tun. Ex:{"most", "short", "lists"}
• Es gelten die Standardregeln für E / A und Lücken .

Das ist Code-Golf , also gewinnt die kürzeste Lösung (in Bytes) in jeder Sprache! Viel Spaß beim Golfen!

Python 2 , 204 202 Bytes

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

Probieren Sie es online!

Gerettet

• -2 Bytes dank rekursiv

Pyth, 39 Bytes

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

Probieren Sie es hier aus

Erläuterung

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 Bytes

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

Führen Sie es aus und debuggen Sie es

Führt alle Testfälle deterministisch in ungefähr einer Sekunde aus.

Dies ist ein rekursiver Algorithmus.

• Beginnen Sie mit jedem eingegebenen Wort als Kandidat
• Ordnen Sie die Wörter bei jedem Schritt nach der Häufigkeit, mit der sie als Teilzeichenfolgen des Kandidaten vorkommen.
• Verbinden Sie für jedes Wort, das mit dem Ende des aktuellen Kandidaten kompatibel ist, das Wort, um einen neuen Kandidaten zu bilden, und führen Sie einen rekursiven Aufruf durch.

Hier ist das Programm entpackt, ungolfed und kommentiert.

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

Führen Sie dieses aus

Bearbeiten: Dies schlägt für eine Klasse von Eingaben fehl ["ab", "ba", "ca"], die wie die meisten anderen geposteten Antworten eine Schleife aufweist .

JavaScript (ES6), 138 - 130 Byte

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

Gibt einen Fehler für Listen zurück, die nicht vollständig portiert werden können.

Ungolfed:

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"

Der Code ist im vollständigen Alphabet-Beispiel unglaublich langsam (aus diesem Grund nicht im obigen Snippet enthalten).

Dies wird durch Ändern von maps in somes für den Verlust von 2 Bytes behoben :

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"