Ponieważ długość jest podana jako kryterium, oto wersja golfowa z 1681 znakami (prawdopodobnie nadal mogłaby być poprawiona o 10%):
import java.io.*;import java.util.*;public class W{public static void main(String[]
a)throws Exception{int n=a.length<1?5:a[0].length(),p,q;String f,t,l;S w=new S();Scanner
s=new Scanner(new
File("sowpods"));while(s.hasNext()){f=s.next();if(f.length()==n)w.add(f);}if(a.length<1){String[]x=w.toArray(new
String[0]);Random
r=new Random();q=x.length;p=r.nextInt(q);q=r.nextInt(q-1);f=x[p];t=x[p>q?q:q+1];}else{f=a[0];t=a[1];}H<S>
A=new H(),B=new H(),C=new H();for(String W:w){A.put(W,new
S());for(p=0;p<n;p++){char[]c=W.toCharArray();c[p]='.';l=new
String(c);A.get(W).add(l);S z=B.get(l);if(z==null)B.put(l,z=new
S());z.add(W);}}for(String W:A.keySet()){C.put(W,w=new S());for(String
L:A.get(W))for(String b:B.get(L))if(b!=W)w.add(b);}N m,o,ñ;H<N> N=new H();N.put(f,m=new
N(f,t));N.put(t,o=new N(t,t));m.k=0;N[]H=new
N[3];H[0]=m;p=H[0].h;while(0<1){if(H[0]==null){if(H[1]==H[2])break;H[0]=H[1];H[1]=H[2];H[2]=null;p++;continue;}if(p>=o.k-1)break;m=H[0];H[0]=m.x();if(H[0]==m)H[0]=null;for(String
v:C.get(m.s)){ñ=N.get(v);if(ñ==null)N.put(v,ñ=new N(v,t));if(m.k+1<ñ.k){if(ñ.k<ñ.I){q=ñ.k+ñ.h-p;N
Ñ=ñ.x();if(H[q]==ñ)H[q]=Ñ==ñ?null:Ñ;}ñ.b=m;ñ.k=m.k+1;q=ñ.k+ñ.h-p;if(H[q]==null)H[q]=ñ;else{ñ.n=H[q];ñ.p=ñ.n.p;ñ.n.p=ñ.p.n=ñ;}}}}if(o.b==null)System.out.println(f+"\n"+t+"\nOY");else{String[]P=new
String[o.k+2];P[o.k+1]=o.k-1+"";m=o;for(q=m.k;q>=0;q--){P[q]=m.s;m=m.b;}for(String
W:P)System.out.println(W);}}}class N{String s;int k,h,I=(1<<30)-1;N b,p,n;N(String S,String
d){s=S;for(k=0;k<d.length();k++)if(d.charAt(k)!=S.charAt(k))h++;k=I;p=n=this;}N
x(){N r=n;n.p=p;p.n=n;n=p=this;return r;}}class S extends HashSet<String>{}class H<V>extends
HashMap<String,V>{}
Wersja bez golfa, która używa nazw pakietów i metod i nie daje ostrzeżeń ani nie rozszerza klas tylko dla ich aliasu, to:
package com.akshor.pjt33;
import java.io.*;
import java.util.*;
// WordLadder partially golfed and with reduced dependencies
//
// Variables used in complexity analysis:
// n is the word length
// V is the number of words (vertex count of the graph)
// E is the number of edges
// hash is the cost of a hash insert / lookup - I will assume it's constant, but without completely brushing it under the carpet
public class WordLadder2
{
private Map<String, Set<String>> wordsToWords = new HashMap<String, Set<String>>();
// Initialisation cost: O(V * n * (n + hash) + E * hash)
private WordLadder2(Set<String> words)
{
Map<String, Set<String>> wordsToLinks = new HashMap<String, Set<String>>();
Map<String, Set<String>> linksToWords = new HashMap<String, Set<String>>();
// Cost: O(Vn * (n + hash))
for (String word : words)
{
// Cost: O(n*(n + hash))
for (int i = 0; i < word.length(); i++)
{
// Cost: O(n + hash)
char[] ch = word.toCharArray();
ch[i] = '.';
String link = new String(ch).intern();
add(wordsToLinks, word, link);
add(linksToWords, link, word);
}
}
// Cost: O(V * n * hash + E * hash)
for (Map.Entry<String, Set<String>> from : wordsToLinks.entrySet()) {
String src = from.getKey();
wordsToWords.put(src, new HashSet<String>());
for (String link : from.getValue()) {
Set<String> to = linksToWords.get(link);
for (String snk : to) {
// Note: equality test is safe here. Cost is O(hash)
if (snk != src) add(wordsToWords, src, snk);
}
}
}
}
public static void main(String[] args) throws IOException
{
// Cost: O(filelength + num_words * hash)
Map<Integer, Set<String>> wordsByLength = new HashMap<Integer, Set<String>>();
BufferedReader br = new BufferedReader(new FileReader("sowpods"), 8192);
String line;
while ((line = br.readLine()) != null) add(wordsByLength, line.length(), line);
if (args.length == 2) {
String from = args[0].toUpperCase();
String to = args[1].toUpperCase();
new WordLadder2(wordsByLength.get(from.length())).findPath(from, to);
}
else {
// 5-letter words are the most interesting.
String[] _5 = wordsByLength.get(5).toArray(new String[0]);
Random rnd = new Random();
int f = rnd.nextInt(_5.length), g = rnd.nextInt(_5.length - 1);
if (g >= f) g++;
new WordLadder2(wordsByLength.get(5)).findPath(_5[f], _5[g]);
}
}
// O(E * hash)
private void findPath(String start, String dest) {
Node startNode = new Node(start, dest);
startNode.cost = 0; startNode.backpointer = startNode;
Node endNode = new Node(dest, dest);
// Node lookup
Map<String, Node> nodes = new HashMap<String, Node>();
nodes.put(start, startNode);
nodes.put(dest, endNode);
// Heap
Node[] heap = new Node[3];
heap[0] = startNode;
int base = heap[0].heuristic;
// O(E * hash)
while (true) {
if (heap[0] == null) {
if (heap[1] == heap[2]) break;
heap[0] = heap[1]; heap[1] = heap[2]; heap[2] = null; base++;
continue;
}
// If the lowest cost isn't at least 1 less than the current cost for the destination,
// it can't improve the best path to the destination.
if (base >= endNode.cost - 1) break;
// Get the cheapest node from the heap.
Node v0 = heap[0];
heap[0] = v0.remove();
if (heap[0] == v0) heap[0] = null;
// Relax the edges from v0.
int g_v0 = v0.cost;
// O(hash * #neighbours)
for (String v1Str : wordsToWords.get(v0.key))
{
Node v1 = nodes.get(v1Str);
if (v1 == null) {
v1 = new Node(v1Str, dest);
nodes.put(v1Str, v1);
}
// If it's an improvement, use it.
if (g_v0 + 1 < v1.cost)
{
// Update the heap.
if (v1.cost < Node.INFINITY)
{
int bucket = v1.cost + v1.heuristic - base;
Node t = v1.remove();
if (heap[bucket] == v1) heap[bucket] = t == v1 ? null : t;
}
// Next update the backpointer and the costs map.
v1.backpointer = v0;
v1.cost = g_v0 + 1;
int bucket = v1.cost + v1.heuristic - base;
if (heap[bucket] == null) {
heap[bucket] = v1;
}
else {
v1.next = heap[bucket];
v1.prev = v1.next.prev;
v1.next.prev = v1.prev.next = v1;
}
}
}
}
if (endNode.backpointer == null) {
System.out.println(start);
System.out.println(dest);
System.out.println("OY");
}
else {
String[] path = new String[endNode.cost + 1];
Node t = endNode;
for (int i = t.cost; i >= 0; i--) {
path[i] = t.key;
t = t.backpointer;
}
for (String str : path) System.out.println(str);
System.out.println(path.length - 2);
}
}
private static <K, V> void add(Map<K, Set<V>> map, K key, V value) {
Set<V> vals = map.get(key);
if (vals == null) map.put(key, vals = new HashSet<V>());
vals.add(value);
}
private static class Node
{
public static int INFINITY = Integer.MAX_VALUE >> 1;
public String key;
public int cost;
public int heuristic;
public Node backpointer;
public Node prev = this;
public Node next = this;
public Node(String key, String dest) {
this.key = key;
cost = INFINITY;
for (int i = 0; i < dest.length(); i++) if (dest.charAt(i) != key.charAt(i)) heuristic++;
}
public Node remove() {
Node rv = next;
next.prev = prev;
prev.next = next;
next = prev = this;
return rv;
}
}
}
Jak widać, analiza kosztów bieżących jest O(filelength + num_words * hash + V * n * (n + hash) + E * hash). Jeśli zaakceptujesz moje założenie, że wstawianie / wyszukiwanie tablicy skrótów jest ciągłym czasem, to znaczy O(filelength + V n^2 + E). Szczegółowe statystyki wykresów w SOWPODS oznaczają, że O(V n^2)naprawdę dominuje ono O(E)dla większości n.
Przykładowe wyniki:
IDOLA, IDOLE, IDYLS, ODYLS, ODALS, OVALS, FOLIE, PIEKARNIKI, WIECZORY, ETENS, STENS, SKENS, SKÓRY, SPINY, KRĘGOSŁUP, 13
WICCA, PROSY, OY
BRINY, BRINS, TRINS, TAINS, TARNS, YARNS, YAWNS, YAWPS, YAPPS, 7
GALESY, GAZY, GASTY, GESTY, GESTE, GESSE, DESSE, 5
SURES, DURES, DUNES, DINES, DINGS, DINGY, 4
LICHT, LIGHT, BIGHT, BIGOT, BIGOS, BIROS, GIROS, GIRNS, GURNS, GUANS, GUANA, RUANA, 10
SARGE, SERGE, SERRE, SERRS, SEERS, DEERS, DYERS, OYERS, OVERS, OVELS, OVALS, ODALS, ODYLS, IDYLS, 12
KEIRY, SEIRS, SEERS, PIWA, BRERS, BRERE, BREME, CREME, CREPE, 7
Jest to jedna z 6 par o najdłuższej najkrótszej ścieżce:
GAINEST, FAINEST, FAIREST, SAIREST, SAIDEST, SADDEST, MADDEST, MIDDEST, MILDEST, WILDEST, WILIEST, WALIEST, WANIEST, CANIEST, CANTEST, KONKURS, KONFEST, CONFESS, CONFERS, CONKERS, KOOKERY, POPOPI, POPIERS, MIEDŹ MIESZANKI, MĄKI, POPSIE, MIĘSKI, MUZY, MUSZKI, MASY, PLUSZKI, MISZKI, PRASY, PRASY, PRÓBY, MOBILE, LĘKNIĘCIA, NIEPOKÓJ, NIEZBĘDNE, NIEZALEŻNE, NIEZBĘDNE, NIEZBĘDNE, NIEZMODNIONE, ZNOWIONE, ZNOWIONE, NIEDRODOWANE, ZAKOŃCZONE. INDEKSY, INDENE, INDENTACJE, INCENTY, INCESTY, INFESTY, INFEKTY, INIEKTY, 56
I jedna z najgorzej rozpuszczalnych 8-literowych par:
WYGŁADZANIE, ROZKŁADANIE, ROZKŁADANIE, ODKRYWANIE, ODKRYWANIE, ODKRYWANIE, ODKRYWANIE, WYGŁADZANIE, WYKRAWANIE, USUWANIE, USUWANIE, WYKŁADANIE, UTWORZANIE, WYKŁADANIE, OPRYSKIWANIE, MODLOWANIE, STROYING, STROKING, STUMK, ZESPÓŁ, STUMK ZACISKANIE, ZACISKANIE, CRISPINY, CRISPENS, CRISPERS, CRIMPERS, CRAMPERS, CLAMPERS, CLASPERS, CLASHERS, SLASHERS, SLATHERS, SLITHERS, SMITHERS, SMOTHERS, SOOTHERS, SOUTHERS, MOUTHERS, MOUCHERS PACHER, COACH LUNCHERY, LYNCHERY, LYNCHETY, LINCHETY, 52
Teraz, gdy wydaje mi się, że mam wszystkie wymagania pytania na bok, moja dyskusja.
W przypadku CompSci pytanie oczywiście sprowadza się do najkrótszej ścieżki na wykresie G, którego wierzchołki są słowami i których krawędzie łączą słowa różniące się jedną literą. Efektywne generowanie wykresu nie jest trywialne - mam pomysł, że muszę ponownie odwiedzić, aby zmniejszyć złożoność do O (Vn hash + E). Sposób, w jaki to robię, polega na utworzeniu wykresu, który wstawia dodatkowe wierzchołki (odpowiadające słowom z jednym znakiem wieloznacznym) i jest homeomorficzny dla danego wykresu. Zastanawiałem się nad użyciem tego wykresu zamiast zmniejszania do G - i przypuszczam, że z golfowego punktu widzenia powinienem to zrobić - na podstawie tego, że węzeł wieloznaczny z więcej niż 3 krawędziami zmniejsza liczbę krawędzi na wykresie, a standardowy najgorszy przypadek czasu działania algorytmów najkrótszej ścieżki to O(V heap-op + E).
Jednak pierwszą rzeczą, jaką zrobiłem, było przeprowadzenie analizy wykresów G dla różnych długości słów i odkryłem, że są one bardzo rzadkie dla słów o długości 5 lub więcej liter. 5-literowy wykres ma 12478 wierzchołków i 40759 krawędzi; dodanie węzłów łącza pogarsza wykres. Do czasu, gdy masz do 8 liter, jest mniej krawędzi niż węzłów, a 3/7 słów jest „na uboczu”. Odrzuciłem więc pomysł optymalizacji, ponieważ nie był zbyt pomocny.
Pomysł, który okazał się pomocny, to zbadanie stosu. Mogę szczerze powiedzieć, że w przeszłości stosowałem umiarkowanie egzotyczne sterty, ale żadne z nich nie było tak egzotyczne. Używam gwiazdki A (ponieważ C nie daje korzyści, biorąc pod uwagę stos, którego używam) z oczywistą heurystyką liczby liter różnych od celu, a trochę analizy pokazuje, że w dowolnym momencie nie ma więcej niż 3 różnych priorytetów w kupie. Kiedy wbijam węzeł, którego priorytetem jest (koszt + heurystyka) i patrzę na jego sąsiadów, rozważam trzy przypadki: 1) koszt sąsiada to koszt + 1; heurystyka sąsiada jest heurystyczna-1 (ponieważ zmieniana litera staje się „poprawna”); 2) koszt + 1 i heurystyka + 0 (ponieważ litera, którą zmienia, zmienia się z „zła” na „nadal zła”; 3) koszt + 1 i heurystyka + 1 (ponieważ litera, którą zmienia, zmienia się z „poprawna” na „zła”). Więc jeśli zrelaksuję sąsiada, wstawię go z tym samym priorytetem, priorytetem + 1 lub priorytetem + 2. W rezultacie mogę użyć 3-elementowej tablicy połączonych list dla sterty.
Powinienem dodać notatkę o moim założeniu, że wyszukiwania skrótów są stałe. Można powiedzieć, że dobrze, ale co z obliczeniami mieszania? Odpowiedź brzmi: amortyzuję je: java.lang.Stringbuforuję hashCode(), więc całkowity czas spędzony na obliczaniu wartości skrótu wynosi O(V n^2)(przy generowaniu wykresu).
Jest jeszcze jedna zmiana, która wpływa na złożoność, ale pytanie, czy jest to optymalizacja, czy nie, zależy od twoich założeń dotyczących statystyki. (IMO podając jako kryterium „najlepsze rozwiązanie Big O” jest błędem, ponieważ nie ma najlepszej złożoności z prostego powodu: nie ma jednej zmiennej). Ta zmiana wpływa na krok generowania wykresu. W powyższym kodzie jest to:
Map<String, Set<String>> wordsToLinks = new HashMap<String, Set<String>>();
Map<String, Set<String>> linksToWords = new HashMap<String, Set<String>>();
// Cost: O(Vn * (n + hash))
for (String word : words)
{
// Cost: O(n*(n + hash))
for (int i = 0; i < word.length(); i++)
{
// Cost: O(n + hash)
char[] ch = word.toCharArray();
ch[i] = '.';
String link = new String(ch).intern();
add(wordsToLinks, word, link);
add(linksToWords, link, word);
}
}
// Cost: O(V * n * hash + E * hash)
for (Map.Entry<String, Set<String>> from : wordsToLinks.entrySet()) {
String src = from.getKey();
wordsToWords.put(src, new HashSet<String>());
for (String link : from.getValue()) {
Set<String> to = linksToWords.get(link);
for (String snk : to) {
// Note: equality test is safe here. Cost is O(hash)
if (snk != src) add(wordsToWords, src, snk);
}
}
}
To O(V * n * (n + hash) + E * hash). Ale O(V * n^2)część pochodzi z wygenerowania nowego ciągu n-znaków dla każdego łącza, a następnie obliczenia jego kodu mieszającego. Można tego uniknąć dzięki klasie pomocniczej:
private static class Link
{
private String str;
private int hash;
private int missingIdx;
public Link(String str, int hash, int missingIdx) {
this.str = str;
this.hash = hash;
this.missingIdx = missingIdx;
}
@Override
public int hashCode() { return hash; }
@Override
public boolean equals(Object obj) {
Link l = (Link)obj; // Unsafe, but I know the contexts where I'm using this class...
if (this == l) return true; // Essential
if (hash != l.hash || missingIdx != l.missingIdx) return false;
for (int i = 0; i < str.length(); i++) {
if (i != missingIdx && str.charAt(i) != l.str.charAt(i)) return false;
}
return true;
}
}
Następnie staje się pierwsza połowa generowania wykresu
Map<String, Set<Link>> wordsToLinks = new HashMap<String, Set<Link>>();
Map<Link, Set<String>> linksToWords = new HashMap<Link, Set<String>>();
// Cost: O(V * n * hash)
for (String word : words)
{
// apidoc: The hash code for a String object is computed as
// s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
// Cost: O(n * hash)
int hashCode = word.hashCode();
int pow = 1;
for (int j = word.length() - 1; j >= 0; j--) {
Link link = new Link(word, hashCode - word.charAt(j) * pow, j);
add(wordsToLinks, word, link);
add(linksToWords, link, word);
pow *= 31;
}
}
Korzystając ze struktury skrótu, możemy wygenerować linki O(V * n). Ma to jednak efekt domina. Nieodłącznym elementem mojego założenia, że wyszukiwania skrótów są ciągłe, jest założenie, że porównywanie obiektów pod kątem równości jest tanie. Jednak test równości Link jest O(n)w najgorszym przypadku. Najgorszym przypadkiem jest zderzenie mieszające między dwoma równymi linkami wygenerowanymi z różnych słów - tj. Występuje to O(E)w drugiej połowie generowania wykresu. Poza tym, z wyjątkiem mało prawdopodobnego przypadku kolizji skrótu między nierównymi linkami, jesteśmy dobrzy. Więc wymieniliśmy się O(V * n^2)na O(E * n * hash). Zobacz mój poprzedni punkt na temat statystyk.
HOUSEdo,GORGEjest zgłaszane jako 2. Zdaję sobie sprawę, że są 2 pośrednie słowa, więc ma to sens, ale # operacji byłoby bardziej intuicyjne.