Wprowadzenie

Popularną łamigłówką jest konwertowanie jednego słowa na drugie za pomocą serii kroków, które zastępują tylko jedną literę i które zawsze skutkują poprawnym słowem. Na przykład BAG można przekonwertować na DOG za pomocą ścieżki pięciu kroków:

TORBA -> BAT -> KOT -> COT -> COG -> DOG

W tym przypadku istnieją również krótsze ścieżki; na przykład:

TORBA -> BOG -> DOG

Gdyby narysować wykres, którego wierzchołki były oznaczone słowami, z krawędzią między dowolną parą słów, które różnią się jedną literą, wówczas najkrótsza ścieżka od „BAG” do „DOG” składałaby się z dwóch krawędzi.

Wyzwanie

Masz napisać program, który odbiera jako dane wejściowe „słownik” słów o tej samej długości, reprezentujących wszystkie dozwolone słowa, które mogą pojawiać się jako kroki wzdłuż ścieżki. Powinien generować co najmniej jedną „najdłuższą najkrótszą ścieżkę”, to znaczy ścieżkę między dwoma słowami, która jest:

• nie dłużej niż jakakolwiek inna ścieżka między tymi dwoma słowami;

• przynajmniej tak długo, jak najkrótsza możliwa ścieżka między dowolną inną parą słów na liście.

W kontekście wykresu opisanego powyżej długość takiej ścieżki jest średnicą wykresu.

W zdegenerowanym przypadku, gdy żadne ze słów wejściowych nie może zostać przekształcone w żadne z pozostałych, wypisz co najmniej jedną ścieżkę o długości zero, to znaczy jedno słowo.

Przykłady

• Dane wejściowe [„torba”, „nietoperz”, „kot”, „łóżeczko”, „kropka”, „pies”] powinny dać ścieżkę przechodzącą przez wszystkie sześć słów w tej kolejności (lub w odwrotnej kolejności), ponieważ najkrótsza ścieżka od „ torba „do” psa w tym słowniku to najdłuższy możliwy do osiągnięcia, pięć kroków.

• Dane wejściowe [„torba”, „nietoperz”, „bot”, „kot”, „łóżeczko”, „kropka”, „pies”] powinny dać ścieżkę „torba, nietoperz, bot, kropka, pies” i / lub jego odwrócenie.

• Dane wejściowe [„kod”, „golf”, „mężczyzna”, „buzz”, „kret”, „rola”, „pleśń”, „zimno”, „złoto”, „tryb”] powinny dać ścieżkę między „kodem” i „golf”.

• Dane wejściowe [„jeden”, „dwa”, „sześć”, „dziesięć”] odpowiadają wykresowi bez krawędzi, więc wypisz jedną lub więcej ścieżek zawierających jedno słowo (o zerowej długości).

• Jeśli dane wejściowe zawierają dowolne dwa słowa o nierównej długości, dane wyjściowe są niezdefiniowane.

Zasady

• Obowiązują standardowe zasady gry w golfa
• Będzie wiele „najkrótszych” ścieżek. Musisz wypisać co najmniej jeden, ale możesz wypisać tyle, ile chcesz.
• Możesz swobodnie decydować, w jaki sposób słownik wejściowy jest przekazywany do twojego programu.
• Najkrótszy kod w bajtach wygrywa.

Galaretka , 20 bajtów

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

Wypróbuj online!

APL (Dyalog Classic) , 84 80 77 76 74 66 61 bajtów

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

Wypróbuj online!

dane wejściowe i wyjściowe są matrycami znaków

⍵+.≠⍉⍵ macierz młotowatych odległości między słowami

9*⍨2⌊pozostaw nietknięte 0 i 1, zmień 2+ na dużą liczbę (512 = 2 ⁹ , używane jako „∞”)

⌊.+⍨⍣≡ Algorytm najkrótszej ścieżki floyda i warshalla

• ⌊.+jak mnożenie macierzy, ale za pomocą min( ⌊) i +zamiast +i ×odpowiednio

• ⍨ użyj tej samej matrycy po lewej i prawej stronie

• ⍣≡ powtarzaj aż do konwergencji

d←⌈/512|, długość najdłuższej (nie „∞”) ścieżki, przypisanej do d

⊃⍸a=które dwa węzły łączy, nazwijmy je i i j

{⍵,⍨⊃⍋(1≠a⌷⍨⊃⍵),⍪⍺⌷a}⍣d/ zrekonstruować ścieżkę

• { }⍣d/oceń czasy { }funkcji d. lewy argument ⍺to zawsze ja . prawy argument ⍵zaczyna się od j i stopniowo akumuluje wewnętrzne węzły ścieżki

• (1≠a⌷⍨⊃⍵),⍪⍺⌷a zbuduj 2-kolumnową macierz tych dwóch wektorów:

  • 1≠a⌷⍨⊃⍵ booleany (0 lub 1) wskazujące, które węzły znajdują się w odległości 1 od pierwszego z ⍵

  • ⍺⌷a odległości wszystkich węzłów wykresu do ⍺

• ⊃⍋ indeks najmniejszego leksykograficznie wiersza

• ⍵,⍨ przygotuj się na ⍵

⍵⌷⍨ indeksuj oryginalne słowa ze ścieżką

Python 3 , 225 bajtów

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]

Wypróbuj online!

Zasadniczo, weź wszystkie możliwe ścieżki, zachowaj tylko te, które są prawidłowe, a następnie przejdź przez każdą kombinację początkową, znajdź minimalną odległość ścieżki i znajdź jej maksimum.

Wolfram Language (Mathematica) , 105 bajtów

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

Wypróbuj online!

JavaScript (ES6),  195  194 bajtów

Powraca [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]

Wypróbuj online!

W jaki sposób?

$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]

(ten kod jest wykonywany przy każdej głębokości rekurencji, ale tak naprawdę ważny jest tylko poziom główny)

$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 bajty

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

Wypróbuj online!

Python 3, 228 bajtów.

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)

Implementuje algorytm Floyd-Warshall dla wszystkich par najkrótszych ścieżek, a następnie przejmuje maksimum ponad znalezione ścieżki.

16 znaków w tej implementacji to tabulatory, co jest niefortunne :(