Tip of the day: Stjepanovi snippeti

Kad naučite Python i počnete ga koristiti u stručne ili znanstvene svrhe, više nikada nećete napisati nijedan algoritam: jednostavno ćete iskoristiti neki od desetak tisuća dostupnih modula. Sve je već napisano, čemu duplicirati kod? Malo pretjerujem, naravno, ali nije ovo daleko od istine. Proguglajte malo Python libraries. Naravno, na natjecanju je dostupna samo standardna Python biblioteka, ali natjecanja ćete ionako brzo prerasti.

A do tada, ako se za natjecanja pripremate u C++u, bacite oko na “module” Stjepana Glavine:

https://github.com/stjepang/snippets

Dosta korisno za razne online zadatke, čisto i jednostavno za ubaciti u kod (plug & play). Readme na dnu stranice sve objašnjava. Ako niste upoznati s namespaceovima, primjer korištenja možete vidjeti npr. u rješenju skloniste_flow.cxx u folderu suboptimalnih rješenja s Izbornih priprema (http://hsin.hr/pripreme2019/zadaci/rjesenja.zip).

Naravno, budući da ovo nemate na natjecanjima, ideja je i da vam posluži kao referenca da naučite kako što implementirati. Kad smo već kod toga, prilažem i jedan sličan, stariji dokument, tzv. Zagreb reference (implementacije raznih algoritama) autora Lovre Pužara.

Tip of the day: broj najkraćih putova i Dijkstrin DAG

Nakon guglanja o tome kaže li se putovi ili putevi, još uvijek nisam siguran što je ovdje ispravno. Kažu da su putovi konkretni, a putevi apstraktni. Za putove u našem smislu, tj. u smislu teorije grafova, može se reći i jedno i drugo. Sigurno su apstraktniji od šumskih putova, ali i konkretniji od, recimo, puteva mudrosti. Odlučio sam se za “konkretnu” varijantu: putovi. (Za one koji se zgražaju nad ovim jezičnim pseudoproblemima: nevažno je, naravno, ali je zabavno, i stvar estetike – shvatite to kao formatiranje teksta.) Dakle: putovi.

Floyd-Warshallov algoritam jedan je od najljepših algoritama koje znam jer u svojih samo 5-6 redaka koda krije mnogo mudrosti (puteva mudrosti, jel). Kao što učinak samog algoritma nije nimalo očit, tako možda nije očito ni da se algoritam može jednostavno nadopuniti tako da izračuna i koliko ima najkraćih putova između svakih dvaju vrhova.

Probajte to sami smisliti. Nije teško, ali je malo tricky. Recimo, prvi odgovor (označen zelenom kvačicom) na Stack Overflowu nije ispravan. Točno rješenje dano je u odgovoru ispod njega (kod počinje s procedure FloydWarshallWithCount ()).

Naravno, mana Floyd-Warshalla je složenost od O(N^3) i zato, osim za guste grafove, prednost ipak ima Dijkstrin algoritam koji se također može nadopuniti tako da računa i broj najkraćih putova.

Evo zadatka gdje to možete isprobati: Šetnja2 (IBT 2010.).

Korišteni bridovi koji se nalaze na najkraćim putovima iz nekog fiksnog vrha čine tzv. Dijkstrin DAG. (Ako su najkraći putovi jedinstveni, riječ je o stablu.) On ima glavnu ulogu u zadatku Najkraći (zadatak dana!) s HONI-ja 2008. (Ako vam je dosad promaklo, rješenja svih HONI-ja možete pronaći ovdje.) Update: još dva zadatka predložio je Marin u komentaru dolje.

Tip of the day: AB prebrojavanje

Jučer se na Hrvatskoj informatičkoj olimpijadi pojavio zadatak Ljepotica autora Ivana Paljka. U zadatku se traži zbroj velikih brojeva s određenim svojstvom, koji se nalaze između dvaju velikih brojeva A i B (koji imaju do 1000 znamenaka). Zadatke koji odgovaraju navedenom kalupu obično rješavamo tzv. AB prebrojavanjem.

Riječ je naprosto o dinamičkom programiranju koje je zbog pojavljivanja u ovom specifičnom obliku dobilo posebno ime. Zamišljamo da veliki broj gradimo znamenku po znamenku te nas u nekom trenutku zanima na koliko načina možemo napisati broj do kraja (ili zbroj tih mogućnosti, ili nešto drugo, ovisno o zadatku). Poanta je da nam za odgovor na to pitanje nisu bitne sve dosad odabrane znamenke, tj. stanje je moguće opisati manjim brojem parametara, od kojih je jedan redovito pozicija na kojoj se nalazimo (tj. redni broj trenutačne znamenke), a drugi ovisi o zadatku, tj. o traženom svojstvu broja koji konstruiramo (npr. pamtimo broj preostalih promjena u zadatku Ljepotica).

Da bismo se ograničili na brojeve iz intervala [A, B], treba nam još jedan parametar: jesmo li dosad odabranim znamenkama već osigurali da će broj koji konstruiramo biti strogo manji od B, ili on još uvijek može biti jednak B, tj. podudaraju li se dosadašnje znamenke sa znamenkama broja B. U stanja gdje bismo premašili B nećemo ni ući, a to osiguravamo upravo iz navedenog parametra, znajući moramo li pri odabiru trenutačne znamenke paziti da ne premašimo istu znamenku u broju B (ako smo dosad birali iste znamenke kao u broju B).

Takva dinamika ne vodi računa o donjoj granici A, ali poslije samo provedemo isti algoritam s tom granicom da bismo oduzeli brojeve manje od A koje smo prethodno ubrojili. Drugim riječima, računamo koliko ih ima do B, minus koliko ih ima do A – 1, čime dobivamo koliko ih ima od A do B.

Osim ovih generičkih ideja, svaki zadatak ovog tipa može biti na svoj način osobit i ponekad je potrebna još neka specifična dosjetka, kao npr. u zadatku Umnožak koji se također pojavio na HIO, desetak godina prije. Otprilike u to vrijeme i na HONI-ju se pojavio zadatak Trešnja ovoga tipa. Priču je moguće i malo okrenuti, pa tražiti N-ti broj koji zadovoljava neko svojstvo, kao u zadatku Sretni s IBT-a.

Tipičan zadatak za početnike bio bi npr. Sum of Digits – ovakve zadatke lako je debugirati jer je lako skodirati brutfors i izmišljati testne primjere. Još mnogo objašnjenja i zadataka dostupno je na webu ako tražite Digit DP. Primjerice:

Dvije stablaste fore

Za neko ukorijenjeno stablo, poredajmo vrhove stabla u niz onim redom kojim ih dohvaćamo DFS obilaskom iz korijena. Taj niz ima svojstvo da svako podstablo čini interval, tj. uzastopni podniz. (Ako dva vrha pripadaju nekom podstablu, onda se između njih u nizu nalaze samo vrhovi iz istog podstabla.) Koristeći taj niz, neki upit na podstablu svodi se na upit na intervalu niza. Nekoliko zadataka koji koriste tu foru:

No posljednji zadatak mnogo je lakše riješiti koristeći manje-u-veće trik. Ako imamo neke skupove od ukupno N elemenata i želimo ih spajati jedan u drugi dok ih sve ne spojimo (spajanja čine stablo), i ako pri spajanju dvaju skupova pazimo da uvijek prebacujemo elemente iz manjeg skupa u veći, svaki element će biti pomaknut najviše log(N) puta jer svakim prijelazom dolazi u barem duplo veći skup. To možemo koristiti kad neke informacije dižemo iz listova prema korijenu stabla, u svakom čvoru spajajući skupove koje smo prethodno izračunali za njegovu djecu, kao u navedenom zadatku Distinct colors. Tim je trikom moguće riješiti i Stablo u stablu iz gornje liste – to je uspjelo Anti Đereku dok smo pripremali zadatak. Još jedan zadatak s tim trikom: Loza (HIO 2010.).

Još zadataka slobodno linkajte u komentarima.

Tip of the day: granice intervala

U pretpretprošlom postu kao jednu od točaka spomenuo sam “neelegantno baratanje donjim i gornjim granicama intervala” kao jednu od početničkih mana u kodiranju. Koje je onda elegantno baratanje?

Uz oznake L i R za lijevu i desnu granicu (left i right), najbolje je brojevima L i R označiti interval {L, L+1, …, R-1}; dakle, interval [L, R> kojemu je donja granica uključena, a gornja isključena. Ta asimetrija može se isprva učiniti neelegantnom, ali ona nam zapravo pojednostavljuje život:

  • Veličina intervala jednostavno je R – L. (Kad bi obje granice bile uključene, bila bi R – L + 1.)
  • Intervali se na ovaj način lako i prirodno nadovezuju: [A, B> + [B, C> = [A, C>. Ovo je korisno u mnogim “podijeli pa vladaj” pristupima gdje se interval dijeli na dva manja, primjerice u tournament stablu: [L, R> dijelimo na [L, mid> + [mid, R>.
  • Na ovaj način možemo pokriti i slučaj kad je interval prazan: L = R.

Druge prednosti koje mi nisu pale na pamet slobodno dopišite u komentare. Jedan od rijetkih slučajeva gdje koristim drugačiji princip (interval [L, R] kojemu su obje granice uključene) jest binarno pretraživanje, iako mnogi i ondje koriste gornji princip.

Princip “donja uključena, gornja isključena” koriste standardni oblici for petlje u većini programskih jezika: sjetite se kako radi range u Pythonu ili najčešća petlja for (i=0; i < n; ++i) u jeziku C. Sve je to povezano i s činjenicom da su nizovi uglavnom indeksirani od nule, tako da se niz duljine N nalazi na indeksima iz intervala [0, N>. Kraj je isključen: u C++u ćete znati da ste došli do kraja STL containera (vector, string, set, map…) kada naiđete na s.end(), primjerice u petlji: for (it = s.begin(); it != s.end(); ++it) ili u provjeri if s.find(element) == s.end() kao znak da element nije pronađen.

Zašto sve ide od nule? Mnogo je razloga, čak i matematičkih. Brojevi koje možete zapisati s K binarnih znamenaka čine interval [0, 2K >. Ostatci modulo N su 0, 1, …, N-1. Koristite li hash tablicu s modulom N, jasno je da su upravo to indeksi koji vam trebaju. Ili, ako se po nizu krećete ciklički, kad povećate indeks za proizvoljan korak, dovoljno ga je modati s N da dobijete pravi indeks (N -> 0, N+1 -> 1, N+2 -> 2, …). Općenito se formule pojednostavljuju: pogledajte npr. odgovore na https://www.quora.com/Why-do-array-indexes-start-with-0-zero-in-many-programming-languages.

Tip of the day: code review

Sve ozbiljne softverske firme imaju praksu code reviewa, što znači da svaki napisani kod mora proći pregled nekog drugog člana tima prije nego što uđe u pogon, tj. postane dio proizvoda. To nije testiranje, koje se obavlja prethodno, tijekom programiranja. To je doslovno čitanje koda. Čak i najboljim zaposlenicima netko drugi mora pročitati kod, iako je prethodno već testiran. Svrha je stvaranje boljeg koda, ne toliko u smislu otkrivanja bugova (iako se nađe onih koje testovi nisu uhvatili), nego uočavanje stvari koje se mogu napraviti drugačije, elegantnije, pravilnije, sigurnije, robusnije, organiziranije, čitljivije za kasnije održavanje/nadogradnju itd.

Ova praksa u natjecateljskom programiranju nije uobičajena. Ako smo riješili zadatak i prolaze svi primjeri, zašto bismo se vraćali na kod koji je ispravan? Ipak, ako je kod ispravan, ne znači nužno da je dobro napisan i da će način na koji smo ga pisali biti dobar i u budućim, težim zadatcima. Zato je korisno baciti oko i na tuđe kodove da bismo iz njih nešto naučili. No jednako je korisno da netko drugi baci oko na naš kod. Tako neki mentori, voditelji grupa ili radionica (u MIOC-u, HSIN-u, ZRS-u…) odvajaju dio svog vremena da barem površno pogledaju kodove svojih učenika i ukažu im na stvari koje se mogu bolje. Čak i za vrlo dobre natjecatelje vrijedi: kad im netko bolji/iskusniji pogleda kod, uočava stvari koje se mogu poboljšati.

Početnički primjeri uključuju:

  • slabu čitljivost koda, npr. škrtarenje s razmacima i redcima (kako ćete debugirati kod koji je napisan gusto i zbrda zdola?),
  • nekonzistentna ili manjkava stilska obilježja (vidi npr. ovaj post),
  • nedeskriptivna imena varijabli – teško ćete se snaći u većem kodu ako vam se varijable zovu a,b,c,d,e,f,g,h,
  • glomazne porcije koda (umjesto organiziranja u funkcije) i kao posljedica kod koji je teško testirati dio po dio i debugirati,
  • duplikacija, tj. isti/sličan dio koda prisutan na više mjesta (lakše se griješi i teže se mijenja) umjesto izdvajanja u funkciju,
  • suvišne varijable i nepotrebno kompliciranje koda (odražava neurednost misli),
  • neefikasne petlje – npr. korištenje dvostruke gdje je dovoljna jedna,
  • neefikasno spremanje podataka u polja/parove/strukture,
  • deklaracije na lošem mjestu (uz neke iznimke, doseg varijabli treba biti najmanji mogući),
  • loše organizirani slučajevi (“puno ifova”) i formule u kojima je lako pogriješiti – te stvari spominjao sam i ovdje,
  • neelegantno baratanje donjim i gornjim granicama intervala (“jel tu sad ide > ili >=? plus jedan ili minus jedan?”),
  • računanje istih podataka više puta, npr. unutar neke petlje, umjesto da se unaprijed izračunaju,

i mnogi drugi. Nakon što se savladaju osnove, poboljšanja koda uglavnom su vezana uz konkretan algoritam i njegove implementacijske varijante. Istina je da vještina kodiranja kod početnika raste jako brzo, a s vremenom sve sporije (logaritamska krivulja), ali čitajući kodove boljih od sebe uvijek se mogu naučiti novi trikovi.