Einführung

Ein beliebtes Worträtsel besteht darin, ein Wort in einer Reihe von Schritten in ein anderes umzuwandeln, die nur einen Buchstaben ersetzen und immer ein gültiges Wort ergeben. Beispielsweise kann BAG in fünf Schritten in DOG konvertiert werden:

TASCHE -> BAT -> CAT -> COT -> COG -> DOG

Auch hier gibt es kürzere Wege; beispielsweise:

TASCHE -> SOG -> HUND

Wenn man einen Graphen zeichnete, dessen Eckpunkte mit Wörtern beschriftet waren, mit einer Kante zwischen zwei Wörtern, die sich um einen Buchstaben unterscheiden, würde der kürzeste Weg von "BAG" zu "DOG" aus zwei Kanten bestehen.

Herausforderung

Sie müssen ein Programm schreiben, das als Eingabe ein "Wörterbuch" von Wörtern empfängt, die alle die gleiche Länge haben und alle zulässigen Wörter darstellen, die als Schritte entlang eines Pfades auftreten können. Es sollte mindestens einen "längsten kürzesten Pfad" ausgeben, d. H. Einen Pfad zwischen zwei der folgenden Wörter:

• nicht länger als irgendein anderer Weg zwischen diesen beiden Wörtern;

• mindestens so lang wie der kürzest mögliche Weg zwischen zwei anderen Wörtern in der Liste.

Im Zusammenhang mit dem oben beschriebenen Graphen ist die Länge eines solchen Pfades der Durchmesser des Graphen.

Geben Sie in dem entarteten Fall, in dem keines der Eingabewörter in eines der anderen umgewandelt werden kann, mindestens einen Pfad der Länge Null aus, d. H. Ein einzelnes Wort.

Beispiele

• Die Eingabe ["bag", "bat", "cat", "cot", "dot", "dog"] sollte einen Pfad ergeben, der alle sechs Wörter in dieser Reihenfolge (oder umgekehrter Reihenfolge) durchläuft, da der kürzeste Pfad von " bag "to" dog "in diesem Wörterbuch ist die längste erreichbare, fünf Schritte.

• Die Eingabe ["bag", "bat", "bot", "cat", "cot", "dot", "dog"] sollte den Pfad "bag, bat, bot, dot, dog" und / oder its ergeben Umkehrung.

• Die Eingabe ["code", "golf", "male", "buzz", "mole", "role", "mould", "cold", "gold", "mode"] sollte einen Pfad zwischen "code" ergeben und "Golf".

• Die Eingabe ["Eins", "Zwei", "Sechs", "Zehn"] entspricht einem Diagramm ohne Kanten. Geben Sie daher einen oder mehrere Einzelwortpfade (mit der Länge Null) aus.

• Wenn die Eingabe zwei Wörter ungleicher Länge enthält, ist die Ausgabe undefiniert.

Regeln

• Es gelten die Standard-Code-Golfregeln
• Es wird mehrere "kürzeste" Wege geben. Sie müssen mindestens eine ausgeben, können jedoch beliebig viele ausgeben.
• Sie können frei entscheiden, wie das Eingabewörterbuch in Ihr Programm übernommen wird.
• Kürzester Code in Bytes gewinnt.

Gelee , 20 Bytes

ŒPŒ!€ẎnƝ§ỊẠƲƇ.ịⱮḢƙƊṪ

Probieren Sie es online!

APL (Dyalog Classic) , 84 80 77 76 74 66 61 Bytes

{⍵⌷⍨{⍵,⍨⊃⍋(1≠a⌷⍨⊃⍵),⍪⍺⌷a}⍣d/⊃⍸a=d←⌈/512|,a←⌊.+⍨⍣≡9*⍨2⌊⍵+.≠⍉⍵}

Probieren Sie es online!

Eingabe und Ausgabe sind Zeichenmatrizen

⍵+.≠⍉⍵ Matrix von Hamming-ähnlichen Abständen zwischen Wörtern

9*⍨2⌊Lasse 0s und 1s intakt, verwandle 2+ in eine große Zahl (512 = 2 ⁹ , verwendet als "∞")

⌊.+⍨⍣≡ floyd & warshalls kürzester weg algorithm

• ⌊.+wie Matrizenmultiplikation jedoch unter Verwendung von min( ⌊) und +anstelle von +und ×jeweils

• ⍨ Verwenden Sie links und rechts dieselbe Matrix

