Konkursy programistyczne

Co jest najważniejsze w informatyce? Odruchowa, wynoszona ze studiów odpowiedź - pisanie algorytmów. Znajdowanie efektywnych rozwiązań trudnych problemów, weryfikowanie ich poprawności formalnej czy numerycznej. Wirth, Knuth, Dijkstra, Hoare, ... Algorytmy i struktury danych!

Codzienna informatyka wygląda trochę inaczej. Kluczowe są umiejętnosci architektoniczne - od zaplanowania złożonego systemu jako całości, po organizowanie kodu tak by był czytelny, rozszerzalny i reużywalny - i organizacyjne. Waży dobra znajomość konkretnych języków, bibliotek i narzędzi. Znaczy profil psychologiczny - od pomysłowości, po umiejętność kooperacji. Przydaje się umiejętność zrozumiałego pisania tekstów, a nawet zmysł estetyczny.

Za to okazje do pisania nietrywialnych algorytmów są - rzadkie. Niemal wszystko, co potrzebne, da się znaleźć i użyć w gotowej formie.

Tym bardziej chce się czasem sprawdzić, czy jeszcze w ogóle to potrafię.

Konkursy

W sieci jest całkiem sporo serwisów z różnymi zadaniami programistycznymi. Czasem są prowadzone przez hobbistów, czasem stanowią odprysk działalności uniwersytetów, często stanowią dyskretną formę szukania potencjalnych kandydatów do pracy (Google CodeJam jest nawet obudowany w sposób pomagający czołówce zapoznać się z firmą Google, w Polsce też raczej nie przypadkiem Mistrzostwa Polski w Programowaniu organizowało Asseco).

Opiszę dwie - bardzo różne - strony, którymi się trochę pobawiłem.

Jest oczywiście wiele innych możliwości. Hasła typu programming contest, programming problems, algorithm competition, a nawet zawody w programowaniu każdy może wpisać w wyszukiwarkę sam, więc nie będę tu kopiował wyników.

ProjectEuler

Bardzo mi się podoba ProjectEuler. Może dlatego, że wpisuje się w moje zainteresowania matematyczne - publikowane są tu zadania z pogranicza matematyki i informatyki.

Spektrum jest dość szerokie, z kilkudziesięciu zadań jakimi się zajmowałem, kilka udało mi się rozwiązać na kartce, kilka miało czysto programistyczną specyfikę, a większość wymagała połączenia chwili rozważań matematycznych z napisaniem rozsądnego algorytmu. Podobnie, niektóre zadania są dość łatwe, a niektóre ... nietrywialne.

Charakterystyczny przykład zadania to optymalizacja n/φ(n). Ale trafia się też czysto algorytmiczne wyszukiwanie optymalnej ścieżki albo pachnące praktycznie symulacja pokera i łamanie hasła.

ProjectEuler nie stawia żadnych wymagań co do metody rozwiązania. Liczy się jedynie wpisanie poprawnej odpowiedzi. Dlatego można stosować dowolnie wybrane narzędzia i języki programowania.

Po rozwiązaniu zadania zyskuje się dostęp do forum, na którym użytkownicy serwisu opisują swoje rozwiązania. Bywa to oczywiście pouczające - gdy mój program przez minutę czy dwie przeszukiwał miliony możliwości, a ktoś znalazł i udowodnił szybką, elegancką metodę - ale też po prostu ciekawe - gdy pojawiają się fragmenty kodu w egzotycznych językach programowania.

Ogromna zaleta: zadania są krótkie i jasno napisane i przygotowane tak, by nie wymagały nudnego programowania (rozbudowanej obsługi wejścia i wyjścia, walidacji, formatowania itp). Rozwiązanie może być trudno wymyślić, ale gdy się już je wymyśli, jest krótkie i pisze się je szybko.

Wady? Część problemów - zwłaszcza tych starszych - daje się łamać brute force, co stanowi niepotrzebną pokusę. A na forum zadania brakuje jakiegoś systemu oceniania wypowiedzi, który pozwoliłby wyłapać najcenniejsze uwagi.

Prowadzona jest prosta punktacja: jeden punkt za jedno poprawnie rozwiązanie, uzupełniana różnymi statystykami. Dochodzi do tego nieformalna rywalizacja, kto najszybciej rozwiąże i opisze nowo dodane zadanie. A takowe pojawia się raz na tydzień.

