Scralphabet
Normalna torba płytek Scrabble zawiera następujące litery ( ?
jest to pusta płytka, która może oznaczać każdą inną literę):
AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJKLLLLMMNNNNNNOOOOOOOOPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZ??
Litery mają następującą wartość:
{"A": 1,"B": 3,"C": 3,"D": 2,"E": 1,"F": 4,"G": 2,"H": 4,"I": 1,"J": 8,"K": 5,"L": 1,"M": 3,"N": 1,"O": 1,"P": 3,"Q": 10,"R": 1,"S": 1,"T": 1,"U": 1,"V": 4,"W": 4,"X": 8,"Y": 4,"Z": 10,"?": 0}
Biorąc pod uwagę normalną torbę płytek Scrabble, stwórz zestaw najwyżej punktowanych słów nieprzecinających się (tj. Pojedyncze słowa, nie na planszy Scrabble), biorąc pod uwagę następujące warunki:
- Wynik dla każdego słowa to
sum(letter_values) * length(word)
. - Możesz dołączyć maksymalnie jedno słowo zaczynające się na każdą literę alfabetu (czyli maksymalnie 26 słów).
- Można uwzględnić tylko prawidłowe słowa Scrabble (z tego słownika ). Możesz odczytać słownik z pliku, zakodować go na sztywno (ugh) lub zeskrobać ze strony internetowej.
- Nie musisz używać każdego kafelka, ale wszystkie nieużywane kafelki tworzą jedno słowo, punktowane w ten sam sposób, który odejmuje od wyniku.
Jeśli chcesz, twój kod może zaakceptować dwa dane wejściowe: zawartość torby jako ciąg znaków oraz wartości literowe w jakimś formacie podobnym do pytona dict
(jak wyżej); alternatywnie możesz zakodować na stałe zawartość torby i wartości literowe. Powinien wyświetlać wyrazy w zestawie, odpowiadające im wyniki i całkowity wynik, w rozsądnym formacie.
Zestaw słów o najwyższej liczbie punktów wygrywa, a na pierwszym miejscu są remisy.
źródło
print"FOO18\nBAR15\nBAZ42\n...\n1523"
?Odpowiedzi:
C, 2765 (optymalna)
Edytować
Teraz wszystko w jednym pliku C. To po prostu znajduje wszystkie optymalne rozwiązania. Wszystkie muszą mieć 6 słów po 15 liter i jedno 10-literowe słowo składające się z 8 liter o wartości 1 i dwóch odstępów. W tym celu muszę załadować tylko ułamek słownika i nie muszę szukać 15-literowych słów ze spacjami. Kod jest prostym, wyczerpującym wyszukiwaniem w pierwszej kolejności.
Stosowanie:
Uwaga: każde rozwiązanie jest drukowane dwukrotnie, ponieważ podczas dodawania 15-literowego słowa „W” tworzone są 2 zamówienia, ponieważ istnieją 2 „W” płytki.
Pierwsze rozwiązanie z podziałem punktowym:
Edycja: wyjaśnienie
Co umożliwia przeszukiwanie całej przestrzeni? Dodając nowe słowo, biorę pod uwagę tylko te słowa, które mają najrzadszą pozostałą literę. W każdym razie ta litera musi zawierać jakieś słowo (i 15-literowe słowo, ponieważ będzie to litera o wartości innej niż 1, choć tego nie sprawdzam). Zacznę więc od słów,
J, Q, W, W, X, Z
które się liczą50, 100, 100, 100, 200, 500
. Na niższych poziomach jestem bardziej odcięty, ponieważ niektóre słowa są eliminowane przez brak liter. Szerokość drzewa wyszukiwania na każdym poziomie:Oczywiście dużą część odcięcia uzyskuje się, nie sprawdzając nieoptymalnych rozwiązań (puste 15-literowe słowa lub krótsze słowa). Na szczęście dzięki temu słownikowi można uzyskać rozwiązanie 2765 (ale było blisko, tylko 2 kombinacje 15-literowych słów dają rozsądne resztki). Z drugiej strony łatwo jest zmodyfikować kod, aby znaleźć kombinacje o niższej punktacji, w których nie wszystkie 10 pozostałych liter ma 1-krotną wartość, choć trudniej byłoby udowodnić, że byłoby to optymalne rozwiązanie.
Również kod pokazuje klasyczny przypadek przedwczesnej optymalizacji. Ta wersja
matches
funkcji spowalnia kod tylko o 30%:Wymyśliłem nawet, jak sprawić, by porównanie magii równoległych bitów było jeszcze krótsze niż w moim oryginalnym kodzie (w tym przypadku nie można użyć najwyższego skrawka, ale to nie jest problem, ponieważ potrzebuję tylko 26 z 32 skórek):
Ale daje zerową przewagę.
Edytować
Pisząc powyższe wyjaśnienie, zdałem sobie sprawę, że większość czasu spędzam na skanowaniu listy słów pod kątem tych, które zawierają określoną literę, która nie jest w
matches
funkcji. Obliczanie list z góry dało 10-krotne przyspieszenie.źródło
Python 2, wynik:
18402162Ten program najpierw znajduje najlepsze słowo punktacji dostępne dla danego kafelka (bez użycia symboli wieloznacznych), a następnie podejmuje 10000 prób włączenia losowych słów, które spełniają ograniczenia unikalnej pierwszej postaci i mają dostępne kafelki. Przy obecnych stałych program działa na moim komputerze 27 sekund. Zastosowanie większych stałych prawdopodobnie zapewniłoby wyższą kombinację słów.
AKTUALIZACJA: Teraz wykorzystuje 2-stopniowy algorytm wyboru, więc wyszukuje najlepsze z 50 słów na każdym etapie wyboru. Punktacja karna jest teraz używana również w algorytmie oceny.
Podaję tutaj najlepszy z kilku przebiegów:
Pamiętaj, że nie używam dzikich kart i płacę większą karę (ze względu na długość słowa). Przyszłe ulepszenie może obejmować użycie symboli wieloznacznych.
źródło
Symulowane wyżarzanie (wynik 2246)
Niestety jest to niedeterministyczne. Spróbuję to naprawić i znajdę deterministyczne ziarno, które daje lepszą wartość.
źródło
Python, wynik
263826752676268926992717Wynik:
Kod:
Wyjaśnienie:
Głębokie wyszukiwanie, które przeszukuje całe drzewo, wybierając najlepsze
picks
najlepsze słowa na każdym etapie.Na początku sortuję całą listę słów według wyniku. Po wybraniu każdego słowa, do następnej iteracji odfiltrowuję wszystkie słowa, które nie są już możliwe, zachowując kolejność, więc nie muszę sortować listy na każdym kroku. Aby poradzić sobie z symbolami wieloznacznymi, jeśli istnieje możliwość, że potrzebna jest karta wieloznaczna, wybieram 10000 najlepszych kandydatów, w razie potrzeby zastępuję brakujące litery symbolami wieloznacznymi i ponownie sortuję na podstawie nowych (niższych) wyników.
To wyjście jest dla
picks=5
i zabrał8m01s
do pracy na moim 8-rdzeniowej maszynie.źródło
Java 8, wynik
26412681Program zaczyna się od 40 najlepszych słów. Dla każdego słowa wyszukuje 40 najlepszych słów do przejścia. Spośród 1600 kombinacji program przyjmuje najlepsze 40. Dla każdej kombinacji znajduje się 40 najlepszych słów i cykl się powtarza.
Gdy pozostało tylko kilka płytek, pozostałe litery są łączone z dwoma odstępami dla ostatniego słowa.
Aktualizacja
Podniosłem próg do 50 najlepszych słów. Ponadto każda kombinacja dodaje tylko słowa, które są mniejsze niż te już obecne. Zapobiega to wielokrotnym permutacjom tej samej grupy.
Program:
źródło
Perl, wynik: 2655
2630Posługiwać się:
Użycie pustych miejsc nie daje tak wiele, a znacznie spowalnia wykonanie:
Po dodaniu heurystyki:
źródło
Python 3, wynik 2735
(Optymalny wynik 2765, „6 słów po 15 liter i jedno 10-literowe słowo składające się z 8 liter o wartości 1 i dwóch spacji” zostało osiągnięte przez nutki .)
Użyłem chciwego podejścia podobnego do innych:
Zaczynam od list jednoelementowych zawierających słowa o najwyższym wyniku zawierające litery Q.
Na każdym kroku dla każdego elementu listy tworzę
k = 800
nowe listy z najlepszymi dozwolonymi słowami dla listy. Z zagregowanej listy list przechowuję listyk
najlepszych wyników i powtarzam ten proces 10 razy.Zauważ, że najlepsze
k
elementyn
długiej listy można uzyskać w O (n + k * log n), którym jest O (n), jeślik<<n
tak jak w naszym przypadku (k = 800, n ~= 250000
) z kolejką sterty. Myślę, że ta metoda nie jest używana w innych wnioskach, stąd mniejszek
wartości.W razie potrzeby używam symboli wieloznacznych.
Czas działania wynosi kilka minut
k = 800
. Większe wartości i inne optymalizacje nie przyniosły jeszcze lepszych wyników.Wynik:
Eksperymentowałem z produktem Descartesa najlepszych słów zawierających Q, J i X, ponieważ litery te ledwo dzielą słowa. Mój najlepszy wynik z tą strategią to 2723 (
DEMISEMIQUAVERS OXYPHENBUTAZONE INTERSUBJECTIVE FLASHFORWARDING KNOWLEDGABILITY RADIOPROTECTION ANALOGUE EA
).Niepotrzebny, skomplikowany kod spaghetti (ze śladami eksperymentów z innymi metodami):
źródło