-
Notifications
You must be signed in to change notification settings - Fork 81
[PL] 5. Paczka z biblioteczką
Często zdarzają się sytuacje, gdy w zadaniu program nie powinien posiadać pełnych informacji. Informacje te musi stopniowo uzyskiwać, poprzez różnego rodzaju zapytania. Wtedy oczywiście nie może być możliwe wczytanie takich danych od razu na wejściu. Potrzeba więc sposobu na interakcję z programem w trakcie jego działania.
Taką możliwość dają biblioteczki. Biblioteczka to zewnętrzny kod, napisany przez autora zadania, łączony z rozwiązaniem uczestnika w trakcie sprawdzania. Program może wtedy wywoływać funkcje z biblioteczki, bądź na odwrót, co daje nam możliwość interakcji. Rozwiązuje to nasz problem, gdyż biblioteczka może regulować dostęp uczestnika do informacji podanych w teście.
Weźmy jedno z podstawowych zadań na wyszukiwanie binarne. Bardzo często naukę powyższego zagadnienia zaczyna się od następującego problemu: "Gramy w grę. Ja myślę o liczbie od 1 do 100, a Ty możesz pytać, czy wybrana przez Ciebie liczba jest mniejsza, większa, czy równa. Zgadnij w jak najmniejszej liczbie prób liczbę, o której myślę".
Często uczniowie piszą program, który wypisuje pytania na standardowe wyjście, a odpowiedzi wpisywane są na standardowe wejście z klawiatury. W ten sposób program ten gra w grę ze swoim autorem. Niestety, o ile wiele platform potrafi zasymulować coś takiego, to SIO2 nie posiada możliwości interakcji z programem uczestnika przez standardowe wejście/wyjście. Jednak nadal mamy możliwość, w lekko zmodyfikowanej formie, dać uczestnikom takie zadanie. Do tego będzie właśnie służyć nam biblioteczka!
Zadaniem uczestników będzie napisanie programu grającego w powyższą grę w interakcji z naszą biblioteczką. Żeby lepiej oceniać poprawność rozwiązań, zwiększymy zakres liczb do 10^6. Program będzie miał do dyspozycji tylko pytania "czy szukana liczba jest większa niż x", a ich liczba będzie ograniczona.
Przykładowe poprawne rozwiązania są w plikach gue.cpp i gue2.py.
Biblioteczka jest osobnym fragmentem programu komputerowego. Nie ma funkcji main, a jedynie funkcje potrzebne do odpowiadania na zapytania programu uczestnika.
Jest też możliwe, żeby to uczestnik pisał "pomocniczą" część kodu, podczas gdy program z funkcją main będzie zapewniony przez organizatorów. Nie będziemy jednak tego poruszać w tym tutorialu. Łatwo taki efekt uzyskać używając omawianego przez nas typu biblioteczki. Wystarczy w biblioteczce zdefiniować 2 funkcje: podajZapytanie i odpowiedzNaZapytanie. W ten sposób da się zasymulować drugi rodzaj zadania z biblioteczką, nie wgłębiając się w szczegóły techniczne z tym związane.
Biblioteczka musi umieć zrobić następujące rzeczy:
- Zainicjować się. W skład inicjalizacji wchodzą:
- Wczytanie danych z wejścia (tylko w ten sposób może posiadać różne dane dla różnych testów)
- Zainicjowanie wszelkich zmiennych, z których będzie korzystać
- Umieć odpowiedzieć na każde z dostępnych zapytań (w wypadku naszego zadania dostępne jest tylko jedno, ale nic nie stoi na przeszkodzie, by w innych zadaniach było ich więcej).
- Umieć zwrócić w szybkim czasie odpowiedź na zapytanie (jeśli biblioteczka obliczy odpowiedź w 1000 operacji, a użytkownik może zadać 1000 zapytań, to może on dostać werdykt "Przekroczenie limitu czasu" za samo używanie biblioteczki zgodnie z przeznaczeniem, co jest złym zachowaniem!).
- Sprawdzić, czy dane zapytanie jest poprawne (na przykład czy podana liczba nie jest spoza dopuszczalnego zakresu), czy nie zostało wywołane za wiele razy, czy została wywołana już funkcja inicjująca, ale też czy program nie powinien już się zakończyć (na przykład nie została już udzielona odpowiedź), oraz wszelkie potencjalne inne wymagania z treści zadania.
- Powinno się tak zaimplementować biblioteczkę, by jej czas działania był stabilny i taki sam dla testów podobnej wielkości. Warto żeby wszystkie zapytania (oprócz inicjalizacji/odpowiedzi) działały tak samo szybko, niezależnie od podanych argumentów. Dzięki temu, jako autorzy, możemy lepiej oszacować czas działania programu uczestnika i lepiej dobrać limity czasowe. Także należy zadbać, by biblioteczka zużywała zawsze tyle samo pamięci!
- Mieć funkcję do zwrócenia odpowiedzi.
- Musi ona wypisać wynik na wyjście oraz poinformować inne funkcje, że nie powinny być już wołane.
- Może ona również sprawdzić czy odpowiedź jest poprawna i wypisać taką informację, zamiast samego wyniku. O podejściach do wypisywania wyniku będzie więcej w późniejszej części poradnika.
Treść naszego zadania początkowo niczym nie różni się od innych treści. Jednak w opisie problemu należy zaznaczyć, że zadanie jest interaktywne.
Następnie powinny pojawić się następujące sekcje:
- Komunikacja: W tej sekcji powinna być dokładnie opisana funkcjonalność biblioteczki. Powinny być wymieniowe wszystkie funkcje, wraz z ich dokładną sygnaturą i wymaganiami przy ich wywołaniach. Warto także napisać, że użytkownik powinien wykonać odpowiednie polecenia na początku programu, żeby widzieć funkcje biblioteki. Należy także przypomnieć, że program nie może czytać i pisać po standardowym wejściu/wyjściu.
- Przykładowe wykonanie programu: Oczywiście potrzebny jest test przykładowy, jednak w tym formacie trzeba go podać zupełnie inaczej. Należy podać wszystkie wywołania funkcji, jakie robi przykładowy program, wraz z opisami co one powodują i co zwracają.
- Ocenianie: Ta sekcja nie jest obowiązkowa, ale warto ją dodać, zwłaszcza gdy warunki punktacji programu nie są oczywiste. Należy tu wymienić wszystkie dodatkowe warunki punktacji, specyficzne dla tego konkretnego zadania.
- Eksperymenty: Będziemy dopiero uczyć się, jak taki program skompilować i przetestować. Skoro dla nas to jest nieoczywiste, to co dopiero dla uczestników. Dlatego ta sekcja musi wszystko wyjaśniać, żeby byli w stanie uruchomić program u siebie.
Gotowa treść dostępna jest w pliku guezad.pdf.
Teraz czas zaimplementować całą potrzebną nam funkcjonalność. Będę tłumaczyć implementację dla języka C++, później wyjaśnię z czego to wynika. Należy skupić się na następujących aspektach:
- Wydajne i poprawne odpowiadanie na zapytania (nie chcemy żeby z winy naszej biblioteki uczestnik dostał mniej punktów niż powinien).
- Dbanie, by uczestnik poprawnie wywoływał funkcje. Należy pamiętać, że może on jako parametr funkcji podać zupełnie cokolwiek (i nawet nie z złośliwości, co popełniając błędy) i trzeba być na to gotowym. Także, jeśli wymagane jest, by funkcja init była wywołana tylko raz i jako pierwsza, to trzeba to wyegzekwować. W wypadku nieprzestrzegania przez program takiej reguły, można wypisać na standardowe wyjście informację o błędzie. Wtedy dalsze zachowanie programu nie ma znaczenia. Dlatego też zazwyczaj nie kończymy programu, aby wszelkie błędy wykonania wynikały tylko z rozwiązania uczestnika, a złą odpowiedź za niepoprawną obsługę biblioteczki dostał tylko przy bezbłędnym zakończeniu wykonania.
Nie musimy się martwić tym, że uczestnik zbyt długo nie wywoła jakiejś funkcji, albo będzie nadużywać swoich limitów pamięci, gdyż dalej dostanie on w takich wypadkach werdykty "Przekroczenie limitu czasu" lub "Błąd wykonania".
Jeżeli chcemy zwiększyć szanse na wychwycenie błędnych rozwiązań, możemy napisać biblioteczkę adaptacyjną. Najczęściej używa się tej techniki, gdy nie chce się przyznawać punktów rozwiązaniom randomizowanym.
Technika ta polega na zmienianiu rozwiązania w trakcie działania programu tak, by dalej było zgodne z poprzednimi zapytaniami, ale układać je "na złość" przy nowych zapytaniach. Weźmy przykład, w którym zgadywana jest liczba od 1 do 100. Wybrana liczba to 100. Pierwsze pytanie jest o 50, zwracana jest informacja "większa". Drugie pytanie jest o 99. Pechowo, odpowiedź "większa" natychmiast ujawni wynik, a przecież pytanie jest słabe, bo dla dowolnej liczby innej niż 100 daje bardzo mało informacji. Dlatego wynik zostaje zmieniony na 51, żeby "ukarać" program za to pytanie. Nie może być jednak zmieniony na 1, gdyż byłoby to sprzeczne z odpowiedzią udzieloną na pierwsze pytanie.
Taki sposób manipulacji rozwiązaniem jest dozwolony w zawodach algorytmicznych, chyba że w treści jest wyspecyfikowane, że rozwiązanie ustalane jest przed rozpoczęciem interakcji i nie zmienia się w trakcie działania programu. W naszym przypadku tak nie jest, więc skorzystamy z biblioteczki adaptacyjnej. Będziemy chcieli wychwycić rozwiązanie pytające o losowy element. Znając działanie wyszukiwania binarnego wiadomo, że w przybliżeniu program taki będzie korzystać z małej liczby zapytań. Część razy trafi pechowo (rozwiązanie będzie w większej połówce przedziału), zaś część razy szczęśliwie, więc istnieje ryzyko, że program zmieści się w limicie 20 zapytań. Nasza adaptacyjna biblioteczka zawsze ustawi rozwiązanie w większym z dwóch przedziałów utworzonych przez zapytanie. Dzięki temu dostajemy gwarancję, że rozwiązanie randomizowane zadziała nieoptymalnie.
W przykładowej paczce dodane jest randomizowane rozwiązanie gueb.cpp. Można zauważyć, że o ile na zwykłych testach radzi sobie całkiem dobrze, to w teście adaptacyjnym zadaje wyraźnie więcej pytań.
Mamy już gotową biblioteczkę w C++. Co z Pythonem? Teoretycznie trzeba napisać drugą, taką samą w tym języku. Jest to jednak męczące, a poprawne zaimplementowanie każdej z biblioteczek wymaga dobrej znajomości języka.
Jest jednak sposób żeby ominąć pisanie biblioteczki w Pythonie. Użyjemy narzędzia SWIG, by umożliwić Pythonowym programom korzystanie z biblioteczki w C++. Dzięki temu napiszemy jeden kod, a rozwiąże on wszystkie nasze problemy. W dużym skrócie stworzymy plik interfejsu guelib.i, a następnie używając narzędzia, wygenerujemy program guelib.py, który będzie przekierowywać zapytania do właściwej biblioteczki guelib.cpp.
Nie jest to konieczne rozwiązanie, jednak najprostsze i najszybsze w użyciu. Więcej informacji o tym narzędziu i sposobach korzystania z niego możne znaleźć tu.
Kolejne ważne pytanie to jak kompiluje się program z biblioteczką.
GCC bardzo dobrze radzi sobie z takimi zadaniami, dlatego wystarczy
podać mu jako argument plik do zlinkowania.
W ten sposób linijka:
g++ gue.cpp guelib.cpp -o gue
wystarczy nam, żeby skompilować nasz program.
Warto jednak skonfigurować pliki w naszej paczce, żeby rozwiązanie było automatycznie kompilowane z biblioteczką. Po pierwsze należy zmodyfikować plik makefile.in. Klucz CXXFLAGS informuje paczkę, jakich flag powinna używać przy kompilowaniu rozwiązań lokalnie. Nie ogranicza się ona tylko do flag, jeśli ustawimy wartość tego klucza na guelib.cpp, będziemy w stanie użyć poprawnie komendy make run. Warto wiedzieć, że po spacji można dodać więcej flag, wedle swojego uznania, należy jednak pamiętać, że są to flagi jedynie do lokalnej kompilacji.
Kolejna konfiguracja dotyczy działania paczki po wrzuceniu na portal. W tym celu należy zmodyfikować plik config.yml. Należy dodać następujące dwie linijki:
extra_compilation_args: {'cpp': 'guelib.cpp'}
Pierwsza z nich mówi, jakie pliki będą nam do kompilacji potrzebne, druga, jakie są potrzebne dodatkowe argumenty kompilacji poszczególnych języków.
Na koniec warto pamiętać, że pamięć zużywana przez biblioteczkę wlicza się do pamięci używanej przez program uczestnika. Warto zatem zwiększyć dozwolony limit pamięci w configu o odpowiednią wartość, żeby użytkownik mógł używać tyle pamięci, ile jest dozwolone w treści zadania.
W tym momencie paczka powinna być już poprawnie skonfigurowana.
Kolejnym wyzwaniem jest bezpieczeństwo. Istnieje szansa, że uczestnik zgadnie format wejściowy i wyjściowy. Wtedy może wczytać wejście samemu, wypisać poprawny wynik, a biblioteczka nie zostanie nawet raz zawołana. Bez żadnych zabezpieczeń nie mamy możliwości dowiedzenia się o takim incydencie.
W celu wyeliminowania powyższego ryzyka, warto zaszyfrować wejście. Nawet jeśli uczestnik domyśli się formatu, wczytane liczby nic mu nie powiedzą. A pamiętajmy, że gdy uczestnik wczyta wejście, to biblioteczka już nie, więc błąd będzie gwarantowany. Oczywiście najlepiej byłoby użyć profesjonalnego szyfrowania, jednak często jest to niepotrzebne, zazwyczaj wystarczy drobna zmiana. Przykładową modyfikację jest przexorowanie wszystkich liczb przez nam tylko znaną stałą. W przykładowej biblioteczce N (czyli zakres liczb) będzie przexorowany przez 143, a szukana liczba przez N. (Jeśli biblioteka ma działać adaptacyjnie, na wejściu szukaną liczbą będzie -1, nie musimy tej informacji szyfrować) Odszyfrowanie takiej informacji wygląda następująco:
cin >> N >> X;
N = N ^ 143;
if (X != -1)
X = X ^ N;Można też do liczb dodać/odjąć stałą, przemnożyć przez dwa, bądź przyłożyć jakąś inną prostą odwracalną funkcję. Nie ma sensu przesadnie się wysilać, w końcu jeśli ktoś koniecznie zechce złamać nasze szyfrowanie, to duża liczba zgłoszeń powinna zwrócić naszą uwagę. Nie będę opowiadać o profesjonalnym szyfrowaniu w tym tutorialu.
Przy wypisywaniu wyjścia nie trzeba szyfrować, natomiast warto w jakiś sposób zaznaczyć, że to nasza biblioteczka wypisała wyjście, a nie program uczestnika. W tym celu warto wypisać pewną oryginalną frazę na wyjście, na przykład "GoodJobYouDidEndTheGame!!". Może to być dowolna fraza, a nawet losowy ciąg znaków, ważne natomiast by nie zawierała spacji, bądź innych białych znaków. Uczestnik nie ma szans zgadnąć takiego słowa, więc wiadomo będzie, że to biblioteczka wypisała wynik. Warto używać checkerki, gdyż inaczej istnieje ryzyko że uczestnik zobaczy komentarz "wczytano 'ERROR' a oczekiwano 'NaszaDlugaFraza'". Checkerka pozwala też na dostosowanie komentarzy, które uczestnik zobaczy w raporcie swojego zgłoszenia (można na przykład w komentarzu umieścić informację o ilości zapytań albo błędzie popełnionym przez program). Także często nasza biblioteczka może obliczyć ile punktów powinien otrzymać program i może tą liczbę wypisać na wyjście.
Ostatnim aspektem jest przechowywanie danych. Jeśli dane zostaną zadeklarowane globalnie, program użytkownika będzie mieć do nich dostęp (a wtedy cóż za problem zczytać wartość zmiennej wynik i odpowiedzieć nią). Także, nawet niecelowo, użytkownik może taką zmienną nadpisać, a to może spowodować duże problemy w działaniu biblioteczki. Wynika to ze sposobu działania linkowania programu uczestnika z biblioteką. Używany przez nas sposób kompilacja działa w przybliżeniu tak, że wkleja kod biblioteczki na początek programu uczestnika. Każdy świadom tego uczestnik może łatwo to wykorzystać. Dlatego wszystkie funkcje pomocnicze i zmienne definiujemy w anonimowym namespacie (czyli namespace bez nazwy). Jest on widoczny tylko wewnątrz pliku, w którym jest zadeklarowany, zatem program uczestnika nie będzie mieć do niego dostępu (mimo linkowania). Tylko właściwe funkcje mogą być zadeklarowane poza nim. To zabezpiecza nas przed czytaniem naszych zmiennych, nadpisywaniem ich itp. Gotowa biblioteczka znajduje się w guelib.cpp Także, w katalogu in znajdują się zaszyfrowane testy (do szyfrowania i odszyfrowania wystarczy kalkulator). Zauważmy, że testy out nie zawierają żadnych informacji, dlatego nie są dodane do paczki (zostaną same wygenerowane na platformie SIO2). Jednak są potrzebne do testowania lokalnego, zatem przed uruchomieniem programu należy wywołać komendę "make ingen".
W skrócie:
- Szyfrujemy wejście, w zależności od wagi problemu xorem, prostym szyfrowaniem, lub nawet dużymi algorytmami szyfrującymi.
- W pierwszym wierszu wyjścia wypisujemy tajną frazę, w kolejnych potencjalne informacje od biblioteczki.
- Piszemy prostą checkerkę, która sprawdza czy informacje się zgadzają i personalizuje wynik/komentarz.
- Wszystkie dane trzymamy w anonimowym namespacie, żeby program uczestnika nie miał do nich dostępu.
Zdarza się, że będziemy chcieli zmniejszać punkty liniowo zależnie od działania programu (udzielonej odpowiedzi, ilości zapytań itp). Jest to oryginalna (i mało powszechna) technika karania lekko niepoprawnych programów w mało bolesny sposób. Jeśli chcemy zaimplementować taką zasadę zależną od wyniku/działania programu, potrzebna będzie nam checkerka. W naszym przypadku będziemy karać liniowym spadkiem punktów programy, które przekraczają 20 zapytań, ale nie 30. Od 30 zapytań otrzymają już tylko połowę punktów. Jeśli zaś użyją one ponad 2000 zapytań, dostaną one zero punktów.
Zaimplementowanie takiej funkcjonalności nie jest trudne, wymaga rozpatrzenia paru przypadków i jednego wzoru.
int points = 100;
if (queries > 30) {
points = 50;
} else if (queries > 20) {
points = (30 - queries) * 5 + 50;
}Warto pamiętać, że liczba wypisywana w trzecim wierszu to procent punktów, jakie uzyska zawodnik za dany test.
Gotowa checkerka znajduje się w guechk.cpp.
Wspominaliśmy już, że warto, by uczestnik mógł skompilować i uruchomić program na swoim komputerze. Do tego potrzebna mu będzie również biblioteczka. Dobrym zwyczajem jest więc mu ją udostępnić. Nie można dać mu oryginalnej, gdyż pozna wszelkie metody szyfrowania, adaptacji i inne potencjalne sekrety. W tym celu tworzymy prostą wersję biblioteczki, która jedynie wczytuje z wejścia test, symuluje działanie (bez adaptacji), oraz wynik wypisuje na wyjście (ewentualnie sprawdzając jego poprawność). Nie trudzimy się o żadne szyfrowania, namespace'y, optymalizacje czasu działania czy inne funkcje, które, niezbędne w wzorcowej biblioteczce, użytkownikowi do lokalnych testów nie są potrzebne. Ważne także, żeby wraz z przykładową biblioteczką udostępnić jej plik nagłówkowy, oraz przykładowy program. Przykładowy program musi działać poprawnie dla testu przykładowego, ale (z wiadomych przyczyn) musi być błędy. Dobrym przykładowym programem jest:
Wczytaj zakres liczb. Szukamy liczby z zakresu [1, 5] Czy większa od 4? Jeśli tak, to odpowiedz 5. Czy większe od 3? Jeśli nie, odpowiedz 1. Jeśli tak, odpowiedz 4. Przypadkiem odpowiedź w teście przykładowym pokrywa się z odpowiedzią programu (mimo że jest on błędny).
Warto nawet w treści/komentarzach programu zaznaczyć, że jest to błędne, lecz działające na przykładzie rozwiązanie. Te trzy pliki pakujemy w zipa (nazywanego zwyczajowo dlazaw.zip) i udostępniamy uczestnikom. Folder dlazaw (międzynarodowo nazywany public) znajduje się tu