Ostatnio gram na telefonie iPhone grę Scramble. Niektórzy z was mogą znać tę grę jako Boggle. Zasadniczo, gdy gra się rozpoczyna, otrzymujesz macierz takich liter:
F X I E
A M L O
E W B X
A S T U
Celem gry jest znalezienie jak największej liczby słów, które można utworzyć, łącząc ze sobą litery. Możesz zacząć od dowolnej litery, a wszystkie otaczające ją litery są uczciwą grą, a następnie, po przejściu do następnej litery, wszystkie litery otaczające tę literę są uczciwe, z wyjątkiem wcześniej używanych liter . Więc w siatce powyżej, na przykład, mogę wymyślić słów LOB
, TUX
, SEA
, FAME
, itd. Słowa muszą mieć co najmniej 3 znaki i nie więcej niż znaków NxN, co byłoby 16 w tej grze, ale mogą się różnić w niektórych implementacjach . Chociaż ta gra jest zabawna i wciągająca, najwyraźniej nie jestem w tym zbyt dobry i chciałem trochę oszukać, tworząc program, który dałby mi najlepsze możliwe słowa (im dłuższe słowo, tym więcej punktów otrzymasz).
(źródło: boggled.org )
Niestety nie jestem zbyt dobry w algorytmach, ich wydajności i tak dalej. Moja pierwsza próba wykorzystuje słownik taki jak ten (~ 2,3 MB) i wykonuje wyszukiwanie liniowe, próbując dopasować kombinacje do pozycji słownika. Znalezienie możliwych słów zajmuje bardzo dużo czasu, a ponieważ masz tylko 2 minuty na rundę, jest to po prostu nieodpowiednie.
Interesuje mnie, czy którykolwiek Stackoverflowers może wymyślić bardziej wydajne rozwiązania. Głównie szukam rozwiązań wykorzystujących Big 3 Ps: Python, PHP i Perl, chociaż wszystko w Javie lub C ++ też jest fajne, ponieważ szybkość jest niezbędna.
AKTUALNE ROZWIĄZANIA :
- Adam Rosenfield, Python, ~ 20s
- John Fouhy, Python, ~ 3s
- Kent Fredric, Perl, ~ 1s
- Darius Bacon, Python, ~ 1s
- rvarcher, VB.NET (link na żywo) , ~ 1s
- Paolo Bergantino, PHP (link na żywo) , ~ 5s (~ 2s lokalnie)
Odpowiedzi:
Moja odpowiedź działa podobnie jak inne tutaj, ale opublikuję ją, ponieważ wygląda na to, że wygląda trochę szybciej niż inne rozwiązania Python, od szybszego konfigurowania słownika. (Sprawdziłem to z rozwiązaniem Johna Fouhy.) Po ustawieniu czas na rozwiązanie jest coraz niższy.
Przykładowe użycie:
Edycja: odfiltruj słowa o długości mniejszej niż 3 litery.
Edycja 2: Byłem ciekawy, dlaczego rozwiązanie Perla Kenta Fredrica było szybsze; okazuje się, że używa zestawu dopasowań wyrażeń regularnych zamiast zestawu znaków. Robiąc to samo w Pythonie, podwajając prędkość.
źródło
def neighbors((x, y))
(bezcelowo, o ile widzę). Wymaga także nawiasów wokół argumentu doprint
.Najszybszym rozwiązaniem, jakie otrzymasz, będzie prawdopodobnie przechowywanie słownika w wersji próbnej . Następnie należy utworzyć kolejkę tripletów ( x , y , y ), gdzie każdy element kolejka odpowiada prefiks s słowem, które mogą być podane w siatce, kończąc w miejscu ( x , y ). Zainicjuj kolejkę za pomocą N x N elementów (gdzie N jest rozmiarem twojej siatki), po jednym elemencie na każdy kwadrat w siatce. Następnie algorytm działa w następujący sposób:
Jeśli przechowujesz słownik w trie, sprawdzanie, czy s + c jest słowem lub przedrostkiem słowa, można wykonać w stałym czasie (pod warunkiem, że zachowasz również dodatkowe metadane w każdej bazie danych kolejki, takie jak wskaźnik do bieżącego węzła w trie), więc czas działania tego algorytmu wynosi O (liczba słów, które można przeliterować).
[Edytuj] Oto implementacja w Pythonie, którą właśnie kodowałem:
Przykładowe użycie:
Wynik:
Uwagi: Ten program nie wyświetla słów 1-literowych ani nie filtruje według długości słów. Jest to łatwe do dodania, ale nie bardzo istotne dla problemu. Wysyła również kilka słów kilka razy, jeśli można je przeliterować na wiele sposobów. Jeśli dane słowo można przeliterować na wiele różnych sposobów (najgorszy przypadek: każda litera w siatce jest taka sama (np. „A”), a słowo takie jak „aaaaaaaaaa” znajduje się w słowniku), czas wykonywania będzie strasznie wykładniczy . Filtrowanie duplikatów i sortowanie jest trywialne, ponieważ po zakończeniu algorytmu.
źródło
(x,y)
, możliwym naśladowcą jest(x+1,y+1)
. Następnie(x+1,y+1)
jest wypychany do kolejki. Jednak(x,y)
również będzie zwolennikiem(x+1,y+1)
, więc czy to nie doprowadzi do niekończącego się odbicia między nimi?W celu przyspieszenia słownika istnieje jedna ogólna transformacja / proces, który możesz zrobić, aby znacznie wcześniej ograniczyć porównania słowników.
Biorąc pod uwagę, że powyższa siatka zawiera tylko 16 znaków, niektóre z nich są zduplikowane, możesz znacznie zmniejszyć całkowitą liczbę kluczy w słowniku, po prostu odfiltrowując wpisy zawierające nieosiągalne znaki.
Myślałem, że to oczywista optymalizacja, ale widząc, że nikt tego nie zrobił, wspominam o tym.
Zmniejszyło mnie to ze słownika 200 000 kluczy do zaledwie 2000 kluczy podczas samego wprowadzania. To przynajmniej zmniejsza obciążenie pamięci, a to z pewnością odwzoruje gdzieś wzrost prędkości, ponieważ pamięć nie jest nieskończenie szybka.
Implementacja Perla
Moja implementacja jest nieco trudniejsza, ponieważ przywiązałem dużą wagę do znajomości dokładnej ścieżki każdego wyodrębnionego łańcucha, a nie tylko jego ważności.
Mam też kilka adaptacji, które teoretycznie pozwolą na funkcjonowanie siatki z dziurami i siatek z liniami o różnych rozmiarach (zakładając, że poprawnie wprowadzasz dane wejściowe i jakoś się wyrównuje).
Wczesne filtr jest zdecydowanie najbardziej znaczącym wąskie gardło w mojej aplikacji, jak podejrzewał wcześniej, komentując, że bloats linii go od 1.5s do 7.5s.
Po wykonaniu wydaje się, że wszystkie pojedyncze cyfry mają własne poprawne słowa, ale jestem pewien, że wynika to ze sposobu działania pliku słownika.
Jest nieco rozdęty, ale przynajmniej ponownie używam Tree :: Trie z cpan
Niektóre z nich zostały częściowo zainspirowane istniejącymi implementacjami, niektóre z nich już miałem na myśli.
Konstruktywny krytycyzm i sposoby, w jakie można go poprawić, mile widziane (/ zauważa, że nigdy nie szukał CPAN w poszukiwaniu rozwikłanego solwera , ale wypracowanie go było przyjemniejsze)
zaktualizowane o nowe kryteria
Informacje o łuku / wykonaniu do porównania:
Więcej bełkotów na temat optymalizacji regex
Optymalizacja wyrażeń regularnych, której używam, jest bezużyteczna dla słowników z wieloma rozwiązaniami, a dla wielu rozwiązań będziesz potrzebować pełnego słownika, a nie wstępnie przyciętego.
Jednak to powiedziawszy, dla jednorazowych rozwiązań, jest naprawdę szybkie. (Wyrażenia regularne Perla są w C! :))
Oto kilka różnych dodatków kodu:
ps: 8,16 * 200 = 27 minut.
źródło
Możesz podzielić problem na dwie części:
Najlepiej byłoby, gdyby (2) zawierał także sposób sprawdzenia, czy łańcuch jest prefiksem prawidłowego słowa - pozwoli to na przycięcie wyszukiwania i zaoszczędzi całą masę czasu.
Trie Adama Rosenfielda to rozwiązanie (2). Jest elegancki i prawdopodobnie preferowany przez specjalistę od algorytmów, ale dzięki nowoczesnym językom i nowoczesnym komputerom możemy być nieco leniwi. Ponadto, jak sugeruje Kent, możemy zmniejszyć rozmiar naszego słownika, odrzucając słowa, których litery nie występują w siatce. Oto kilka python:
Łał; testowanie prefiksu w czasie stałym. Załadowanie połączonego słownika zajmuje kilka sekund, ale tylko kilka :-) (zauważ, że
words <= prefixes
)Teraz, w części (1), jestem skłonny myśleć w kategoriach grafów. Zbuduję słownik, który wygląda mniej więcej tak:
tj.
graph[(x, y)]
jest to zestaw współrzędnych, do których można dotrzeć z pozycji(x, y)
. Dodam również fikcyjny węzeł,None
który połączy się ze wszystkim.Budowanie jest trochę niezdarne, ponieważ istnieje 8 możliwych pozycji i musisz sprawdzić granice. Oto odpowiednio nieporadny kod python:
Ten kod tworzy także mapowanie słownika
(x,y)
na odpowiedni znak. To pozwala mi zamienić listę pozycji w słowo:Na koniec przeprowadzamy wyszukiwanie dogłębne. Podstawowa procedura to:
Pyton:
Uruchom kod jako:
i sprawdź,
res
aby zobaczyć odpowiedzi. Oto lista słów znalezionych dla Twojego przykładu, posortowanych według rozmiaru:Ładowanie kodu zajmuje (dosłownie) kilka sekund, ale reszta jest natychmiastowa na moim komputerze.
źródło
range(len(w)+1)
zamiastrange(len(w))
. Twierdziłem, żewords <= prefixes
ale najwyraźniej nie testowałem tego: - /Moja próba w Javie. Odczytanie pliku i zbudowanie trie zajmuje około 2 sekund, a rozwiązanie zagadki około 50 ms. Użyłem słownika podanego w pytaniu (zawiera kilka słów, których nie znałem w języku angielskim, takich jak fae, ima)
Kod źródłowy składa się z 6 klas. Zamieszczę je poniżej (jeśli nie jest to właściwa praktyka na StackOverflow, proszę powiedz mi).
gineer.bogglesolver.Main
gineer.bogglesolver.Solver
gineer.bogglesolver.trie.Node
gineer.bogglesolver.trie.Trie
gineer.bogglesolver.util.Constants
gineer.bogglesolver.util.Util
źródło
Myślę, że prawdopodobnie poświęcisz większość czasu na dopasowanie słów, których nie można zbudować za pomocą siatki listów. Pierwszą rzeczą, którą chciałbym zrobić, jest przyspieszenie tego kroku, co powinno zapewnić ci większość możliwości.
W tym celu ponownie wyraziłbym siatkę jako tabelę możliwych „ruchów”, które indeksujesz według literowanego przejścia, na które patrzysz.
Zacznij od przypisania każdej literze numeru z całego alfabetu (A = 0, B = 1, C = 2, ... itd.).
Weźmy ten przykład:
I na razie, użyjmy alfabetu liter, które mamy (zwykle prawdopodobnie za każdym razem będziesz chciał używać tego samego alfabetu):
Następnie tworzysz tablicę boolowską 2D, która informuje, czy dostępne jest pewne przejście literowe:
Teraz przejrzyj listę słów i przekonwertuj słowa na przejścia:
Następnie sprawdź, czy te przejścia są dozwolone, sprawdzając je w tabeli:
Jeśli wszystkie są dozwolone, istnieje szansa, że to słowo zostanie odnalezione.
Na przykład słowo „kask” można wykluczyć przy 4. przejściu (m do e: helMEt), ponieważ ten wpis w tabeli jest fałszywy.
I słowo chomik można wykluczyć, ponieważ pierwsze przejście (h do a) jest niedozwolone (nawet nie istnieje w twojej tabeli).
Teraz, dla prawdopodobnie niewielu pozostałych słów, których nie wyeliminowałeś, spróbuj znaleźć je w siatce w sposób, w jaki to robisz teraz lub jak sugerowano w niektórych innych odpowiedziach tutaj. Ma to na celu uniknięcie fałszywych trafień wynikających ze skoków między identycznymi literami w siatce. Na przykład słowo „pomoc” jest dozwolone w tabeli, ale nie w siatce.
Kilka dalszych wskazówek dotyczących poprawy wydajności tego pomysłu:
Zamiast korzystać z tablicy 2D, użyj tablicy 1D i po prostu sam oblicz indeks drugiej litery. Tak więc zamiast tablicy 12x12 jak powyżej, utwórz tablicę 1D o długości 144. Jeśli zawsze będziesz używać tego samego alfabetu (tj. Tablicy 26x26 = 676x1 dla standardowego alfabetu angielskiego), nawet jeśli nie wszystkie litery pojawiają się na twojej siatce , możesz wstępnie obliczyć indeksy do tej tablicy 1D, którą musisz przetestować, aby dopasować słowa ze słownika. Na przykład, wskaźniki dla „cześć” w powyższym przykładzie byłyby
Rozszerz pomysł na tabelę 3D (wyrażoną jako tablica 1D), tzn. Wszystkie dozwolone kombinacje 3-literowe. W ten sposób możesz natychmiast wyeliminować jeszcze więcej słów i zmniejszyć liczbę wyszukiwań tablicowych dla każdego słowa o 1: Aby „cześć”, potrzebujesz tylko 3 wyszukiwań tablic: hel, ell, llo. Nawiasem mówiąc, zbudowanie tego stołu będzie bardzo szybkie, ponieważ w twojej sieci jest tylko 400 możliwych 3-literowych ruchów.
Oblicz wstępnie wskaźniki ruchów w siatce, które musisz uwzględnić w tabeli. W powyższym przykładzie musisz ustawić następujące wpisy na „Prawda”:
Jestem pewien, że jeśli zastosujesz to podejście, możesz sprawić, że Twój kod będzie działał niesamowicie szybko, jeśli masz słownik wstępnie obliczony i już załadowany do pamięci.
BTW: Inną przyjemną rzeczą, jeśli budujesz grę, jest uruchamianie tego rodzaju rzeczy natychmiast w tle. Rozpocznij generowanie i rozwiązywanie pierwszej gry, gdy użytkownik nadal patrzy na ekran tytułowy aplikacji i ustawia palec na pozycji, aby nacisnąć „Graj”. Następnie wygeneruj i rozwiąż następną grę, gdy użytkownik gra w poprzednią. To powinno dać ci dużo czasu na uruchomienie kodu.
(Podoba mi się ten problem, więc prawdopodobnie będę miał ochotę wdrożyć moją propozycję w Javie w najbliższych dniach, aby zobaczyć, jak by to faktycznie działało ... opublikuję kod tutaj, kiedy to zrobię).
AKTUALIZACJA:
Ok, miałem dzisiaj trochę czasu i wdrożyłem ten pomysł w Javie:
Oto kilka wyników:
W przypadku siatki z obrazka opublikowanego w pierwotnym pytaniu (DGHI ...):
Dla listów opublikowanych jako przykład w pierwotnym pytaniu (FXIE ...)
Dla następującej siatki 5x5:
daje to:
W tym celu wykorzystałem listę słów turniejowych TWL06 , ponieważ link w pierwotnym pytaniu już nie działa. Ten plik ma 1,85 MB, więc jest trochę krótszy. A
buildDictionary
funkcja wyrzuca wszystkie słowa zawierające mniej niż 3 litery.Oto kilka uwag na temat wydajności tego:
Jest około 10 razy wolniejszy niż raportowana wydajność implementacji OCaml Victora Nicolleta. Niezależnie od tego, czy jest to spowodowane przez inny algorytm, krótszy słownik, którego używa, fakt, że jego kod jest kompilowany, a mój działa na maszynie wirtualnej Java, lub wydajność naszych komputerów (moim jest Intel Q6600 @ 2,4 MHz z systemem WinXP), Nie wiem Jest to jednak znacznie szybsze niż wyniki dla innych implementacji cytowane na końcu pierwotnego pytania. Tak więc, czy ten algorytm jest lepszy od słownika trie, czy nie, nie wiem w tym momencie.
Zastosowana metoda
checkWordTriplets()
tabelowa daje bardzo dobre przybliżenie do rzeczywistych odpowiedzi. Tylko 1 na 3-5 słów, które przejdzie, nie przejdziecheckWords()
testu (patrz liczba kandydatów vs. liczba faktycznych słów powyżej).Coś, czego nie widać powyżej:
checkWordTriplets()
Funkcja zajmuje około 3,65 ms i dlatego jest w pełni dominująca w procesie wyszukiwania.checkWords()
Funkcja zajmuje dość dużo pozostałe 0,05-0,20 ms.Czas wykonania
checkWordTriplets()
funkcji zależy liniowo od wielkości słownika i jest praktycznie niezależny od wielkości płyty!Czas wykonania
checkWords()
zależy od wielkości planszy i liczby słów, które nie są wykluczonecheckWordTriplets()
.Powyższe
checkWords()
wdrożenie jest najgłupszą pierwszą wersją, jaką wymyśliłem. Zasadniczo nie jest w ogóle zoptymalizowany. Ale w porównaniu zcheckWordTriplets()
tym nie ma znaczenia dla całkowitej wydajności aplikacji, więc nie martwiłem się o to. Ale jeśli rozmiar płyty się powiększy, ta funkcja będzie coraz wolniejsza i ostatecznie zacznie mieć znaczenie. Następnie należałoby go również zoptymalizować.Jedną zaletą tego kodu jest jego elastyczność:
initializeBoard()
.Ok, ale myślę, że do tej pory ten post jest wystarczająco długi. Z całą pewnością mogę odpowiedzieć na wszelkie pytania, ale przejdźmy do komentarzy.
źródło
ok = possibleTriplets[entry.triplets[t]];
. hmmmentry.letters[i] = (byte) letter - 65;
Po prostu bierze wartość ASCII i odejmuje 65 („A”). Jeśli masz w słowniku Umlauty lub małe litery, da to wartości większe niż 31, które nie są planowane przez ustawienie wielkości alfabetu w linii 9. Aby obsługiwać inne litery, musisz rozwinąć ten wiersz aby zamapować je w zakresie dozwolonym przez rozmiar alfabetu.Zaskakujące, nikt nie próbował tej wersji PHP.
To jest działająca wersja PHP rozwiązania Pythona Johna Fouhy.
Chociaż wziąłem pewne wskazówki z odpowiedzi wszystkich innych, jest to w większości skopiowane od Johna.
Oto link na żywo jeśli chcesz go wypróbować. Chociaż zajmuje to ~ 2s na moim komputerze lokalnym, zajmuje ~ 5s na moim serwerze internetowym. W obu przypadkach nie jest to bardzo szybkie. Mimo to jest to dość ohydne, więc mogę sobie wyobrazić, że czas można znacznie skrócić. Wszelkie wskazówki dotyczące tego, jak to osiągnąć, będą mile widziane. Brak krotek w PHP sprawił, że współrzędne były dziwne, a moja niemożność zrozumienia, co się do cholery dzieje, wcale nie pomogła.
EDYCJA : Kilka poprawek sprawia, że lokalnie zajmuje to mniej niż 1 sekundę.
źródło
Nie interesuje Cię VB? :) Nie mogłem się oprzeć. Rozwiązałem to inaczej niż wiele przedstawionych tutaj rozwiązań.
Moje czasy to:
EDYCJA: Czasy ładowania słownika na serwerze hosta działają o około 1 do 1,5 sekundy dłużej niż na moim komputerze domowym.
Nie wiem, jak źle czasy się pogorszą przy obciążeniu serwera.
Moje rozwiązanie napisałem jako stronę internetową w .Net. myvrad.com/boggle
Korzystam ze słownika wymienionego w pierwotnym pytaniu.
Litery nie są ponownie używane w słowie. Znaleziono tylko słowa o długości 3 znaków lub dłuższe.
Używam hashtable wszystkich unikalnych prefiksów i słów zamiast trie. Nie wiedziałem o trie, więc się tam czegoś nauczyłem. Pomysł stworzenia listy prefiksów słów oprócz pełnych słów jest tym, co ostatecznie sprowadziło mój czas na znaczną liczbę.
Przeczytaj komentarze do kodu, aby uzyskać dodatkowe informacje.
Oto kod:
źródło
Gdy tylko zobaczyłem opis problemu, pomyślałem „Trie”. Ale widząc, jak kilka innych plakatów wykorzystało to podejście, szukałem innego podejścia, aby być innym. Niestety, podejście Trie działa lepiej. Uruchomiłem Perla Kenta na moim komputerze i uruchomienie go zajęło 0,31 sekundy, po dostosowaniu go do użycia pliku słownika. Uruchomienie mojej własnej implementacji perla wymagało 0,54 sekundy.
To było moje podejście:
Utwórz skrót przejścia, aby modelować legalne przejścia.
Iteruj przez wszystkie 16 ^ 3 możliwe trzyliterowe kombinacje.
Następnie przejdź przez wszystkie słowa w słowniku.
Wydrukuj znalezione słowa.
Próbowałem sekwencji 3-literowych i 4-literowych, ale sekwencje 4-literowe spowolniły program.
W moim kodzie używam / usr / share / dict / words do mojego słownika. Jest standardem w systemie Mac OS X i wielu systemach uniksowych. Możesz użyć innego pliku, jeśli chcesz. Aby złamać inną łamigłówkę, po prostu zmień zmienną @puzzle. Łatwo byłoby to dostosować do większych matryc. Musisz tylko zmienić skrót mieszania% przejść i skrót mieszania% legalTransitions.
Zaletą tego rozwiązania jest to, że kod jest krótki, a struktury danych proste.
Oto kod Perla (wiem, że używa zbyt wielu zmiennych globalnych):
źródło
Wiem, że się spóźniłem, ale jeden z nich zrobiłem jakiś czas temu w PHP - dla zabawy też ...
http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastu Znaleziono 75 słów (133 pkt) w 0,90108 sekund
F.........X..I..............E............... A......................................M..............................L............................O............................... E....................W............................B..........................X A..................S..................................................T.................U....
Daje pewne wskazówki na temat tego, co faktycznie robi program - każda litera rozpoczyna przeglądanie wzorów, a każda „.” pokazuje ścieżkę, którą próbował obrać. Więcej '.' istnieje dalsze wyszukiwanie.
Daj mi znać, jeśli chcesz kod ... to straszna mieszanka PHP i HTML, która nigdy nie miała ujrzeć światła dziennego, więc nie ważę się go tutaj nie publikować: P
źródło
Spędziłem 3 miesiące pracując nad rozwiązaniem problemu 10 najlepszych gęstych punktów 5x5 tablic Boggle.
Problem został już rozwiązany i przedstawiony z pełnym ujawnieniem na 5 stronach internetowych. Proszę o kontakt z pytaniami.
Algorytm analizy tablic używa jawnego stosu, aby pseudo-rekurencyjnie przechodzić przez kwadraty planszy przez Directed Acyclic Word Graph z bezpośrednimi informacjami potomnymi i mechanizmem śledzenia znaczników czasu. Może to być najbardziej zaawansowana struktura danych leksykalnych na świecie.
Schemat ocenia około 10 000 bardzo dobrych płyt na sekundę na poczwórnym rdzeniu. (9500 punktów)
Nadrzędna strona internetowa:
DeepSearch.c - http://www.pathcom.com/~vadco/deep.html
Składowe strony internetowe:
Optymalna tablica wyników - http://www.pathcom.com/~vadco/binary.html
Zaawansowana struktura leksykonu - http://www.pathcom.com/~vadco/adtdawg.html
Algorytm analizy płytki - http://www.pathcom.com/~vadco/guns.html
Równoległe przetwarzanie wsadowe - http://www.pathcom.com/~vadco/parallel.html
- Ten kompleksowy zakres prac zainteresuje tylko osobę, która wymaga tego, co najlepsze.
źródło
Czy Twój algorytm wyszukiwania stale zmniejsza listę słów w miarę wyszukiwania?
Na przykład w powyższym wyszukiwaniu jest tylko 13 liter, od których słowa mogą zaczynać (skutecznie zmniejszając do połowy liczby liter początkowych).
W miarę dodawania kolejnych permutacji liter dalsze zmniejszanie dostępnych zestawów słów zmniejsza konieczność wyszukiwania.
Zacznę tam
źródło
Musiałbym więcej zastanowić się nad kompletnym rozwiązaniem, ale jako przydatna optymalizacja zastanawiam się, czy warto byłoby wstępnie obliczyć tabelę częstotliwości digramów i trygramów (kombinacje 2- i 3-literowe) na podstawie wszystkich słowa ze słownika i użyj go do ustalenia priorytetu wyszukiwania. Wybrałbym początkowe litery słów. Jeśli więc słownik zawiera słowa „Indie”, „Woda”, „Ekstremalne” i „Niezwykłe”, wówczas obliczona tabela może być następująca:
Następnie wyszukaj te digramy w kolejności podobieństwa (najpierw EX, potem WA / IN)
źródło
Najpierw przeczytaj, jak jeden z projektantów języka C # rozwiązał powiązany problem: http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx .
Podobnie jak on, możesz zacząć od słownika i kanonizować słowa, tworząc słownik od tablicy liter posortowanych alfabetycznie do listy słów, które można przeliterować na podstawie tych liter.
Następnie zacznij tworzyć możliwe słowa z tablicy i przeglądaj je. Podejrzewam, że doprowadzi cię to dość daleko, ale z pewnością jest więcej sztuczek, które mogą przyspieszyć.
źródło
Sugeruję utworzenie drzewa liter na podstawie słów. Drzewo będzie się składać z struktur literowych, takich jak to:
Następnie budujesz drzewo, a każda głębokość dodaje nową literę. Innymi słowy, na pierwszym poziomie byłby alfabet; następnie z każdego z tych drzew będzie kolejnych 26 wpisów i tak dalej, dopóki nie przeliterujesz wszystkich słów. Trzymaj się tego przeanalizowanego drzewa, a wszystkie możliwe odpowiedzi będą szybciej wyszukiwane.
Za pomocą tego przeanalizowanego drzewa możesz bardzo szybko znaleźć rozwiązania. Oto pseudo-kod:
Można to przyspieszyć odrobiną dynamicznego programowania. Na przykład w twojej próbce dwa „A” znajdują się obok „E” i „W”, które (od punktu, w który je uderzyły) byłyby identyczne. Nie mam wystarczająco dużo czasu, aby naprawdę przeliterować kod, ale myślę, że możesz to zrozumieć.
Ponadto jestem pewien, że znajdziesz inne rozwiązania, jeśli Google dla „Boggle solver”.
źródło
Dla zabawy zaimplementowałem jeden w bash. To nie jest super szybkie, ale rozsądne.
http://dev.xkyle.com/bashboggle/
źródło
Wesoły. Kilka dni temu prawie napisałem to samo pytanie z powodu tej samej cholernej gry! Nie zrobiłem tego jednak, ponieważ właśnie szukałem w Google Pythona w języku boggle solver i uzyskałem wszystkie odpowiedzi, których mogłem chcieć.
źródło
Zdaję sobie sprawę, że czas na to pytanie minął, ale ponieważ sam pracowałem nad solwerem i natknąłem się na to podczas przeglądania Google, pomyślałem, że powinienem opublikować odniesienie do mojego, ponieważ wydaje się ono nieco inne niż niektóre inne.
Zdecydowałem się użyć płaskiej tablicy na planszy i wykonywać rekurencyjne polowania z każdej litery na planszy, przechodząc od ważnego sąsiada do ważnego sąsiada, rozszerzając polowanie, jeśli bieżąca lista liter jest poprawnym prefiksem w indeksie. Podczas przechodzenia przez pojęcie bieżącego słowa jest lista indeksów na tablicy, a nie litery, które składają się na słowo. Podczas sprawdzania indeksu indeksy są tłumaczone na litery i sprawdzanie jest wykonywane.
Indeks jest słownikiem typu brute force, który jest trochę jak trie, ale pozwala na zapytania Pythona o indeks. Jeśli na liście znajdują się słowa „kot” i „cater”, otrzymasz to w słowniku:
Więc jeśli bieżącym słowem jest „ca”, wiesz, że jest to poprawny przedrostek, ponieważ
'ca' in d
zwraca True (więc kontynuuj przeglądanie tablicy). A jeśli bieżącym słowem jest „kot”, to wiesz, że jest to poprawne słowo, ponieważ jest to poprawny przedrostek i'cat' in d['cat']
zwraca również wartość True.Jeśli wydaje się, że jest to dozwolone dla pewnego czytelnego kodu, który nie wydaje się zbyt wolny. Podobnie jak wszyscy inni, wydatkiem w tym systemie jest czytanie / budowanie indeksu. Rozwiązanie planszy to w zasadzie hałas.
Kod znajduje się na stronie http://gist.github.com/268079 . Jest celowo pionowy i naiwny, z dużą ilością jawnej kontroli poprawności, ponieważ chciałem zrozumieć problem bez kruszenia go za pomocą magii lub niejasności.
źródło
Mój solver napisałem w C ++. Zaimplementowałem niestandardową strukturę drzewa. Nie jestem pewien, czy można to uznać za trie, ale jest podobnie. Każdy węzeł ma 26 gałęzi, po 1 na każdą literę alfabetu. Przemierzam gałęzie tablicy boggle równolegle do gałęzi mojego słownika. Jeśli gałąź nie istnieje w słowniku, przestaję ją wyszukiwać na tablicy Boggle. Konwertuję wszystkie litery na tablicy na ints. Zatem „A” = 0. Ponieważ są to tylko tablice, wyszukiwanie zawsze ma wartość O (1). Każdy węzeł przechowuje, jeśli uzupełnia słowo i ile słów istnieje w jego elementach potomnych. Drzewo jest przycinane, ponieważ znaleziono słowa, które ograniczają wielokrotne wyszukiwanie tych samych słów. Uważam, że przycinanie jest również O (1).
Procesor: Pentium SU2700
1,3 GHz RAM: 3 GB
Ładuje słownik 178 590 słów w <1 sekundę.
Rozwiązuje Boggle 100x100 (boggle.txt) w 4 sekundy. Znaleziono około 44 000 słów.
Rozwiązanie Boggle 4x4 jest zbyt szybkie, aby zapewnić znaczący punkt odniesienia. :)
Szybkie Boggle Solver GitHub Repo
źródło
Biorąc pod uwagę tablicę Boggle z N rzędami i M kolumnami, załóżmy, że:
Przy tych założeniach złożoność tego rozwiązania wynosi O (N * M).
Myślę, że porównywanie czasów działania dla tej jednej przykładowej płyty na wiele sposobów nie ma sensu, ale ze względu na kompletność to rozwiązanie kończy się w <0,2 s na moim nowoczesnym MacBooku Pro.
To rozwiązanie znajdzie wszystkie możliwe ścieżki dla każdego słowa w korpusie.
źródło
To rozwiązanie daje również kierunek wyszukiwania w danej tablicy
Algo:
Wynik:
Kod:
źródło
Mam wdrożone rozwiązanie w SML . Wstępnie kompiluje słownik jako trie i wykorzystuje dwuliterowe częstotliwości sekwencji, aby wyeliminować krawędzie, które nigdy nie mogłyby pojawić się w słowie, aby przyspieszyć przetwarzanie.
Rozwiązuje przykładową płytkę w 0,35 ms (z dodatkowym czasem uruchamiania 6 ms, który jest głównie związany z ładowaniem trie do pamięci).
Znalezione rozwiązania:
źródło
/usr/share/dict
słownika i niektórych słów rzeczywiście brakuje (np. EMBOLE).Rozwiązanie JavaScript Node.JS. Oblicza wszystkie 100 niepowtarzalnych słów w mniej niż sekundę, w tym czytanie pliku słownika (MBA 2012).
Wynik:
[„FAM”, „TUX”, „TUB”, „FAE”, „ELI”, „ELM”, „ELB”, „TWA”, „TWA”, „SAW”, „AMI”, „SWA” , „SWA”, „AME”, „SEA”, „SEW”, „AES”, „AWL”, „AWE”, „SEA”, „AWA”, „MIX”, „MIL”, „AST”, „ ASE ”,„ MAX ”,„ MAE ”,„ MAW ”,„ MEW ”,„ AWE ”,„ MES ”,„ AWL ”,„ LIE ”,„ LIM ”,„ AWA ”,„ AES ”,„ ALE ” , „BLO”, „WAS”, „WAE”, „WEA”, „LEI”, „LEO”, „LOB”, „LOX”, „WEM”, „OIL”, „OLM”, „WEA”, „ WAE ”,„ WAX ”,„ WAF ”,„MILO”, „EAST”, „WAME”, „TWAS”, „TWAE”, „EMIL”, „WEAM”, „OIME”, „AXIL”, „WEST”, „TWAE”, „kończyna”, „WASE ”,„ WAST ”,„ BLEO ”,„ STUB ”,„ BOIL ”,„ BOLE ”,„ LIME ”,„ SAWT ”,„ LIMA ”,„ MESA ”,„ MEWL ”,„ AXLE ”,„ FAME ”, „ASEM”, „MILE”, „AMIL”, „SEAX”, „SEAM”, „SEMI”, „SWAM”, „AMBO”, „AMLI”, „AXILE”, „AMBLE”, „SWAMI”, „AWEST ”,„ AWEST ”,„ LIMAX ”,„ LIMES ”,„ LIMBU ”,„ LIMBO ”,„ EMBOX ”,„ SEMBLE ”,„ EMBOLE ”,„ WAMBLE ”,„ FAMBLE ”]EAST ”,„ WAME ”,„ TWAS ”,„ TWAE ”,„ EMIL ”,„ WEAM ”,„ OIME ”,„ AXIL ”,„ WEST ”,„ TWAE ”,„ kończyna ”,„ WASE ”,„ WAST ” , „BLEO”, „STUB”, „BOIL”, „BOLE”, „LIME”, „SAWT”, „LIMA”, „MESA”, „MEWL”, „AXLE”, „FAME”, „ASEM”, „ MILE ”,„ AMIL ”,„ SEAX ”,„ SEAM ”,„ SEMI ”,„ SWAM ”,„ AMBO ”,„ AMLI ”,„ AXILE ”,„ AMBLE ”,„ SWAMI ”,„ AWEST ”,„ AWEST ” , „LIMAX”, „LIMES”, „LIMBU”, „LIMBO”, „EMBOX”, „SEMBLE”, „EMBOLE”, „WAMBLE”, „FAMBLE”]EAST ”,„ WAME ”,„ TWAS ”,„ TWAE ”,„ EMIL ”,„ WEAM ”,„ OIME ”,„ AXIL ”,„ WEST ”,„ TWAE ”,„ kończyna ”,„ WASE ”,„ WAST ” , „BLEO”, „STUB”, „BOIL”, „BOLE”, „LIME”, „SAWT”, „LIMA”, „MESA”, „MEWL”, „AXLE”, „FAME”, „ASEM”, „ MILE ”,„ AMIL ”,„ SEAX ”,„ SEAM ”,„ SEMI ”,„ SWAM ”,„ AMBO ”,„ AMLI ”,„ AXILE ”,„ AMBLE ”,„ SWAMI ”,„ AWEST ”,„ AWEST ” , „LIMAX”, „LIMES”, „LIMBU”, „LIMBO”, „EMBOX”, „SEMBLE”, „EMBOLE”, „WAMBLE”, „FAMBLE”]„TWAE”, „EMIL”, „WEAM”, „OIME”, „AXIL”, „WEST”, „TWAE”, „kończyna”, „WASE”, „WAST”, „BLEO”, „STUB”, „BOIL ”,„ BOLE ”,„ LIME ”,„ SAWT ”,„ LIMA ”,„ MESA ”,„ MEWL ”,„ AXLE ”,„ FAME ”,„ ASEM ”,„ MILE ”,„ AMIL ”,„ SEAX ”, „SEAM”, „SEMI”, „SWAM”, „AMBO”, „AMLI”, „AXILE”, „AMBLE”, „SWAMI”, „AWEST”, „AWEST”, „LIMAX”, „LIMES”, „LIMBU ”,„ LIMBO ”,„ EMBOX ”,„ SEMBLE ”,„ EMBOLE ”,„ WAMBLE ”,„ FAMBLE ”]„TWAE”, „EMIL”, „WEAM”, „OIME”, „AXIL”, „WEST”, „TWAE”, „kończyna”, „WASE”, „WAST”, „BLEO”, „STUB”, „BOIL ”,„ BOLE ”,„ LIME ”,„ SAWT ”,„ LIMA ”,„ MESA ”,„ MEWL ”,„ AXLE ”,„ FAME ”,„ ASEM ”,„ MILE ”,„ AMIL ”,„ SEAX ”, „SEAM”, „SEMI”, „SWAM”, „AMBO”, „AMLI”, „AXILE”, „AMBLE”, „SWAMI”, „AWEST”, „AWEST”, „LIMAX”, „LIMES”, „LIMBU ”,„ LIMBO ”,„ EMBOX ”,„ SEMBLE ”,„ EMBOLE ”,„ WAMBLE ”,„ FAMBLE ”]„WEST”, „TWAE”, „KOŃCZYNA”, „WASE”, „WAST”, „BLEO”, „STUB”, „BOIL”, „BOLE”, „LIME”, „SAWT”, „LIMA”, „MESA ”,„ MEWL ”,„ AXLE ”,„ FAME ”,„ ASEM ”,„ MILE ”,„ AMIL ”,„ SEAX ”,„ SEAM ”,„ SEMI ”,„ SWAM ”,„ AMBO ”,„ AMLI ”, „AXILE”, „AMBLE”, „SWAMI”, „AWEST”, „AWEST”, „LIMAX”, „LIMES”, „LIMBU”, „LIMBO”, „EMBOX”, „SEMBLE”, „EMBOLE”, „WAMBLE ”,„ FAMBLE ”]„WEST”, „TWAE”, „KOŃCZYNA”, „WASE”, „WAST”, „BLEO”, „STUB”, „BOIL”, „BOLE”, „LIME”, „SAWT”, „LIMA”, „MESA ”,„ MEWL ”,„ AXLE ”,„ FAME ”,„ ASEM ”,„ MILE ”,„ AMIL ”,„ SEAX ”,„ SEAM ”,„ SEMI ”,„ SWAM ”,„ AMBO ”,„ AMLI ”, „AXILE”, „AMBLE”, „SWAMI”, „AWEST”, „AWEST”, „LIMAX”, „LIMES”, „LIMBU”, „LIMBO”, „EMBOX”, „SEMBLE”, „EMBOLE”, „WAMBLE ”,„ FAMBLE ”]SAWT ”,„ LIMA ”,„ MESA ”,„ MEWL ”,„ AXLE ”,„ FAME ”,„ ASEM ”,„ MILE ”,„ AMIL ”,„ SEAX ”,„ SEAM ”,„ SEMI ”,„ SWAM ” , „AMBO”, „AMLI”, „AXILE”, „AMBLE”, „SWAMI”, „AWEST”, „AWEST”, „LIMAX”, „LIMES”, „LIMBU”, „LIMBO”, „EMBOX”, „ SEMBLE ”,„ EMBOLE ”,„ WAMBLE ”,„ FAMBLE ”]SAWT ”,„ LIMA ”,„ MESA ”,„ MEWL ”,„ AXLE ”,„ FAME ”,„ ASEM ”,„ MILE ”,„ AMIL ”,„ SEAX ”,„ SEAM ”,„ SEMI ”,„ SWAM ” , „AMBO”, „AMLI”, „AXILE”, „AMBLE”, „SWAMI”, „AWEST”, „AWEST”, „LIMAX”, „LIMES”, „LIMBU”, „LIMBO”, „EMBOX”, „ SEMBLE ”,„ EMBOLE ”,„ WAMBLE ”,„ FAMBLE ”]LIMAX ”,„ LIMES ”,„ LIMBU ”,„ LIMBO ”,„ EMBOX ”,„ SEMBLE ”,„ EMBOLE ”,„ WAMBLE ”,„ FAMBLE ”]LIMAX ”,„ LIMES ”,„ LIMBU ”,„ LIMBO ”,„ EMBOX ”,„ SEMBLE ”,„ EMBOLE ”,„ WAMBLE ”,„ FAMBLE ”]
Kod:
źródło
Chciałem więc dodać inny sposób rozwiązania tego problemu, ponieważ wszyscy kochają PHP. Chciałbym zrobić trochę refaktoryzacji, na przykład użyć dopasowania wyrażenia przeciwnego do pliku słownika, ale w tej chwili ładuję cały plik słownika do listy słów.
Zrobiłem to, korzystając z pomysłu na listę połączoną. Każdy węzeł ma wartość znaku, wartość lokalizacji i następny wskaźnik.
Wartość lokalizacji jest sposobem, w jaki dowiedziałem się, czy dwa węzły są połączone.
Korzystając z tej siatki, wiem, że dwa węzły są połączone, jeśli położenie pierwszego węzła jest równe położeniu drugiego węzła +/- 1 dla tego samego rzędu, +/- 9, 10, 11 dla rzędu powyżej i poniżej.
Używam rekurencji do wyszukiwania głównego. Usuwa słowo z listy słów, wyszukuje wszystkie możliwe punkty początkowe, a następnie rekurencyjnie znajduje następne możliwe połączenie, pamiętając, że nie może przejść do lokalizacji, z której już korzysta (dlatego dodam $ notInLoc).
W każdym razie wiem, że wymaga to trochę refaktoryzacji i chciałbym usłyszeć opinie na temat tego, jak uczynić go czystszym, ale daje prawidłowe wyniki na podstawie pliku słownika, którego używam. W zależności od liczby samogłosek i kombinacji na planszy zajmuje to od 3 do 6 sekund. Wiem, że kiedy już dopasuję wyniki słownika, to znacznie się zmniejszy.
źródło
Wiem, że jestem naprawdę spóźniony na imprezie, ale zaimplementowałem, jako ćwiczenie programistyczne, rozwikłany solver w kilku językach programowania (C ++, Java, Go, C #, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl) i Myślałem, że ktoś może być nimi zainteresowany, więc zostawiam link tutaj: https://github.com/AmokHuginnsson/boggle-solvers
źródło
Oto rozwiązanie Używanie predefiniowanych słów w zestawie narzędzi NLTK NLTK ma pakiet nltk.corpus w tym, że mamy pakiet o nazwie słowa i zawiera on więcej niż dwa słowa angielskie, których możesz po prostu użyć w swoim programie.
Po utworzeniu matrycy przekonwertuj ją na tablicę znaków i wykonaj ten kod
Wynik:
Mam nadzieję, że rozumiesz.
źródło
Oto moja implementacja Java: https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java
Kompilacja Trie zajęła 0 godzin, 0 minut, 1 sekundę, 532 milisekund
Wyszukiwanie słowa zajęło 0 godzin, 0 minut, 0 sekund, 92 milisekund
Uwaga: użyłem słownika i matrycy znaków na początku tego wątku. Kod został uruchomiony na moim MacBookPro, poniżej znajduje się kilka informacji o maszynie.
Nazwa modelu: MacBook Pro
Identyfikator modelu: MacBookPro8,1
Nazwa procesora: Intel Core i5
Szybkość procesora: 2,3 GHz
Liczba procesorów: 1
Całkowita liczba rdzeni: 2
L2 Cache (na rdzeń): 256 KB
L3 Cache: 3 MB
Pamięć: 4 GB
Boot ROM Wersja: MBP81.0047.B0E
Wersja SMC (system): 1.68f96
źródło
Też rozwiązałem to za pomocą Java. Moja implementacja ma 269 linii i jest łatwa w użyciu. Najpierw musisz utworzyć nową instancję klasy Boggler, a następnie wywołać funkcję rozwiązywania z siatką jako parametrem. Załadowanie słownika zawierającego 50 000 słów na moim komputerze zajmuje około 100 ms, a znalezienie słów następuje po około 10-20 ms. Znalezione słowa są przechowywane w ArrayList,
foundWords
.źródło
Rozwiązałem to w ok. Uruchomienie na moim komputerze zajmuje około 48 ms (około 98% czasu spędzonego na ładowaniu słownika z dysku i tworzeniu trie). Słownik to / usr / share / dict / american-english, który ma 62886 słów.
Kod źródłowy
źródło
Rozwiązałem to doskonale i bardzo szybko. Umieściłem go w aplikacji na Androida. Wyświetl wideo w linku do sklepu Play, aby zobaczyć go w akcji.
Word Cheats to aplikacja, która „łamie” każdą grę słowną w stylu matrycy. Ta aplikacja została stworzona, aby pomóc mi oszukiwać w programie szyfrującym. Może być używany do wyszukiwania słów, ruzzle, słów, wyszukiwarki słów, crackowania słów, boggle i wiele więcej!
Można to zobaczyć tutaj https://play.google.com/store/apps/details?id=com.harris.wordcracker
Zobacz aplikację w akcji na wideo https://www.youtube.com/watch?v=DL2974WmNAI
źródło