Zostało to napisane w ramach First Periodic Premier Programming Puzzle Push .
Gra
Zapewnione jest słowo początkowe i końcowe o tej samej długości. Celem gry jest zmiana jednej litery w słowie początkowym, aby utworzyć inne prawidłowe słowo, powtarzanie tego kroku, aż do osiągnięcia słowa końcowego, przy użyciu jak najmniejszej liczby kroków. Na przykład, biorąc pod uwagę słowa TREE i FLED, wynikiem byłoby:
TREE
FREE
FLEE
FLED
2
Dane techniczne
- Artykuły w Wikipedii dotyczące OWL lub SOWPODS mogą być przydatnym punktem wyjścia do listy słów.
- Program powinien obsługiwać dwa sposoby wyboru słów początkowych i końcowych:
- Określony przez użytkownika za pomocą wiersza polecenia, standardowego wejścia lub innego odpowiedniego dla wybranego języka (wystarczy wspomnieć o tym, co robisz).
- Wybieranie losowo 2 słów z pliku.
- Słowa początkowe i końcowe, a także wszystkie słowa pośrednie powinny mieć tę samą długość.
- Każdy krok powinien być wydrukowany na linii.
- Ostatnim wierszem danych wyjściowych powinna być liczba kroków pośrednich wymaganych do przejścia między słowami początkowymi i końcowymi.
- Jeśli nie można znaleźć dopasowania między słowami początkowymi i końcowymi, wynik powinien składać się z 3 wierszy: słowa początkowego, słowa końcowego i słowa OY.
- W odpowiedzi umieść oznaczenie Big O dla swojego rozwiązania
- Dołącz 10 unikalnych par słów początkowych i końcowych (oczywiście z ich wynikiem), aby pokazać kroki, które wykonuje Twój program. (Aby zaoszczędzić miejsce, podczas gdy twój program powinien wypisywać je w poszczególnych wierszach, możesz skonsolidować je w jednym wierszu w celu opublikowania, zastępując nowe wiersze spacjami i przecinkiem między każdym uruchomieniem.
Cele / kryteria wygranej
- Zwycięży najszybsze / najlepsze rozwiązanie Big O zapewniające najkrótsze tymczasowe kroki po tygodniu.
- Jeśli remis wynika z kryteriów Big O, wygrywa najkrótszy kod.
- Jeśli nadal będzie remis, wygra pierwsze rozwiązanie, które umożliwi najszybszą i najkrótszą wersję.
Testy / Wyjście próbki
DIVE
DIME
DAME
NAME
2
PEACE
PLACE
PLATE
SLATE
2
HOUSE
HORSE
GORSE
GORGE
2
POLE
POSE
POST
PAST
FAST
3
Uprawomocnienie
Pracuję nad skryptem, którego można użyć do sprawdzenia poprawności danych wyjściowych.
To będzie:
- Upewnij się, że każde słowo jest poprawne.
- Upewnij się, że każde słowo różni się dokładnie o 1 literę od poprzedniego słowa.
Nie będzie:
- Sprawdź, czy zastosowano najmniejszą liczbę kroków.
Kiedy już to otrzymam, oczywiście zaktualizuję ten post. (:
code-challenge
word-puzzle
1p5
Rebecca Chernoff
źródło
źródło
HOUSE
do,GORGE
jest 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.The fastest/best Big O solution producing the shortest interim steps after one week will win.
Ponieważ nie możesz zagwarantować, że najszybszym rozwiązaniem jest w międzyczasie ten, który wykorzystuje najmniej kroków, powinieneś podać preferencję, jeśli jedno rozwiązanie używa mniejszej liczby kroków, ale osiągnie cel później.BAT
iCAT
mam zero kroków, prawda?Odpowiedzi:
Ponieważ długość jest podana jako kryterium, oto wersja golfowa z 1681 znakami (prawdopodobnie nadal mogłaby być poprawiona o 10%):
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:
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 znaczyO(filelength + V n^2 + E)
. Szczegółowe statystyki wykresów w SOWPODS oznaczają, żeO(V n^2)
naprawdę dominuje onoO(E)
dla większościn
.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.String
buforujęhashCode()
, więc całkowity czas spędzony na obliczaniu wartości skrótu wynosiO(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:
To
O(V * n * (n + hash) + E * hash)
. AleO(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:Następnie staje się pierwsza połowa generowania wykresu
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 jestO(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 toO(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)
naO(E * n * hash)
. Zobacz mój poprzedni punkt na temat statystyk.źródło
Jawa
Złożoność : ?? (Nie mam stopnia CompSci, więc byłbym wdzięczny za pomoc w tej sprawie.)
Wprowadzanie : Podaj parę słów (więcej niż 1 parę, jeśli chcesz) w wierszu polecenia. Jeśli nie podano linii poleceń, wybierane są 2 różne losowe słowa.
źródło
System.nanoTime()
.c na Uniksie
Korzystanie z algorytmu dijkstra.
Duża część kodu to kostiumowa implementacja drzewa n-ary, która służy do przechowywania
Ktoś ciekaw jak to działa prawdopodobnie powinien czytać
findPath
,process
orazprocessOne
(i związane z nimi komentarze). A możebuildPath
ibuildPartialPath
. Reszta to księgowość i rusztowania. Pozostało kilka procedur używanych podczas testowania i rozwoju, ale nie w wersji „produkcyjnej”.Używam
/usr/share/dict/words
na moim Mac OS 10.5 skrzynki, która ma tak wiele długich, ezoteryczne wpisy pozwalając działać całkowicie losowo generowanych jest wiele zOY
s.Niektóre dane wyjściowe:
Analiza złożoności jest nietrywialna. Poszukiwanie jest dwustronnym, iteracyjnym pogłębianiem.
W
.S_min = (<number of different letter>-1)
że jeśli dzieli nas tylko jedna litera, zmianę oceniamy na 0 kroków pośrednich. Maksymalny poziom jest trudny do oszacowania, patrz powyżej TRICKY - SWOOSH. Każda połowa drzewa będąS/2-1
doS/2
B
.Tak więc minimalna liczba operacji jest w pobliżu
2 * (S/2)^B * W
, niezbyt dobra.źródło
O(|V|+|E|)
zamiastO(|E|+|V| log |V|)
?