Wprowadzenie
W tym wyzwaniu otrzymujesz listę nieujemnych liczb zmiennoprzecinkowych narysowanych niezależnie od pewnego rozkładu prawdopodobieństwa. Twoim zadaniem jest wywnioskować ten rozkład na podstawie liczb. Aby wyzwanie było wykonalne, masz tylko pięć dystrybucji do wyboru.
U
, równomierny rozkład w przedziale [0,1].T
, rozkład trójkątny w przedziale [0,1] z trybem c = 1/2.B
, rozkład beta w przedziale [0,1] o parametrach α = β = 1/2.E
, rozkład wykładniczy w przedziale [0, ∞) ze współczynnikiem λ = 2.G
, rozkład gamma w przedziale [0, ∞) o parametrach k = 3 i θ = 1/6.
Zauważ, że wszystkie powyższe rozkłady mają dokładnie 1/2.
Zadanie
Dane wejściowe to tablica nieujemnych liczb zmiennoprzecinkowych o długości od 75 do 100 włącznie. Twój wynik będzie jedną z literUTBEG
, na podstawie której z powyższych rozkładów, jak się domyślacie, pochodzą liczby.
Zasady i punktacja
Możesz podać pełny program lub funkcję. Standardowe luki są niedozwolone.
W tym repozytorium znajduje się pięć plików tekstowych, po jednym dla każdej dystrybucji, każdy o długości dokładnie 100 linii. Każda linia zawiera rozdzielaną przecinkami listę od 75 do 100 liczb zmiennoprzecinkowych narysowanych niezależnie od rozkładu i obciętych do 7 cyfr po przecinku. Możesz zmodyfikować ograniczniki, aby pasowały do natywnego formatu macierzy Twojego języka. Aby kwalifikować się jako odpowiedź, Twój program powinien poprawnie sklasyfikować co najmniej 50 list z każdego pliku . Wynik poprawnej odpowiedzi to liczba bajtów + całkowita liczba błędnie sklasyfikowanych list . Najniższy wynik wygrywa.
Odpowiedzi:
Julia,
6062 bajtów +252 błędy =8264To jest dość proste. Wariancja rozkładów jest w większości różna - wynosi 1/4 dla wykładniczej, 1/8 dla beta, 1/12 dla gamma i munduru oraz 1/24 dla trójkąta. Jako taki, jeśli użyjemy wariancji (tutaj wykonanej przy użyciu
std
odchylenia standardowego, pierwiastka kwadratowego wariancji) do ustalenia prawdopodobnego rozkładu, musimy jedynie zrobić więcej, aby odróżnić gamma od jednolitej; w tym celu szukamy wartości większej niż 1 (używającany(k.>1)
) - to powiedziawszy, sprawdzamy zarówno wykładniczy, jak i gamma, ponieważ poprawia to ogólną wydajność.Aby zapisać bajt, indeksowanie ciągu
"EGTBU"
odbywa się zamiast bezpośredniej oceny ciągu w ramach warunków warunkowych.W celu przetestowania zapisz pliki txt w katalogu (zachowując nazwy bez zmian) i uruchom Julia REPL w tym katalogu. Następnie dołącz funkcję do nazwy jako
i użyj następującego kodu, aby zautomatyzować testowanie (to przeczyta z pliku, skonwertuje na tablicę tablic, użyje funkcji i wyświetli dane dla każdego niedopasowania):
Dane wyjściowe będą składać się z wierszy zawierających przypadek niedopasowania, prawidłowego rozkładu -> określonego rozkładu i obliczonej wariancji (np.
13 G->E 0.35008999281668357
Oznacza, że 13 wiersz w G.txt, który powinien być rozkładem gamma, jest określony jako wykładniczy rozkład, przy odchyleniu standardowym wynoszącym 0,35008999 ...)Po każdym pliku wyświetla również liczbę niezgodności dla tego pliku, a następnie na końcu wyświetla również całkowitą niezgodność (i powinien odczytać 2, jeśli działa jak wyżej). Nawiasem mówiąc, powinien mieć 1 niezgodność dla G.txt i 1 niezgodność dla U.txt
źródło
R,
202 192 184 182 162 162154 bajty + 0 błędówJest to oparte na formule bayesowskiej P (D = d | X = x) = P (X = x | D = d) * P (D = d) / P (X = x), gdzie D jest rozkładem, a X jest losową próbką. Wybieramy d tak, że P (D = d | X = x) jest największe z 5.
Zakładam, że wcześniejszy (tj. P (D = di) = 1/5 dla i w [1,5]), co oznacza, że P (D = d) w liczniku jest taki sam we wszystkich przypadkach (a mianownik miałby tak czy inaczej we wszystkich przypadkach), więc możemy odstawić wszystko poza P (x = X | D = d), które (z wyjątkiem rozkładu trójkątnego) upraszczają funkcje natywne w R.
bez golfa:
Zauważ, że wersja bez golfa nie jest dokładnie równoważna z wersją z golfem, ponieważ pozbycie się mianownika pozwala uniknąć przypadku Inf / Inf, który występuje, jeśli pozwolisz, aby rozkład beta był w zamkniętym przedziale [0,1] zamiast (0, 1) - podobnie jak przykładowe dane. Dodatkowa instrukcja if poradziłaby sobie z tym, ale ponieważ jest to wyłącznie w celach ilustracyjnych, prawdopodobnie nie warto dodawać złożoności, która nie jest sednem algorytmu.
Dzięki @Alex A. za dodatkowe redukcje kodu. Specjalnie dla what.max!
źródło
{
i jeden przed zamknięciem}
, i aliasingprod
, np.P=prod
Potem robiącP(dunif(x))
itp. Funkcja nie potrzebuje nazwy, aby być poprawnym przesyłaniem, więc możesz usunąćp=
. Również świetna robota. :)which.max(c(u,r,b,e,g))
zamiastc(u,r,b,e,g)==max(c(u,r,b,e,g))
.function(x){c("U","T","B","E","G")[which.max(lapply(list(dunif(x),sapply(x,function(y)max(0,2-4*abs(.5-y))),dbeta(x,.5,.5),dexp(x,2),dgamma(x,3,6)),prod))]}
CJam, 76
Kod źródłowy ma 43 bajty i błędnie klasyfikuje 33 listy.
Weryfikacja
Pomysł
Odróżnienie rozkładu wykładniczego i gamma od pozostałych jest łatwe, ponieważ są to jedyne rozkłady, które przyjmują wartości większe niż 1 .
Aby wybrać między gamma , wykładniczym i innymi, przyjrzymy się drugiej najwyższej wartości próbki.
Jeśli leży w [1,5, ∞) , domyślamy się gamma .
Jeśli leży w [1, 1.5) , domyślamy się wykładniczego .
Jeśli leży w [0, 1) , mamy trzy pozostałe możliwości.
Pozostałe rozkłady można różnicować poprzez procent wartości próbek, które leżą blisko średniej ( 0,5 ).
Długość próbki dzielimy przez liczbę wchodzących wartości (0,3, 0,7) i sprawdzamy wynikowy iloraz.
Jeśli to leży (1, 2) , domyślamy się trójkątny .
Jeśli to leży (2, 3) , domyślamy się munduru .
Jeśli leży w (3, ∞) , domyślamy się wersji beta .
Kod
źródło
Matlab,
428328 bajtów + 33 błędnie sklasyfikowanyTen program w zasadzie porównuje rzeczywisty CDF z oszacowanym, biorąc pod uwagę dane, a następnie oblicza średnią odległość między nimi: Myślę, że obraz wyjaśnia więcej:
Dane pokazane na tym obrazku pokazują dość wyraźnie, że należy on do rozkładu turkusowego, ponieważ jest dość zbliżony do tego, więc w zasadzie to robi mój program. Prawdopodobnie można go nieco pograć w golfa. Dla mnie było to przede wszystkim wyzwanie koncepcyjne, niezbyt golfowe.
Podejście to jest również niezależne od wybranych plików pdf, działałoby dla każdego zestawu dystrybucji.
Poniższy (nie golfowy) kod powinien pokazywać, jak to się robi. Wersja do gry w golfa jest poniżej.
Wersja w pełni golfa:
źródło
Perl, 119 bajtów + 8 błędnych klasyfikacji = 127
Podjąłem małe drzewo decyzyjne dotyczące trzech funkcji:
Wywoływany z
perl -F, -lane -e '...'
. Nie jestem pewien, czy powinienem dodać karę za niestandardowe parametry. Gdyby przecinki były spacjami, myślę, że mógłbym uciec bez znaku -F,Lekko sformatowane wyjście (bez flagi -l) to:
źródło
Python, 318 bajtów + 35 błędnych klasyfikacji
Pomysł: rozkład zgaduje się na podstawie wartości p testu Kołmogorowa-Smirnowa.
Test
źródło