Iza kulisa HONI-ja

Voditelji ovogodišnjeg HONI-ja, Ivan Paljak i Marin Kišić, odlučili su javno objaviti repozitorij u kojem su rađeni zadatci. Evo ga ovdje:

https://github.com/mkisic/HONI-19-20

Za one koji to nikada nisu radili, ovo je dobra prilika da dobiju neki uvid u izradu zadataka za informatička natjecanja. Osim samih tekstova i rješenja, autori pišu generatore testnih primjera, razna polurješenja da bi provjerili nose li očekivani broj bodova ili konstruirali primjere koji ih ruše, kodiraju validatore koji provjeravaju zadovoljavaju li primjeri uvjete iz teksta zadatka i jesu li u dobrom formatu, pišu checkere za one zadatke gdje output nije jednoznačan itd. Kao primjer što se sve ponekad napravi za jedan zadatak, pogledajte direktorij za zadak Skandi (6. kolo).

Najprije, što je uopće repozitorij? Riječ je o folderu u kojemu više suradnika zajedno radi, a sve promjene prate se putem tzv. version control sustava (kao što je git) koji omogućava praćenje tko je i kada što dodao, promijenio i slično. Ljudi drže takve repozitorije (što javne, što privatne) na stranicama kao što su GitHub, Bitbucket i Gitlab. Version control sustavi su norma u svijetu programiranja i koristi ih svaki iole ozbiljan projekt jer inače nastane kaos. Korisni su čak i kad samo jedna osoba radi na projektu, jer imaju mogućnost undo-a tj. vraćanja na prethodnu verziju bilo koje datoteke. Sram me to priznati, ali za Državno 2018. (pod mojom palicom) koristili smo Google Drive. Ručni upload, ručni download, živi užas, ne znam što mi je bilo. Jednom i nikad više. Ovdje sve ide lijepo glatko iz komandne linije, naravno, na Linuxu.

Još jedan od važnih ovdje korištenih alata je LaTeX za tekstove zadataka. On omogućava automatizaciju mnogih stvari, npr. probni primjeri ne moraju se pisati na dva mjesta (u tekstu i u datotekama) nego se automatski kopiraju u tekst, svaki je zadatak u svojoj .tex datoteci čime se lakše prate promjene i slično. Ove godine i školsko i županijsko bili su u LaTeX-u (priznajem, prethodne dvije godine bio je Word u igri). Evo primjera glavne .tex datoteke za 6. kolo koja, kao što vidite, uključuje po jednu datoteku za svaki zadatak (npr. Trener). To se onda pretvara (“kompajlira”) u PDF naredbom pdflatex. Matematičari već znaju da je LaTeX nezaobilazan, ali to zapravo vrijedi i za računarstvo i većinu stručnih/znanstvenih disciplina.

Onda su tu generatori testnih primjera koji se najčešće pišu u Pythonu (jer je najlakše) i nastoji se izgenerirati sve primjere u jednom pokretanju generatora. Ovdje je primjer generatora za zadatak Trener. Također u Pythonu piše se i validator primjera (npr. ovaj) koji mora napisati druga osoba; on provjerava da su primjeri u ispravnom formatu (uključujući i razmake) i da zadovoljavaju sva ograničenja, uključujući i ona iz sekcije Bodovanje (npr. N < 100 u 50% primjera). Kao što se može uočiti, za generatore i validatore postoje templateovi koji pomažu da se oni brže napišu. Validator je uglavnom lako napisati, ali ponekad se moraju provjeriti i netrivijalni uvjeti poput zahtjeva da je graf povezan ili još težih uvjeta.

I naravno, tu su brutforsi, alternativna rješenja, rješenja za parcijale iz bodovanja, “prevare” (greedyji, heuristike) i ostala rješenja za koje se mora provjeriti koje primjere osvajaju. Za one zadatke gdje natjecateljev output treba programski provjeriti (jer nije jedinstven) pišu se checkeri (npr. ovaj) koji provjeravaju je li output točan. Oni su poseban izazov jer se ne smiju srušiti i moraju raditi za sve neočekivane slučajeve (pogrešan format, manjak ili višak ispisa, očekuje broj a dobije string i sve ostalo).

Previše posla? Ne uvijek. Za većinu zadataka (pogotovo one lakše) ne pojavljuju se baš svi od navedenih izazova. Nekad tekst zadatka može biti kratak i jednostavan, nekad je lako generirati primjere (baciš neki random i bok), nekad ih je lako validirati, nekad je lako napisati brutforse, checker često nije potreban itd. Na kraju, ako je dovoljno zainteresiranih ljudi i ako počnu raditi na vrijeme, ispadne OK i, naravno, bude jako zabavno.

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google photo

Ovaj komentar pišete koristeći vaš Google račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s