Po konkursie drugim

Już po konkursie i jego omówieniu otrzymałem dwa kolejne rozwiązania.

Rozwiązanie pierwsze

Z autorem pierwszego sporo czasu spędziłem na dyskusji, bo okazało się, że jego rozwiązanie daje lepsze wyniki niż program p12! Wprawdzie różnica była na poziomie błędu statystycznego, ale jednak zawsze ze wskazaniem na pokonkursowy program! Zmarnowałem sporo czasu autorowi, bo nawet nie próbowałem zrozumieć skąd się to bierze, gdyż cały czas zastanawiałem się, co by mogło być nie tak w tym p12, aż w końcu zrozumiałem: naszym sukcesem nie jest zdarzenie polegające na tym, że wszystkie kolejne liczby będą mniejsze od danej! Sukcesem jest zdarzenie będące sumą dwóch rozłącznych zdarzeń:

  1. wszystkie kolejne liczby będą mniejsze od danej
  2. będzie liczba większa i w kolejnych próbach prawidłowo ją wytypujemy!

Prawdopodobieństwa tych zdarzeń wynoszą odpowiednio p1 i p2. Możemy zapisać znów warunek, że prawdopodobieństwo naszego sukcesu musi być większe od prawdopodobieństwa zdarzenia przeciwnego:

p1+p2 > 1-(p1+p2)

co, po uproszczeniu daje

p1+p2 > 0.5

p1 to znane nam już xn, (gdzie n–liczba liczb, których jeszcze nie znamy), więc

xn + p2 > 0.5

Ponieważ p2 >= 0, więc wynika z tego, że warto się zatrzymywać dla liczb nieco mniejszych niż (jak pierwotnie) pierwiastek n-tego stopnia z 0.5.

Obliczenie p2 nie jest banalne, gdyż p2 jest funkcją dwóch zmiennych: f(x, n).

Autor nadesłanego rozwiązania (akrasuski1) podszedł do tego nieco inaczej, bo porównywał te dwa prawdopodobieństwa i w zależności od tego, które z nich było większe, podejmował decyzję: jeśli większe było prawdopodobieństwo, że nie będzie już większych liczb, to typował x; a jeśli większe było prawdopodobieństwo, że jednak może wystąpić liczba większa i ją dobrze wytypujemy, czekał. Oczywiście, przy następnej liczbie sytuacja się powtarzała.

Linki do rozwiązanie zamieszczam poniżej, a ich mnogość tłumaczę tym, że ich autor włożył naprawdę dużo wysiłku, by przekonać mnie do tego, co w końcu wydaje się oczywiste.

http://pastebin.com/8TQHDXFx
http://pastebin.com/h3c27wpK
http://pastebin.com/7rCWnwuD
Opis rozwiązania
http://pastebin.com/hiwxmUDS
http://pastebin.com/9TdJ6cC8

No i jeszcze wyniki dla miliona zbiorów danych (N=3)

 akrasuski1 accuracy for N=3: 68.437600% (1000000 runs)
         My accuracy for N=3: 68.412100%

Rozwiązanie drugie

Przepraszam autora (pingwindykator), że nie omówię szczegółowo tego rozwiązania, ale P.T. Czytelników zachęcam do zapoznania się z kodem:

https://github.com/pingwindyktator/guessing_machine

Konkurs drugi – wyniki

Wyniki konkursu ogłosiłem wcześniej tu: http://pastebin.com/m1SgLB0T, ale zauważyłem tam sporo literówek i błędów gramatycznych. Głównym błędem było jednak porównanie programów p10 i p11, więc niniejszym prezentuję poprawioną wersję.

Konkurs został ogłoszony tu: http://pastebin.com/SbEzsxtG

Za pomocą programu opisanego powyżej wygenerowałem 10000 plików z danymi. W plikach wystąpiły wszystkie możliwe wartości N, czyli od 1 do 1000.

Nadesłane funkcje były testowane za pomocą programu http://pastebin.com/Gr546BH6, który był uruchamiany (w większości przypadków) w pętli:

for i in $(seq -w 10000); do ./a.out < /home/wiechu/konkurs/B/00data/$i; done | grep Trafiony | wc -l

Nadesłano jedenaście rozwiązań, nie nadesłano jednego. Oto rozwiązania:

Kategoria: hakerskie

Program p01 – http://pastebin.com/m9UgFjW4

Autor próbował następującej sztuczki: dostać się przez stos do zmiennych z main() i w ostatnim wywołaniu ustawić real_max i your_max na tę samą wartość. Nie wiem tylko, dlaczego uparł się ustawiać je na ostanią wartość x, skoro znał już wartość największą. Oszustwo niemal doskonałe, ale nie działa przy kompilacji z flagą -O3, więc skuteczność 0%.

Program p02 – http://pastebin.com/P5dX4Pg9

Gdyby ktoś był ciekaw, jak dowiedzieć się, z jakimi parametrami został wywołany program pod linuksem, to na pewno zainteresuje się tym rozwiązaniem. Program testowy jednak wywoływany był bez parametrów, więc skuteczność 0%.

Program p03 – http://pastebin.com/XAcbFQzr

