Notka ósma, w której poznajemy linuksowe narzędzia przydatne w programowaniu konkursowym

Zacznijmy od następującego zadania:

Zadanie 6: Kserokopiarka

Tomek ma listę jego ulubionych liczb całkowitych. Chciałby podzielić się tą listą z Kasią. Tomek bardzo lubi Kasię. Poprosił Ciebie o pomoc. Treść tego zadania nie jest ambitna. Można powiedzieć, że dorównuje poziomowi tego zadania.

Wejście

Na standardowym wejściu znajduje się pewna liczba liczb całkowitych a_i spełniających -10⁹ ≤ a_i ≤ 10⁹.

Wyjście

Na standardowym wyjściu należy wypisać tę samą listę liczb.

Przykład

Dla danych wejściowych

-3
14
15

Poprawnym wynikiem jest

-3
14
15

Zadanie nie jest ambitne i myślę, że prawie każdy potrafiłby sobie z tym zadaniem poradzić. Wyjątkowo zatem zaczniemy od rozwiązania tego problemu. Jedynym miejscem, które może sprawiać problem, jest konieczność wczytania nieznanej ilości danych. Nie jest to trudne, ale nigdy jeszcze z taką koniecznością się nie spotkaliśmy.

#include <iostream>

using namespace std;

int main()
{
    int n;

    while (cin >> n)
    {
        cout << n << endl;
    }

    return 0;
}

Pętla while (cin >> n) zadziała dopóki będą dane na standardowym wejściu. Trochę o tym dzisiaj porozmawiamy. O tym jak to działa od środka, opowiem innym razem. Zwróć też uwagę, że użyliśmy zmiennej typu int, bo z sekcji wejście wiemy, że liczby będą podane z takiego przedziału, że int będzie potrafił je obsłużyć. Skompilujmy program:

g++ -o kserokopiarka kserokopiarka.cpp

Uruchommy program i zobaczmy czy działa dla testowych danych.

./kserokopiarka
-3
-3
14
14
15
15

Dziwne rzeczy się dzieją. Po pierwsze możesz zauważyć, że program wypisuje listę “od razu”. Ze swojego doświadczenia w nauczaniu wiem, że dużą liczbę osób to martwi. Czy program nie powinien najpierw wczytać wszystkie dane, a dopiero później wszystkie dane wypisać? Odpowiedź: nie ma to znaczenia. Dlaczego? Dzisiaj poznamy jak sprawdzaczki konkursowe działają od środka i zobaczymy, że z ich punktu widzenia program działa dobrze.

Drugą dziwną rzeczą, jest to, że program się nie zakończył, mimo że wpisaliśmy wszystkie dane. Z drugiej strony, skąd komputer miałby wiedzieć, że dane się skończyły? Po 15 moglibyśmy wszak wpisać kolejną liczbę. Jak zatem powiedzieć komputerowi, że dalszych danych już nie będzie? Należy wcisnąć CTRL + D (nie mylić ze skrótem CTRL + C który kończy program).

Oczywiście na konkursie nikt nie będzie sprawdzał rozwiązań “ręcznie”. No może wyjątek stanowił tutaj konkurs organizowany przez pewną politechnikę. Konkurs (na szczęście?) już się nie odbywa. Złośliwi mówią, że to dlatego, że studenci politechniki przegrywali sromotnie ze studentami konkurencyjnej uczelni. Ciekawe czy istnieje jakiś związek przyczynowo-skutkowy między tym, że prowadzący nie chcieli automatycznie sprawdzać rozwiązań a poziomem jaki reprezentowali studenci… nie ważne… Oczywiście na konkursie nikt nie będzie sprawdzał rozwiązań “ręcznie”. Zatem jak?

Organizatorzy przygotują szereg testów dla każdego zadania. Każdy test umieszczą w osobnym pliku. Przygotujmy własny plik z testem. Możecie to zrobić na dwa sposoby. Możecie użyć swojego ulubionego edytora tekstu (zazwyczaj będzie to program w którym piszecie kod). Ja pokażę jak to zrobić w konsoli. Wpisujemy polecenie cat > nazwa_pliku:

