Musisz napisać solver Hangman. Testując tę listę angielskich słów [1] , wygrywa solver, który rozwiązuje największą liczbę słów, przy czym liczba niepoprawnych zgadnięć jest rozstrzygająca. Wszystkie słowa na liście słów zostaną przetestowane w losowej kolejności.
[1]: Ta lista słów jest pobierana stąd , a następnie usuwane są liczby, następnie usuwane są słowa o długości 1 lub ze znakami niealfabetycznymi, a następnie jako tę listę słów wybiera się najczęściej 4096 niepowtarzalnych słów.
Szczegóły:
Twój program wejdzie w interakcję z programem do gry, który przekaże ci standardowe podkreślenia i poprawnie odgadnięte litery. Twój program da ci standardowe domysły i na podstawie danych wejściowych musi wywnioskować, czy poprzednie domniemanie było prawidłowe, czy złe. Po 6 razy pomyłce twój program przegrywa. Twój program musi być gotowy do następnej gry po zakończeniu każdej gry (po wygranej lub przegranej).
Długość kodu musi być mniejsza niż 2048 bajtów, a program nie może używać żadnych zasobów zewnętrznych (w tym między innymi dostępu do listy słów w lokalnej pamięci masowej lub przez Internet).
Przykład : (Dane wejściowe poprzedza się >tutaj wyłącznie w celu wyjaśnienia - nie są one faktycznie obecne w danych wejściowych)
>_______ // 7 underscores
a // Now you wait for input again
>_a___a_
e
>_a___a_ // Implies that your guess is wrong
>_____ // new round, this will be given ONLY IF you already have 6 losses
Załóżmy, że jesteś w błędzie przez 6 razy, otrzymasz końcowy wkład, który sugeruje, że twoje domysły są błędne, a twój program musi być gotowy do rozpoczęcia nowej rundy (tj. Weź inny wkład).
Jeśli wygrasz,
>_angman
h
>hangman
>_____ // new round
Po dowiedzeniu się, że wygrałeś (ponieważ wkład nie ma podkreślników), musisz być gotowy na przyjęcie następnej rundy.
Twój program musi zakończyć się, gdy otrzyma dane wejściowe END.
Jeśli twój program nie jest deterministyczny (zależy od losowości, pseudolosowości, czasu systemowego, temperatury otoczenia, mojego nastroju itp.), Musisz wyraźnie to zaznaczyć w swoim zgłoszeniu, a twój wynik zostanie pobrany 10 razy (przeze mnie, chyba że zalecono inaczej) i uśrednione.
Uwaga : jeśli używasz języków takich jak python, po każdym poleceniu wydruku wyraźnie wypróżnij swoje standardowe wyjście.
Program gry jest następujący ( przypis do nneonneo ):
import sys, random, subprocess
proc = subprocess.Popen(sys.argv[1:], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
def p(x):
proc.stdin.write(x+'\n')
proc.stdin.flush()
wordlist=[]
f=open('wordlist.txt', 'r')
for i in f:
wordlist.append(i[:-1] if i[-1]=='\n' else i)
# wordlist=[i[:-1] for i in f]
random.shuffle(wordlist)
score=0
totalerr=0
for s in wordlist:
s2=[]
for i in s:
s2.append('_')
err=0
p(''.join(s2))
while err<6 and '_' in s2:
c=proc.stdout.readline().strip()
nomatch=True
for i in range(0, len(s)):
if s[i]==c:
s2[i]=c
nomatch=False
if nomatch:
err+=1
totalerr+=1
p(''.join(s2))
if err<6:
score+=1
p('END')
sys.stderr.write('score is '+str(score)+', totalerr is '+str(totalerr)+'\n')
Stosowanie: python ./game.py [yoursolverprogram]
Przykład: python ./game.py ruby ./solver.rb
Powinno to działać jak stary program oceniania, ale nie zależy od nazwanych potoków, więc może działać na innych platformach. Jeśli interesuje Cię stara wersja, zapoznaj się z historią wersji.
źródło
subprocessz zewnętrznego fifo do prowadzenia gry? W ten sposób kod będzie działał dla innych systemów operacyjnych (na przykład Cygwin w systemie Windows). Otogame.pyzmodyfikowano, aby użyćsubprocessdo uruchomienia programu o nazwie podanej w wierszu polecenia: gist.github.com/nneonneo/d173f8888e1ea0c6fe37 . Użyj go jakopython game.py <program> [args]nppython game.py python hangman.py.Odpowiedzi:
Python 2, wynik = 2111
Uruchom z
python -u. (Do testowania z danym kontrolerem,.python ./game.py python -u ./solver.py) Jest to 2044 bajtów kodu + 1 dla-u= 2045 bajtów.Wynik
Jak to działa
Program zamienia wszystkie
_s na1s w bieżącym stanie, traktuje wynik jako liczbę całkowitą 36 i przyjmuje to modulo 1879, dając nam surową funkcję skrótu. Wybiera literę do odgadnięcia, indeksując tę wartość skrótu w długi ciąg liter. Jeśli już odgadł tę literę wcześniej, zmniejsza moduł o 6 (więc zawsze pozostaje względnie pierwszy do 36) i wybiera inną literę, powtarzając, aż znajdzie literę, której jeszcze nie odgadł.Zaprojektowałem tę strategię tak, aby zawierała wiele modyfikowalnych zmiennych (pojedyncze litery długiego łańcucha), z których większość będzie miała niewielki wpływ na końcowy wynik. To sprawia, że dobrze nadaje się do optymalizacji stylu wspinaczki - użyłem Diverified Late Acceptance Search .
Python 2, wynik = 2854
Dzięki liberalnemu wykorzystaniu bajtów niedrukowalnych i wbudowanej kompresji możemy wycisnąć o wiele więcej informacji.
Dekoduj za pomocą
xxd -ri uruchom zpython -u. (Do testowania z danym kontrolerempython ./game.py python -u ./solver.py,.) Jest to 2047 bajtów kodu + 1 dla-u= 2048 bajtów.Wynik
źródło
Python: 2006 bajtów, wynik = 1501
1885 bajtów, wynik = 13371961 bajtów, wynik = 1207Oto moje zgłoszenie:
Wynik wyjściowy:
Ten program jest w pełni deterministyczny. Olbrzymi obiekt blob (będący fragmentem
zlibskompresowanych danych w formacie base 64 ) jest listą drzew decyzyjnych (jedno drzewo na długość słowa). Każde drzewo decyzyjne koduje kompletne drzewo binarne o głębokości od 2 do 5. Każdy węzeł wewnętrzny jest pojedynczym znakiem, a decyzja jest podejmowana na podstawie tego, czy znak jest obecny w słowie kata.Każdy węzeł liścia drzewa binarnego zawiera zoptymalizowaną tabelę częstotliwości specyficzną dla tej gałęzi wyszukiwania drzewa. Tabela jest specjalnie zoptymalizowana, aby sprzyjać uzupełnianiu niektórych słów, a jednocześnie całkowicie ignorować inne (do których nie można dotrzeć z powodu ograniczonego budżetu „awarii”). Tabela nie jest zoptymalizowana w celu zminimalizowania błędów, a zatem całkowita liczba programów w programie jest wysoka pomimo (względnie) dobrego wyniku.
Optymalizator, który nie został pokazany, wykorzystuje niedeterministyczny nieliniowy optymalizator wykorzystujący losową strategię spadku gradientu do utworzenia tabel częstotliwości.
źródło
range(4)możesz go zastąpić, pod[1]*4warunkiem, że tak naprawdę nie musisz używać wartościi.decode('zip')zamiastdecode('zlib')Rubin
Wspólne zgłoszenie od użytkownika PragTob i mnie.
Wynik:
Ma 1672 znaki i nie jest jeszcze golfem, więc mamy dużo miejsca na ulepszenia algorytmu.
Najpierw przechowujemy skrót częstotliwości znaków (obliczony z listy słów) pogrupowanych według długości słowa.
Następnie w każdej rundzie po prostu sortujemy wszystkie postacie według częstotliwości dla bieżącej długości i wypróbowujemy je od najbardziej popularnej do najmniej popularnej. Stosując to podejście, najwyraźniej zawodzimy każde pojedyncze słowo, które ma nawet tylko średni wspólny charakter.
źródło
score is 625, totalerr is 23196Twój aktualny algorytm jest nadal aktualny? Próbowałem podobnego i dostałem tylko maksymalnie 300.Aktualizacja Korzystając z metody podobnej do @nneonneo, docieram do tego kodu, dokładnie 2047 znaków .
Wynik:
Kod:
Stary wpis
Wynik:
Nie jest to średnia, ponieważ ten algorytm jest deterministyczny, tzn. Zawsze daje taki sam wynik dla każdej tasowanej listy słów.
Oto mój wpis w Pythonie 2.7; w golfa (717 znaków)
Wykorzystuje to podobny pomysł jak @ m.buettner, przechowując uporządkowaną listę liter, po której zostaną wykonane domysły. Ale to nie wykorzystuje bezpośrednio danych częstotliwości, po prostu próbuje prawie każdej możliwej permutacji liter i symuluje grę, a na końcu przyjmuje permutację, która daje najlepszy wynik.
Ta wersja jest zoptymalizowana przy użyciu 9 pierwszych liter, więc dla słów 2-literowych i 3-literowych permutacja jest już optymalna w klasie algorytmów, w której informacje z poprzednich danych wejściowych są ignorowane. Obecnie nadal uruchamiam kod dla 10 pierwszych liter, optymalizując 4-literowe słowa (i znajduję lepsze rozwiązanie dla dłuższych słów).
niewłaściwy wpis
Dla mojego testu porównawczego, oto kod, który wykorzystuje pełne drzewo decyzyjne, 11092 znaków.
Wynik:
Kod:
źródło
Perl, 1461 bajtów, wynik = 1412, totalerr = 21050
(Uwaga: po usunięciu sporo opcjonalnych białych znaków ma 1461 bajtów. Jak wydrukowano, jest około sto cięższy, ale wciąż znacznie poniżej 2000.)
Wypróbowałem kilka bardziej „subtelnych” podejść, ale w końcu pokonałem je wszystkie. Te dwa ciągi danych to po prostu uszeregowane listy znaków, które najprawdopodobniej następują po każdym znaku, oraz znaków, które najprawdopodobniej poprzedzają każdy znak (z cyframi, które nie występują na liście słów, w ogóle nie są reprezentowane).
<i>są używane do przedstawienia początku i końca słowa. Jako przykład"w[aiehonrlsdtkfy]"oznacza, że „wa” jest bardziej powszechne niż „wi” jest bardziej powszechne niż „my” itp.%d, Mapowanie do przodu obejmuje globalny ranking przechowywany jako$d{''}. Jest używany w miejscach, w których są dwie niewiadome z rzędu lub gdzie wszystkie digrafy na liście słów są wyczerpane (więc musimy mieć do czynienia ze słowem nie z listy słów).Za każdą nieznaną pozycję w słowie, patrzy na poprzedni znak, daje każdej możliwej następnej postaci wynik, zaczynając od 180 dla najwyższego miejsca, a malejąc do 80 na końcu listy; to samo dzieje się z następującą postacią. Wszystkie wyniki dla wszystkich postaci są sumowane i wybierany jest ten z najwyższym wynikiem.
Po odgadnięciu litery jest ona usuwana bezpośrednio z tabel rankingu, więc nie można jej odgadnąć ponownie (dopóki nie zaczniemy nowego słowa i ponownie zainicjalizujemy tabele).
Aktualizacja: zyskałem mnóstwo punktów, naprawiając błąd (nie usuwaliśmy liter z odwrotnej tabeli) i zmieniając sposób, w jaki punkty spadają, gdy schodzimy na dół listy.
źródło
Python: 2046 bajtów, wynik = 1365
wynik to 1365, totalerr to 21343
Znaczna część kodu zapożycza się z przesłania pytona przez nneonneo (bez którego nie dostałbym tego poniżej limitu 2048 bajtów). Początkowo myślałem, że powinno to uzyskać około 200 więcej, ale odkryłem błąd w moim narzędziu do tworzenia ciągów danych. Teraz to naprawiono, mój wynik jest znacznie bardziej rozsądny 1365.
Zamiast tworzyć drzewa binarne na podstawie długości, stworzyłem pojedyncze drzewo binarne do przechowywania informacji o częstotliwości. Drzewo nie ma jednolitej głębokości, ponieważ nie ma sensu przechowywania informacji o częstotliwości dla niczego głębszego niż sześć błędnych domysłów (ale poprawne domysły mogą teoretycznie mieć dwanaście głębokości dla „znacznie” i „niewygodne”). Po tym niezgrabnie ukształtowanym drzewie porusza się kod silni (właściwie przy użyciu funkcji kombinacji ). Aby łańcuch danych był bardziej ściśliwy, uzupełniałem wszystkie nieużywane indeksy znakiem „s”.
Użyłem skryptu, aby obliczyć dobre ciągi do przechowywania jako d, a jeśli ktoś może zagrać w kilka innych znaków z pozostałej części skryptu, oto kilka zamienników, które powinny dać lepsze wyniki. Górny wiersz to ciąg kodowany w powyższym programie.
Skrypt, którego użyłem do wygenerowania ciągów danych, jest tutaj , na wypadek, gdyby był użyteczny dla każdego!
źródło
distinctwyjście programu było w kolejnościeitanogsuc, co oznacza, że w jakiś sposób przestaje dawać wyjście, nawet jeśli zgaduje tylko niepoprawnie 5 razy.Język programowania D jest moim narzędziem wyboru do tego wyzwania.
Wystarczy, że przekroczysz limit 2048 bajtów, choć w niektórych częściach jest nieco golfowy, aby odliczyć bajt, wszystkie ciężkie podnoszenie pozostaje doskonale czytelne. Ten solver nie jest zbyt dobry w swojej pracy i spodziewam się, że zostanie łatwo pokonany, ale to tylko po to, aby piłka się potoczyła. Zrób coś, żeby tak rzec.
EDYCJA 1 :
Jak już wspomniano, oryginalny kod ma skłonność do okropnej śmierci, gdy wyczerpuje wszystkie samogłoski. Ponieważ nie działa poprawnie, zastąpiłem go nieco bardziej brutalnym podejściem do losowego zgadywania.EDYCJA 2 : Oryginalny kod został naprawiony i teraz pozostaje w mocy.
Ocena :
25.7; totalerr: 24,529.9 (average of 10 tests).Jak to działa
Ten solver jest całkowicie losowy. Nawet przypadkowość jest przypadkowa, zabawne czasy!
Gdy program odbierze dane wejściowe, zgadnie jeden losowy znak, którego jeszcze nie odgadł, i wyśle go do STDOUT.
Algorytm zgadywania działa w ten sposób:
źródło
./test.d(44): Error: cannot implicitly convert expression (uniform(0, Letters.length, rng)) of type ulong to int. Udało mi się to naprawićcast(int). Po 10 uruchomieniach twój średni wynik to 22,4 słowa z 24529,1 błędnymi domysłami. Przeprowadzę ponowny test, jeśli naprawisz bardziej zaawansowaną wersję :) Miłej zabawyRozwiązanie JAVASCRIPT + HTML
źródło