W tej chwili ProjectEuler zawiera 225 zadań. Rozwiązanie ich wszystkich to zabawa na wiele wieczorów... Mi udało się na razie zrobić kilkadziesiąt.

Topcoder

Topcoder działa zupełnie inaczej. To duży serwis, ukierunkowany głównie na praktyczne programowanie.

Piszemy konkretny kod (w C++, C# lub Javie), który zapisujemy na serwerze i który tam zostaje skompilowany i przetestowany. Nie ma pełnej swobody, jest wymóg by to, co napiszemy, skompilowało się i zwróciło odpowiednie wyniki.

Nie piszemy całych programów. Zazwyczaj zadanie nakazuje napisać metodę o takiej-a-takiej sygnaturze, która zostaje zlinkowana z gotowym (niewidocznym) szkieletem programu.

Po rozwiązaniu problemu można oglądać cudze rozwiązania - i nie jest to kwestia dobrej woli ich autorów, dostępne są wszystkie. Ba! Można próbować je obalać (przez podanie parametrów, dla których nie zadziałają poprawnie) - i jest to także ważny element rywalizacji (za udane obalenie zdobywamy dodatkowe punkty). Fajny pomysł, pomagający zdobywać wyczucie przydatne przy robieniu review kodu.

Topcoder uruchamia się w formie rozbudowanego apletu, zapewniającego nawigację pomiędzy konkursami i zadaniami oraz środowisko edycyjne (okno edytora z kolorowaniem składni, podgląd ewentualnych błędów kompilacji). Wygodna jest funkcja bezkarnego uruchamiania na danych testowych.

Tryb pracy: piszemy program, dowolną ilość razy próbujemy go kompilować i uruchamiać na danych testowych, wreszcie publikujemy rozwiązanie (co już jest nieodwracalne).

W środowisku Topcodera do dyspozycji jest masa zadań archiwalnych, do tego regularnie odbywają się nowe konkursy - czasem nawet z nagrodami finansowymi (te toczą się w ustalonych terminach, z ograniczeniem czasu).

Wady?

Aplet Topcodera jest niewygodny i mało intuicyjny. Sporo wysiłku wymaga elementarna nawigacja, okno edytora jest małe i nieporęczne (po paru próbach pisania w nim zdecydowałem się pisać programiki w Emacsie i kopiować, gdy są już gotowe), ciężko się zorientować w pokaźnej ilości zadań i konkursów o kryptycznych nazwach.

Zadania - przynajmniej te, które robiłem lub oglądałem (kilkakanaście wybranych na chybił-trafił) - są mniej zgrabne, niż te z ProjectEuler. Długa - nawet kilkustronicowa - treść, częsta konieczność pisania parserów danych wejściowych, czy sprawdzania rozmaitych warunków brzegowych, za to faktyczne rozwiązanie nieraz dość oczywiste. Jest to bliższe prawdziwej informatyce ale mniej pociągające jako forma rozrywki. No i jest dużo bardziej czasochłonne.

Ma tu oczywiście znaczenie wybór narzędzi. Załadowanie ciągu liczb rozdzielonych przecinkami w perlu czy pythonie jest jedną instrukcją, w C++ czy Javie wymaga znacznie więcej zachodu. Topcoder ma opcję Python ale dla konkursów algorytmicznych chyba nie jest ona dostępna (w Pythonie można pisać rozwiązania maratonów, czyli otwartych trudnych problemów).

Podsumowując: bardzo rozbudowany, ciekawie pomyślany, realistyczny i obiektywnie oceniający rozwiązania serwis - ale raczej dla osób dysponujących większą ilością wolnego czasu.

Bawiłem się tylko konkursami algorytmicznymi i tylko o nich piszę. Na Topcoderze dzieje się więcej, min. rywalizacje związane z projektowaniem.

Dopisek (OPSS)

Rzuciłem szybko okiem na OPSS. Całkiem przyjemnie ten serwis wygląda. Piszemy gotowy pełny program (C++, Pascal lub C), uploadujemy go, po chwili sprawdzamy wynik. Program zazwyczaj wczytuje ciąg liczb z standardowego wejścia i ma wypisać odpowiedź na standardowe wyjście.

Zadania wyglądają ciekawie, zwłaszcza te z dalszymi numerkami.

Co może być ważne: OPSS jest po polsku.