cat > kserokopiarka.in
-3
14
15

Pamiętajcie o wciśnięciu CTRL + D po zakończeniu wpisywania danych. Pro-tip: będąc na zawodach, powinieneś stworzyć pliki z danymi wejściowymi z przykładowych danych zanim będziesz testował swój program. Powód jest taki, że jest to taka sama praca jak skopiowanie tych danych bezpośrednio do programu (a musisz przecież przetestować program zanim go wyślesz do sprawdzenia), a jeśli program nie zadziała poprawnie to będziesz musiał wprowadzić poprawki i przetestować go ponownie. Wtedy plik z danymi wejściowymi będziesz miał już gotowy i nie będziesz musiał marnować czasu na ponowne jego skopiowanie z treści zadania.

Plik, jak widzicie, ma rozszerzenie “.in”. Od angielskiego “input” oznaczającego “wejście”. Jest to zatem plik wejściowy. Tak tradycyjnie na konkursach oznacza się tego typu pliki. Nie ma to jednak większego praktycznego znaczenia. Plikom wyjściowym nadamy rozszerzenie “.out” (od ang. output).

Po wpisaniu komendy cat powinieneś otrzymać nowy plik w katalogu. Możesz też to sprawdzić komendą ls lub dir. Teraz możesz uruchomić program z tymi danymi wpisując w konsoli:

./kserokopiarka < kserokopiarka.in
-3
14
15

Widzimy teraz, że na ekranie pojawił się wynik naszego programu i program od razu się zakończył. Ale czemu program nie wczytywał nic z klawiatury? Sedno tkwi w pojęciu “standardowego wejścia”. W pierwszej notce powiedziałem Tobie, że oznacza to, że dane powinny być wczytywane z klawiatury. Było to uproszczenie, które do tej pory nam wystarczało. Standardowe wejście jest jednak czymś więcej. Dane w komputerach mogą być wczytywane z różnych źródeł. Z klawiatury, z pliku, z internetu, ze skanera… Bardzo fajną rzeczą w linuksie jest to, że jeśli program wczytuje dane ze standardowego wejścia to nie trzeba wiele, aby program wczytywał dane z wszystkich tych źródeł, które wymieniłem. Wystarczy przekierować standardowe wejście. Służy do tego znaczek <. Powiedzieliśmy właśnie konsoli: uruchom program kserokopiarka i ustaw standardowe wejście na plik kserokopiarka.in.

Oprócz tego, że organizatorzy przygotują plik z danymi wejściowymi, przygotują również pliki z poprawnymi danymi wyjściowymi. Utwórzmy teraz taki plik i nazwijmy go kserokopiarka.out. Teraz masz trzy (a nie dwie) możliwości utworzenia tego pliku. Możesz stworzyć go w edytorze tekstu, w konsoli za pomocą komendy cat albo po prostu kopiując plik kserokopiarka.in, bo wyjątkowo zawartość tych dwóch plików będzie taka sama.

Jak się domyślasz, skoro standardowe wejście możesz przekierować, to również standardowe wyjście możesz. Służy do tego symbol >. Wpiszmy następujące polecenie w konsoli:

./kserokopiarka < kserokopiarka.in > wyjscie_mojego_programu.out

Teraz na ekranie nic się nie pojawiło. To co nasz program wypisał na wyjściu, zostało zapisane do pliku wyjscie_mojego_programu.out. Pro-tip: na zawodach często dane wyjściowe są niewielkie. W takiej sytuacji zazwyczaj nie przekierowuję standardowego wyjścia, tylko program normalnie wynik wypisuje mi na ekran i sprawdzam wzrokiem szybko czy wynik jest poprawny.

Mamy teraz dwa pliki z wynikami. Z wynikiem naszego programu: wyjscie_mojego_programu.out oraz z poprawnym wynikiem: kserokopiarka.out. Możemy teraz te pliki porównać. Służy do tego polecenie diff.