• ⍣≡ Wiederholen Sie diesen Vorgang bis zur Konvergenz

d←⌈/512|, Länge des längsten (nicht "∞") Pfades, zugewiesen an d

⊃⍸a=Welche zwei Knoten verbindet es? Nennen wir sie i und j

{⍵,⍨⊃⍋(1≠a⌷⍨⊃⍵),⍪⍺⌷a}⍣d/ rekonstruiere den Pfad

• { }⍣d/die { }Funktionszeiten auswerten d. Das linke Argument ⍺ist immer i . Das rechte Argument ⍵beginnt mit j und akkumuliert allmählich die internen Knoten des Pfades

• (1≠a⌷⍨⊃⍵),⍪⍺⌷a Erstellen Sie eine 2-Spalten-Matrix aus diesen beiden Vektoren:

  • 1≠a⌷⍨⊃⍵ Boolesche Werte (0 oder 1), die angeben, welche Knoten sich im Abstand 1 zum ersten von befinden ⍵

  • ⍺⌷a Abstände aller Graphenknoten zu ⍺

• ⊃⍋ Index der lexikographisch kleinsten Zeile

• ⍵,⍨ voranstellen ⍵

⍵⌷⍨ Indizieren Sie die ursprünglichen Wörter mit dem Pfad

Python 3 , 225 Bytes

from itertools import*
def f(a):b=[((p[0],p[-1]),(len(p),p))for i in range(len(a))for p in permutations(a,i+1)if all(sum(q!=r for q,r in zip(*x))<2for x in zip(p,p[1:]))];return max(min(r for q,r in b if x==q)for x,y in b)[1]

Probieren Sie es online!

Nehmen Sie grundsätzlich alle möglichen Pfade, behalten Sie nur die gültigen bei, gehen Sie dann jede Start-Ende-Kombination durch, ermitteln Sie die minimale Pfadentfernung und ermitteln Sie das Maximum davon.

Wolfram Language (Mathematica) , 105 Byte

f@x_:=MaximalBy[AdjacencyGraph[x,UnitStep[1-DistanceMatrix@x]]~FindShortestPath~##&@@@Tuples[x,2],Length]

Probieren Sie es online!

JavaScript (ES6),  195 bis  194 Byte

Rückgabe [optimal_length, [optimal_path]].

f=(a,p=[],w=o=[],l=0)=>Object.values(o,o[k=[w,p[0]]]=(o[k]||0)[0]<l?o[k]:[l,p],a.map((v,i)=>w+w&&[...v].map((c,i)=>s-=c!=w[i],s=1)|s||f(a.filter(_=>i--),[...p,v],v,l+1))).sort(([a],[b])=>b-a)[0]

Probieren Sie es online!

Wie?

$f$$o$$w_0$$w_1$$[l, p]$$p$$w_0$$w_1$$l$

$p$$l$$w$$p$$o$

o[k = [w, p[0]]] = (o[k] || 0)[0] < l ? o[k] : [l, p]

$o$

Object.values(o).sort(([a], [b]) => b - a)[0]

(Dieser Code wird bei jeder Rekursionstiefe ausgeführt, aber nur die Root-Ebene ist wirklich von Bedeutung.)

$v$$w$

[...v].map((c, i) => s -= c != w[i], s = 1) | s

$v$

f(                    //
  a.filter(_ => i--), // remove the i-th word from a[]
  [...p, v],          // append v to p[]
  v,                  // pass v as the last word
  l + 1               // increment the length of the path
)                     //

Wolfram Language (Mathematica) , 92 Byte

MaximalBy[Select[Rule@@@a,EditDistance@@#<2&]~FindShortestPath~##&@@@(a=#~Tuples~2),Length]&

Probieren Sie es online!

Python 3, 228 Bytes.

def G(w):
    D={A+B:[A,B]if sum(a!=b for a,b in zip(A,B))<2else[0,0]*len(w)for A in w for B in w}
    for k in w:
        for i in w:
            for j in w:
                p=D[i+k]+D[k+j][1:]
                if len(p)<len(D[i+j]):D[i+j]=p
    return max(D.values(),key=len)

Implementiert den Floyd-Warshall-Algorithmus für die kürzesten Pfade aller Paare und nimmt dann das Maximum über die gefundenen Pfade.

16 der Zeichen in dieser Implementierung sind Registerkarten, was bedauerlich ist :(