Skip to content

[PL] 4. Paczka z generatorem wejść

Jump to bottom
niedziol edited this page Jun 16, 2020 · 3 revisions

Problem

We wszystkich poprzednich poradnikach, struktura wejścia była bardzo prosta. Przygotowanie plików wejściowych mogło nastąpić przez ręczne wpisanie wartości w edytorze, lub przez napisanie skrajnie prymitywnego skryptu w dowolnym języku. Niestety, nie zawsze jest to możliwe. W istotnej większości zadań, na wejściu chcemy umieszczać tablice, grafy, macierze i inne zaawansowane byty. System SIO2 umożliwia rozwiązanie tego problemu przez umieszczenie w paczce programu generującego potrzebne pliki wejściowe.

Zadanie

Mamy dane drzewo, czyli spójny, nieskierowany i acykliczny graf. Składa się on z n wierzchołków i n - 1 krawędzi. Zadaniem będzie wyznaczyć liczbę liści. Liściem nazywamy każdy wierzchołek (oprócz korzenia) o stopniu 1 (wychodzi z niego tylko jedna krawędź). Zadanie będzie mieć tytuł Leaves i skrót lea.

Testy

Przygotowanie testów jest bezapelacyjnie najważniejszą (i często najtrudniejszą) częścią opracowania. Testy powinny być tak dobrane, by różnicowały poszczególne klasy (poprawnych) rozwiązań. Dobierając testy, należy kierować się następującymi ogólnymi wytycznymi:

  • Przy każdym uruchomieniu generatorki, utworzone testy muszą być identyczne.
  • To, ile punktów zdobywa dane rozwiązanie, powinno odzwierciedlać wysiłek (koncepcyjny i programistyczny) konieczny do jego opracowania. W przypadku wątpliwości należy równomiernie rozdzielić punkty między coraz efektywniejsze rozwiązania.
  • To, ile testów przejdzie dane rozwiązanie, powinno zależeć jedynie od rodzaju rozwiązania, a nie od języka programowania, w którym jest zaimplementowane.
  • Z reguły wszystkie rozwiązania poprawne, również te mniej efektywne, powinny zdobywać jakieś punkty częściowe.
  • Heurystyki lub rozwiązania opierające się na błędnych założeniach powinny otrzymywać mało punktów. W szczególności rozwiązania, które udzielają zawsze tej samej odpowiedzi (np. 0, NIE, czy odpowiedź dla testu przykładowego), powinny otrzymywać 0 punktów (można w tym celu zastosować grupowanie testów).
  • Zestaw powinien zawierać testy skrajnie małe i skrajnie duże, nawet jeśli są trywialnie proste.
  • Program otrzymuje punkty za daną grupę testów, jeśli przejdzie wszystkie testy w zestawie. Należy starać się, w miarę rozsądku, minimalizować liczbę testów w grupie.

Generator wejścia

W pliku leaingen.cpp będziemy musieli umieścić kod, który wygeneruje testy wejściowe. Z reguły każdy autor zadania ma przygotowany swój szablon takiego pliku, który specjalnie przygotował sobie pod swoje preferencje pracy nad testami. Na potrzeby tego poradnika pokażemy bardzo prosty generator wejścia napisany w języku C++. Tak jak w poprzednim poradniku, będziemy wykorzystywać bibliotekę oi.h, która dostarcza nam wiele narzędzi do pseudolosowości. Na początek stworzymy funkcję, która zwraca liczbę z zadanego przedziału.

unsigned randomUIntInRange(unsigned a, unsigned b) {
    unsigned res = RG.randUInt();
    return res % (b - a + 1) + a;
}

Teraz zajmiemy się strukturą naszego testu. Warto zastanowić się, jakie dane musi posiadać test, aby jednoznacznie móc go wypisać. Można wtedy przydzielić temu jedną funkcję, a pozostałymi wypełniać strukturę testu. W naszym przypadku będzie to:

struct Test {
    int n;
    vector<pair<int, int>> edges;

Rzeczywiście liczba wierzchołków i wektor krawędzi wystarczają do wypisania testu. Teraz przygotujmy funkcję, która posłuży do wypisywania danego testu.

void print(int no, char *letter) {
    assert('a' <= *letter && *letter <= 'z');
    string name = id + to_string(no) + *letter + ".in";
    cerr << "Printing to file: " << name << "\n";
    ofstream outFile(name);
    outFile << n << "\n";
    for (const auto &edge : edges) {
        outFile << edge.first << " " << edge.second << "\n";
    }
    outFile.close();
    (*letter)++;
}

Mamy funkcję, która przyjmuje numer grupy, oraz pierwszą literkę (często przydatne jeśli chcemy ileś pierwszych testów z grupy wygenerować ręcznie). Teraz jeśli stworzymy funkcję, która zwraca typ Test, możemy wywołać metodę print i automatycznie zostanie stworzony plik zawierający dany test. Stworzymy też funkcję shuffle, która pomiesza dane w wektorze (pamiętajmy, że nigdzie w zadaniu nie gwarantujemy konkretnej kolejności). Warto zaznaczyć, że do losowania używamy funkcji dostarczonej przez bibliotekę oi.h.

RG.randomShuffle(test->edges.begin(), test->edges.end());

Teraz możemy stworzyć kilka różnych typów testów. Dokładniejszy ich opis można znaleźć w samym pliku generatorki. Kod jednej grupy w mainie wygląda następująco.

{ // Test group 1 - n <= 100
    int group = 1;
    char c = 'a';
    RG.setSeed(1);
    random(100).print(group, &c);
    random(92).print(group, &c);
    path(100, false).print(group, &c);
    star(100, true).print(group, &c);
    binaryTree(100).print(group, &c);
}

Warto zwrócić uwagę na poniższą linijkę.

RG.setSeed(1);

Ustawienie ziarna dla generatora gwarantuje, że testy będą deterministyczne. W tym zadaniu ziarno zmieniamy co każdą grupę, warto jednak zaznaczyć, że częstą praktyką jest ustalanie nowego ziarna dla każdego testu (wtedy zmiana konkretnego testu nie rzutuje na następne należące do tego samego ziarna). Więcej o ziarnie i pseudolosowości można przeczytać tutaj. Teraz po uruchomieniu make ingen w folderze gue powinny pojawić się wszystkie testy.

Weryfikacja wejścia

Podczas pracy nad testami bardzo często będziemy zmieniać generatorkę. Z reguły będziemy układać po jednej konkretnej funkcji, która ma sprawdzić pewną klasę rozwiązań. Możemy wtedy uruchomić testy i sprawdzić jakie wyniki otrzymują konkretne rozwiązania wzorcowe, błędne czy wolne. Jak możemy jednak zadbać o poprawność tych testów? Z pomocą przychodzi program do weryfikacji wejścia. Będzie on działał na bardzo podobnej zasadzie co program do weryfikacji wyjścia, przedstawiony w poprzednim poradniku. Z pomocą biblioteki oi.h będziemy czytać plik wejściowy znak po znaku i sprawdzać czy spełnia on wymagania, które gwarantujemy w zadaniu. Należy w szczególności pamiętać o informowaniu o spełnieniu konkretnych podzadań. Gotową weryfikatorkę możemy znaleźć w pliku gueinwer.cpp. Możemy uruchomić weryfikator wpisując w terminalu make inwer. Pisanie weryfikatora wejścia jest bardzo ważnym nawykiem i powinnien znajdować się on w każdej paczce niezależnie od poziomu skomplikowania wejścia.

Czyszczenie

Aby wyczyścić wszystkie wygenerowane testy (prócz testów przykładowych) używamy make clean-gen.

Clone this wiki locally