diff kserokopiarka.out wyjscie_mojego_programu.out
4d3
<

Swoją drogą… wiesz, że długich nazw plików (czy też poleceń) nie musisz wpisywać w całości do konsoli? Po wpisaniu kilku znaków i wciśnięciu klawisza tabulacji, konsola sama dopisze resztę, jeśli tylko będzie w stanie to zrobić. Jeśli kilka plików (poleceń) zaczyna się tymi symbolami to ponowne wciśnięcie tabulatora wypisze je wszystkie na ekranie. Przetestuj!

Program diff sprawdza zawartość obu plików i jeśli nie widzi różnicy to nic nie wypisuje. Jeśli różnicę znajdzie to mówi w której linijce wystąpiła i jaka jest różnica. Nam zazwyczaj wystarczy informacja czy pliki są sobie równe czy nie są. Jak widzisz z przykładu powyżej, moje pliki różnią się od siebie… znakiem nowej linii. Na konkursach dodatkowe spacje i znaki nowych linii nie są zazwyczaj brane pod uwagę przy ocenie zadania. Przy czym “zazwyczaj” może zrobić różnicę w naszym wyniku (na starych ACMach za złą liczbę spacji można było otrzymać werdykt Presentation Error). Od tego są dni próbne, aby takie rzeczy sprawdzić. Dopiszcie do rzeczy, które macie zrobić w dniu próbnym, aby sprawdzić ile spacji możecie wstawić zanim program sprawdzający się na was obrazi 😉

Wracając jednak do głównego wątku. Ponieważ spacje i znaki nowych linii nie mają znaczenia, możemy zmodyfikować nasze polecenie w następujący sposób:

diff kserokopiarka.out wyjscie_mojego_programu.out --ignore-trailing-space --ignore-space-change --ignore-blank-lines

Ignore trailing space ignoruje białe znaki na końcu każdej linijki, ignore space change ignoruje różnice wynikające z liczby białych znaków (rozdzielenie dwóch liczb jedną spacją versus oddzielenie dwóch liczb dwoma spacjami) i w końcu ignore blank lines ignoruje różnice wynikająca z wstawienia pustej linijki tam gdzie nie trzeba. Ponownie podkreślę, że to od konkretnej sprawdzaczki zależy jak bardzo będzie restrykcyjna. Wszystkie opcje polecenia diff można znaleźć w manualu.

Przetestowaliśmy już nasz program na małych danych. Jak jednak zrobić to na dużych danych? Możemy oczywiście otworzyć edytor tekstu i wpisywać przez pół godziny dane. Ale naturalnie, lepiej do tego nadają się komputery. Na przykład następujący program:

#include <iostream>

using namespace std;

int main()
{
   int n;

   cin >> n;
   for (int i = 0; i < n; i++)
   {
       cout << i << endl;
   }

   return 0;
}

Wczytuje ze standardowego wejścia liczbę n, a następnie wypisuje na standardowe wyjście liczby z zakresu [0, n-1]. Zapiszmy go jako generator.cpp i uruchommy go za pomocą komendy:

g++ -o generator generator.cpp && echo "5000000" | ./generator > kserokopiarka_duzy.in

Instrukcja g++ oczywiście kompiluje program. Komenda echo wypisuje 5000000 na ekran, co służy jako wejście dla naszego generatora, który zapisuje do pliku kserokopiarka_duzy.in 5000000 liczb naturalnych. Być może dostrzegłeś właśnie niesamowitą synergię między tymi poleceniami. Ponieważ linux posiada niesamowite komendy (jak g++ czy diff) oraz można je łączyć w bardziej skomplikowane twory (jak widać w przykładzie powyżej), jest to potężne narzędzie do robienia niesamowitych rzeczy! Aby mogło to w ten sposób działać – programy muszą ze sobą się komunikować. W szczególności w przykładzie powyżej: jeśli program się nie skompiluje, następne instrukcje nie zostaną wykonane (co można sprawdzić robiąc literówkę w kodzie programu). Zatem kompilator (tak jak każdy inny program) musi powiedzieć programom, które go uruchomią, że nie udało mu się skompilować programu (wszakże to nie jest nawet jego wina!).