Kolejnym pomysłem było przysłonięcie funkcji fopen(). Niestety, mój kompilator odmawiał dalszej pracy przy linijce z funkcją fopen_s(). Skuteczność 0%.

Program p04 – https://gist.github.com/vesim987/1c0df8d01e3018e74d9a9218353b9aef

Program jest tak hakerski, że nie odważę się go komentować, ale niestety również bazuje na założeniu, że dane będą w otwartym pliku. Poprosiłem autora o komentarz i opis możecie podziwiać powyżej oraz tu: http://pastebin.com/arG3S9BL Skuteczność 0%

Kategoria: siłowe

Program p05 – http://pastebin.com/A2eTwchd

Pomysł autora odczytuję następująco: jeśli odgadniemy ziarno, które powoduje wylosowanie liczby N, to będziemy też znali kolejne losowane liczby i w ten sposób znajdziemy (bez odgadywania) największą. Niestety, daną liczbę N <1,1000> otrzymamy dla około dwóch milionów przypadków, więc… Program trafił 84 z 10000 przypadków, a wynik jest tak dobry tylko dlatego, że napędzają go pliki z N=1, N=2, N=3.

Program p06 – http://pastebin.com/0sDfTrYE

Program p07 – http://pastebin.com/0GJ7JN29

Dwaj kolejni autorzy kombinowali jak autor programu p05, ale dodatkowo sprawdzali, czy dane ziarno spowoduje nie tylko wygenerowanie N, ale też pierwszej liczby x. Oczywiście, żadnego z nich nie uruchomiłem dla 10000 danych testowych, gdyż zależało mi, by wyniki konkursu ogłosić jeszcze w tym roku.

Uruchomiłem któryś z nich dla pierwszego zestawu danych (N=771) i działał na moim laptopie około pół godziny i trafił. Uruchomiłem go dla N=1 i wtedy też trafił (sic!), ale działał przez godzinę.

Wygląda na to, że mamy programy, które na 100% trafiają, ale tylko w dane wygenerowane moim przykładowym programem. Przypomina mi to niezwykle skuteczną maszynę, którą wymyślił Dijkstra. Maszyna ta znajdowała największy wspólny podzielnik liczb 111 i 259. Urządzenie Dijkstry składało się z dwóch tekturek, ale ja je uproszczę do jednej tekturki. Na jednej stronie piszemy „NWP(111,259)”, a na drugiej 37. I teraz ilekroć chcemy poznać NWP(111,259) odwracamy tekturkę i odczytujemy wynik. Podobieństwo widzę w tym, że tak jak tej maszyny Dijkstry, tak i tych programów trudno użyć do czegoś innego niż rozwiązywanie ograniczonego zestawu danych. Gdybym w generatorze napisał „%f” zamiast „%.15f”… no ale nie napisałem.

To jest czyste marudzenie. Był określony zestaw danych, są rozwiązania. Czy jednak zawsze te programy zadziałają? Niestety nie. Skompilowane kompilatorem (na przykład pod windows – warunki konkursu mówiły, w jakim systemie będą generowane dane, a nie w jakim będą testowane konkursowe programy) linkującym do innej funkcji rand() nie zadziałają na pewno. (Na szczęście nikt nie wpadł na to, by źródła funkcji rand() z libc zamieścić w pliku guess_max_fn.c)

Tak więc mamy:
Linux circa 100%
Windows circa 0%

Średnio: 50%

Kategoria: całkiem nieźle, czyli one-linery

Program p08

int guess_max(double x, int N, int count)
{
     return ((double)(N - count)*(double)(1 - x))<0.5;
}

Całkiem niezła funkcja, która im bliżej końca, zadowala się coraz mniejszym x. Skuteczność też niezła: 5296 trafień, czyli ~53%. A najlepsze jest to, że będzie działać równie skutecznie pod dowolnym systemem operacyjnym i dla dowolnie wygenerowanych danych – tym generatorem, innym, kostką lub monetą!

Program p09 – http://pastebin.com/YLejtg2g

Autor zawarł dwa w jednym. Zacznijmy od – jak to nazwał – naginania rzeczywistości. Rzeczywistość jest taka, że u mnie kompilacja się kładzie w linii 101 i może bym nawet dociągnął ten nieszczęsny stropts.h, ale z kodu widzę, że to jakieś kombinacje z macaniem po pliku FILE *f, a to już przerabialiśmy i skutki były mizerne.

Ciekawsze jest drugie rozwiązanie, które da się sprowadzić znów do one-linera:

return ( x >= 1.0-1.0/(N-(count-1)) );

Skuteczność nieco porównywalna z p08: 5311 czyli ~53%. Komplementów, które napisałem przy programie p08 nie będę powtarzał.

Może kiedyś przeprowadzę więcej prób, albo spróbuję znaleźć teoretyczne uzasadnienie, która funkcja jest lepsza i dlaczego, ale już nie dziś.

Przerywnik – historia zadania

Ponad 30 lat temu do naszego pokoju w akademiku zajrzał Lechu i powiedział: „Dostałem fajne zadanie na laborkę. W czytniku znajduje sie N kart perforowanych z liczbami od 0 do 1. Mój program ma je czytać i zatrzymać się na największej. Lecę programować”.