Czy nasz program również musi to zrobić? Ależ naturalnie! Do tego służy tajemnicza instrukcja return 0 którą umieszczamy zawsze na końcu programu. Oznacza ona “Zakończyliśmy pracę bez żadnego błędu”. Jeśli zwróciliśmy na przykład return 17, oznaczałoby to dla świata: “Zakończyliśmy się z błędem. Kod tego błędu to 17”. Sami możemy decydować o tym jaki numer błędu co oznacza. Na konkursach pamiętajmy jednak, że powinniśmy zwracać jednak zawsze zero. W innym przypadku, system sprawdzający nasze zgłoszenie uzna, że program wykonał błąd i zwróci werdykt Run Time Error. Nawet jeśli zawsze będziecie zwracać 0, to wynikiem waszego programu również może być Run Time Error, gdyż inne komponenty, których używamy w naszych programach, mogą zwrócić kod błędu i zakończyć działanie naszego programu. Stanie się tak na przykład, kiedy w programie spróbujecie podzielić przez zero. Operator dzielenia w takiej sytuacji zakończy wasz program i zwróci kod błędu.

Sprawdźmy ile czasu zajmuje naszemu programowi ten duży test. Możemy to zrobić wpisując w konsoli:

time ./test < kserokopiarka_duzy.in > /dev/null

real    0m3,775s
user    0m2,526s
sys     0m1,155s

Użyliśmy programu time, który jak się domyślasz – liczy czas. Urządzenia /dev/null możemy użyć, jeśli nie chcemy zapisywać naszego wyjścia do pliku (ani go wyświetlać na ekranie). Program time wypisał trzy liczby. I żeby było śmieszniej – wszystkie różnią się od siebie dość znacząco. Na który z nich powinniśmy popatrzeć?

real – oznacza ile upłynęło czasu od rozpoczęcia naszego programu do jego zakończenia; to nie jest wartość o którą nam chodzi
sys – oznacza ile czasu system operacyjny poświęcił na obsługę naszego programu. Nasz program musiał zostać wczytany do pamięci operacyjnej; w pewnym momencie system musiał przerwać pracę naszemu programowi, bo właśnie z YouTube’a przyszła następna ramka z teledysku Justina Timberlake’a, którą oglądasz w tle i musiał ją obsłużyć, potem wznowienie działania naszego programu również trwało cenne dziesiątki sekund, i tak dalej.
user – to jest wartość o którą nam chodzi. Ile faktycznie czasu nasz program się wykonywał.

Komendy time możemy używać aby sprawdzać, które konstrukcje programistyczne są szybsze albo czy nasz program działa szybko na dużych danych. Pamiętaj jednak, że jeśli limit czasowy w zadaniu wynosi 5 sekund, a nasz program działa sekund 4, to nie oznacza, że nie możemy otrzymać werdyktu Time Limit Exceeded. Nasz komputer może się różnić od tego na którym uruchamiane jest sprawdzanie. Warto o tym pamiętać.

Umiemy kompilować program, sprawdzać czy program zakończył się poprawnie, mierzyć czas wykonania i sprawdzać czy wynik programu jest poprawny. Na dobrą sprawę, moglibyśmy napisać własną sprawdzaczkę. I może kiedyś to zrobimy.

Zadania do samodzielnego rozwiązania

Ponieważ nie nauczyliśmy się żadnej nowej techniki programistycznej, ani nowego algorytmu, przećwiczmy to co już umiemy. Wybrałem zadania o różnym poziomie trudności:

Watermelon (ranking 800)
New Year’s Number (ranking 900)
Triangles on a Rectangle (ranking 1000)
Move and Turn (ranking 1300)
Table Decorations (ranking 1800)

Nie przejmuj się jeśli nie potrafisz rozwiązać tych trudniejszych. Wymagają one pewnej sprawności matematycznej.

Notka ósma, w której poznajemy linuksowe narzędzia przydatne w programowaniu konkursowym