Zdziwiłem się: „Co on tam chce programować? Wystarczy sprawdzić, czy prawdopodobieństwo, że wśród pozostałych liczb wszystkie będą mniejsze od x, jest większe od zdarzenia przeciwnego” i dodałem „Dwa karo”, bo akurat graliśmy w brydża.

Robert spojrzał w swoje karty, zastanowił się, potem popatrzył na mnie i powiedział: „Warto też pamiętać, jaka największa już była, bo jeśli teraz mamy mniejszą od niej, to nie ma co na nią stawiać”.

Lechu, Robert i ja studiowaliśmy na wydziale elektroniki i choć żaden z nas nie był wtedy studentem informatyki, to trafiały nam się ciekawe zadania.

Kategoria: probabilistyczna

Program p10

One-liner, więc dam tu:

#include <math.h>

int guess_max(double x, int N, int count)
{
    return (1.0 - pow((double)(x), (double)(N - count))) < 0.5;
}

To jest właśnie to, o czym mówiłem. Prawdopodobieństwo p, że wśród m liczb wszystkie będą mniejsze od x (dla x <0,1>)

p = x^m

i jednocześnie

p > (1-p)

co daje:

x^m > 0.5

Autor zapisał to nieco inaczej, ale w sumie to na jedno wychodzi.

Skuteczność? 5455 trafień, czyli ~55%.

Program p11 – http://pastebin.com/wvTGPkc4

Identyczne z p10 rozwiązanie, tyle że autor nie wykorzystał funkcji pow(), a zaimplementował ją samodzielnie. Skuteczność identyczna: 5455 trafień, czyli ~55%.

Dyskusyjne jest tylko użycie relacji >= 0.5 w miejscu > 0.5, bo intuicyjnie lepiej stawiać na to, czego prawdopodobieństwo jest większe, ale jak jest naprawdę?

Rozważmy wybór dla N=2 i naturalnego x z przedziału <0,10>. Niech pierwsza liczba x=5. Program p10 nie postawi na tę liczbę, program p11 ją wybierze. Jeżeli druga liczba również będzie równa 5 i wtedy p11 trafił już wcześniej, a p10 wybierze przy drugim wywołaniu. Ponieważ prawdopodobieństwo, że drugą liczbą będzie [0,1,2,3,4] jest równe prawdopodobieństwu, że będzie to liczba [6,7,8,9,10], więc w tylu samo przypadkach p11 dobrze obstawi pierwszą liczbę (p10 w tych przypadkach nie trafi), co polegnie na drugiej (którą dobrze wybierze p10). Dla x różnego od 5 (a ściślej: dla zbiorów, w którym nie zachodzi warunek p^m=0.5) sprawa jest oczywista i niewarta dyskusji.

Wygląda na to, że programy będą zgadywały równie skutecznie, choć dla pewnych specyficznych zestawów danych będą się myliły w innych, choć równie licznych przypadkach.

Kategoria: programy nienadesłane

Program p12

#include <math.h>

int guess_max(double x, int N, int count) {
  static double prev_max = 0;
  if ( x < prev_max ) /* Warto też pamiętać, jaka największa już była, bo jeśli teraz mamy mniejszą od niej, to nie ma co na nią stawiać */
     return 0;
  prev_max = x;

  return pow(x, N-count) > 0.5; /* Wystarczy sprawdzić, czy prawdopodobieństwo, że wśród pozostałych wszystkie będą mniejsze od x jest większe od zdarzenia przeciwnego */
}

A jego skuteczność: 5843, czyli ~58%

Gawędy teoretyczne

Jaką maksymalną skuteczność można osiągnąć?

Dla N=1 mamy 100% trafności.

Dla N=2 stawiamy na pierwszą liczbę, jeśli jest większa od 0,5. Trafność wynosi 75%, co pokazałem na rysunku http://imgur.com/sZfjeI8

Dla N=3… tu już jest trudniej, bo zaczyna działać warunek Roberta, więc obliczenia zostawiam P.T. Czytelnikom jako zadanie domowe. Podpowiem tylko, że w 100 tysiącach plików z N=3 programy p10 i p11 trafiły ~68%.

Dla N=4… szkoda mi czasu na kolejne testy, ale ufunduję nagrodę temu, kto przyśle mi wzór na probabilistyczną skuteczność dla dowolnego N.

Werdykt

Najlepsze wyniki daje program p12, ale nikt go nie nadesłał.

Nie pozostaje mi nic innego, jak nie przyznanie pierwszej nagrody.

Postanowiłem jednak ufundować dwie nagrody pocieszenia dla autorów programów p10 i p11. Autorami są odpowiednio: mrx1 i google13.

Nagrodą pocieszenia jest książka napisana przez Gospodarza konkursu, którą ufundowałem w http://ksiegarnia.pwn.pl/Zrozumiec-programowanie,114589762,p.html

Pozdrawiam wszystkich – tych którzy nadesłali rozwiązania i tych którzy ich nie nadesłali.