Jeste li ikad bjesomučno refreshali neku stranicu čekajući neku vijest ili promjenu? (Recimo, popis pozvanih na Državno natjecanje koji se danas očekuje?)

Možda ste znali, a možda i niste, da se to refreshanje može automatizirati.

Postoje online alati za to (recimo, https://www.followthatpage.com/), ali zašto ne bismo zasukali rukave i sami napisali odgovarajuću skripticu?

Ovo je moja:

"""
Usage: refresh.py [full_url] [refresh_interval_in_seconds] [optional: string_to_search]

If the search string is given, then refreshes until the string is found in page text.
Otherwise, refreshes until the page is changed.
"""

import urllib.request
import sys
from time import sleep
from bs4 import BeautifulSoup

def get_text(url):
    text = str(urllib.request.urlopen(url).read())
    soup = BeautifulSoup(text, 'html.parser')
    [s.extract() for s in soup(['style', 'script', '[document]', 'head', 'title'])]
    text = soup.getText()
    # ignore numbers
    for z in '0123456789':
        text = text.replace(z, '')
    return text

try:
    interval = int(sys.argv[2])
    url = sys.argv[1]
except:
    print(f'usage: {sys.argv[0]} [full_url] [refresh_interval_in_seconds] [optional: string to search]')
    exit(0)
if len(sys.argv) > 3:
    word = sys.argv[3]
else:
    word = None
print(f'reading {url} ...')
previous_text = get_text(url)
while True:
    sleep(interval)
    print(f'refreshing {url} ...', end=' ')
    text = get_text(url)
    if word: 
        if word in text:
            print(f'String "{word}" found in page text!')
            exit(0)
        else:
            print(f'string "{word}" not found')
    else:
        if text != previous_text:
            print(f'Page has changed!')
            exit(0)
        else:
            print('no change')
    previous_text = text

Ovaj dio s promjenom ne radi na stranicama s oglasima (npr. portali) jer su svaki put drugačije reklame pa skripta misli da se stranica promijenila. Možda ima i još bugova ili prostora za poboljšanje, slobodno komentirajte.

Napomena: Ne postavljajte refresh interval na manje od nekoliko sekundi; prečesto slanje requestova može biti nepristojno ili čak zabranjeno. Related: https://softwareengineering.stackexchange.com/a/304767

Na IOI-u 2010. prvi put smo se susreli s tipom zadatka u kojemu treba poslati neku informaciju u što manje bitova. Zadatak se zvao Saveit i trebalo je, za zadani graf, najkraće udaljenosti (između zadanih posebnih vrhova do svih ostalih) poslati kao bitovni niz iz jednog programa (encoder) u drugi program (decoder) koji će taj niz znati protumačiti, tj. iz binarnog niza rekonstruirati tražene udaljenosti. Trebalo je, naravno, napisati oba programa.

Naivno je rješenje svaku udaljenost poslati kao binaran broj, što rezultira prevelikim ukupnim brojem bitova. Ključna ideja bila je iskoristiti činjenicu da, ako su X i X’ susjedi u grafu, udaljenost(X, Y) razlikuje se od udaljenosti(X’, Y) najviše za 1. Zato je za ovu drugu udaljenost, pod pretpostavkom da smo već poslali prvu, dovoljno poslati samo razliku (-1, 0 ili 1) što možemo dvama bitovima. Ili, još bolje, konstruiramo ternarni niz koji prije slanja pretvorimo u binarni. Detalje ostavljamo čitateljici za vježbu, a cijelo rješenje imate npr. ovdje (napisala ga je moja malenkost, doduše poslije natjecanja).

Tako se na IOI-u pojavila nova tema, koju smo u Hrvatskoj ponekad zvali komunikacijskom složenošću jer se radi o veličini poruka između dvaju programa. Riječ je još i o zadatcima Parrots iz 2011., Supper iz 2012. i Stations iz 2020., a i na CEOI-u 2016. pojavio se zadatak Trick.

Ima to veze i s kompresijskim algoritmima, npr. onima koji smanje veličinu datoteka kad ih zipate, ali za razliku od tih algoritama koji su prilično generički (ne tumače sadržaj datoteka), u ovim problemima traži se kompresija specifična za dani problem. Tako mi je palo na pamet sljedeće pitanje: kako zakodirati partiju šaha, u smislu poteza koji su odigrani? Naravno, pitanje je prilično beskorisno budući da tekstualni zapis šahovske partije nije uopće velik, vjerojatno ste ga i vidjeli (riječ je o Portable Game Notation – PGN), primjerice:

1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8 10. d4 Nbd7 11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5 Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6 23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5 hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5 35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6 Nf2 42. g4 Bd3 43. Re6 1/2-1/2

Ali čemu tražiti svrhu, ni većina drugih informatičkih zadataka nije u ovom smislu korisna. Najbolje stvari su beskorisne. Razmislimo onda kako bismo zakodirali ovakav niz poteza u što manju (binarnu ili tekstualnu) datoteku. Želite li se sami zabaviti razmišljajući o tome, slobodno ovdje prestanite čitati…

Na prvi pogled nije lako jako nadmašiti gornji PGN zapis, ali neke redukcije možemo smisliti relativno brzo. Primjerice: nema potrebe navoditi redni broj poteza; moguće je izostaviti i razmake; ne trebaju nam znakovi x (za jedenje) i + (za šah). Moguća su i sitnija poboljšanja: rezultat na kraju može se zapisati samo jednim znakom, a ponekad (npr. u slučaju mata ili pata) on nije ni potreban jer slijedi iz pozicije; rokadu je moguće prikazati jednim znakom; neka jedenja od strane pješaka (npr. hxg5) dovoljno je pisati kao običan potez (g5) ako ne može doći do zabune, tj. ako u tom trenutku ne postoje dva pješaka koji mogu jesti na g5. Tu ideju možemo proširiti i na druge figure pa pisati npr. e1 umjesto Ke1 ako u tom trenutku samo kralj može odigrati na e1. Nisu ta poboljšanja nimalo loša, ali… zasad smo još uvijek vrlo bliski PGN formatu; i dalje nam trebaju 2-3 znaka po potezu. Ako je jedan znak jedan bajt, riječ je o približno 20 bitova po prosječnom potezu. To je nekoliko puta manje od originalnog PGN zapisa, ali može i bolje!

Dobra je ideja odustati od tekstualnog zapisa, od znakova, jer 8 bitova za jedan znak nije dobar deal. Ono što zapravo zapisujemo polja su šahovske ploče, a njih je 64 = 2⁶, što znači da je za zapis jednog polja dovoljno samo 6 bitova. Zapisujemo li potez kao par (početno polje, završno polje), dovoljno je 12 bitova po potezu – mnogo bolje od tekstualnog zapisa! Ipak, postoje i posebni potezi koje nije moguće tako zapisati: mala/velika rokada, završetak partije (kao predaja bijelog/crnog ili dogovoreni remi) ili izvlačenje nove figure gdje treba precizirati izvlači li se kraljica ili nešto drugo. Srećom, možemo se izvući tako da svaki od tih nekoliko posebnih poteza zapišemo kao neki potez koji je inače nemoguć. Recimo, mala rokada može biti zapisana kao da je riječ o potezu a1-b8, velika kao a1-c8, predaja bijelog kao a1-d8, itd. I dalje smo na 12 bitova po potezu!

Slijedi zamjedba da je umjesto početnog polja (6 bitova) bolje zakodirati figuru koja odigrava potez, jer budući da igrač ima samo 16 figura, svaka može biti određena 4-bitnim kodom. Posebne poteze i ovdje možemo zakodirati kao poteze koji su inače nemogući (npr. za bijelog pješak na a1, b1…, a za crnog pješak na a8, b8…). Već smo na 10 bitova po potezu!

Prethodni odlomci navode nas na pomisao da kompresija još uvijek nije optimalna jer postoji nemogući potezi. Ali ne samo potezi koji su uvijek nemogući, poput bijelog pješaka na prvi red ploče ili bjelopoljnog lovca na crno polje, nego i mnoštvo poteza koji su nemogući u danom trenutku partije. Pozicija na ploči, u bilo kojem trenutku, dopušta samo vrlo ograničen skup poteza i nema potrebe koristiti cijeli skup od 2¹⁰ šahovskih poteza da bismo zapisali što je u tom trenutku odigrano. Drugim riječima, većina kodova uopće ne opisuje dozvoljene poteze i to je očit znak da smo još uvijek rastrošni. To je pogotovo jasno, recimo, na početku partije kada se mogu micati samo pješaci i skakači, ili u završnici kad većine figura više i nema na ploči. Ako je u nekom trenutku samo desetak dozvoljenih poteza, ne bi li nam četiri bita trebala biti dovoljna?

Kako ostvariti tu ideju? Evo kako. Za trenutačnu poziciju odredimo sve dopuštene poteze, sortiramo ih “abecedno” (ili bilo kojim drugim kriterijem), pronađemo onaj indeks u tom nizu na kojem se nalazi potez koji je zaista odigran, i zakodiramo taj indeks. Našao sam na webu podatak (dobiven empirijski) da je prosječan broj dopuštenih poteza u nekoj poziciji približno 31. To znači da bi prosječno 5 bitova trebalo biti dovoljno. Na prvi pogled može biti nejasno kako to iskoristiti jer broj dopuštenih poteza može, naravno, biti i veći – poznata je pozicija iz stvarne partije gdje je taj broj bio 79, a teoretski se on može popeti i do 218 pa nam može zatrebati i 8 bitova. Treba li nam onda neki “separator” koji će dijeliti broj s manje bitova od onog s više bitova? Ne, jer dekoder u svakom trenutku – ako prati poziciju – može znati koliko je dopuštenih poteza, a time i koliko idućih bitova treba pročitati da bi odredio indeks odigranog poteza u tom nizu. Na primjer, ako je 14 dopuštenih poteza, pročitat će četiri iduća bita da otkrije indeks odigranog (makar on bio i 0000).

Dakle, prosječno samo 5 bitova po potezu! Mana je ovog rješenja što i enkoder i dekoder moraju biti programi koji znaju igrati šah, ili barem znaju njegova pravila, jer moraju znati odrediti dopuštene poteze (te ih sortirati po istom kriteriju). Ali čini se da bolje rješenje ne postoji: uočite da svaki proizvoljno dug niz bitova (bio on i slučajan), osim pri samom kraju gdje mu može “nedostajati” bitova, opisuje neku legalnu partiju – što za prijašnja rješenja ni izdaleka ne vrijedi. Ne može bolje! Ili?

Imam i nedovršenu ideju za bolje rješenje. Dosjetka je u tome da, iako pozicija nudi 30ak mogućih poteza, nisu svi jednako vjerojatni: postoje dobri i loši potezi te, što je potez bolji, veća je vjerojatnost da je odigran. To vrijedi i za partije potpunih amatera: u svakoj poziciji postoji značajan broj zbilja besmislenih poteza koje nitko normalan neće odigrati. Kako to iskoristiti? Ovdje nam, nažalost, nije dovoljno da enkoder i dekoder znaju igrati šah. Za ovo rješenje oni bi morali dobro igrati šah, procjenjujući (na jednak način) koliko je koji potez dobar. Pa dobro, to nije neostvarivo, mogu koristiti isti šahovski engine. No što dalje? Umjesto da sortiramo dopuštene poteze po abecedi, sortirat ćemo ih po kvaliteti poteza. Tako će bolji potezi (koji se češće igraju) imati manji indeks pa će za njihov zapis trebati manje bitova. Tako, as a side effect, kvalitetu igrača možemo mjeriti duljinom zapisa njegovih poteza.

No ovdje se javlja problem koji sam natuknuo u jednom od prethodnih odlomaka. Ako postoje, recimo, 32 dopuštena poteza (5 bitova), a odigran je šesti potez po kvaliteti, želimo iskoristiti činjenicu da je indeks mali i zapisati ga koristeći 3 bita. Ali kako će dekoder znati da treba pročitati samo iduća 3 bita, a ne 5? Treba nam, možda, neki separator, ali i on mora biti binaran, i ne smije zauzeti previše bitova… Ako netko ima pametnu ideju kako ovo riješiti, neka napiše u komentar.

Prije nekoliko mjeseci u postu Znanost i algoritmi pisao sam o nekim znanstvenim radovima u kojima glavnu ulogu igraju algoritmi ne toliko različiti od onih na natjecanjima. U međuvremenu sam se sjetio još dvaju dobrih primjera u kojima glavnu ulogu igraju naši algoritmaši. Za početak spomenimo članak u kojem su naši bivši uspješni natjecatelji (Goran Žužić i Filip Pavetić) objavili efikasan algoritam računanja sličnosti stringova. A o drugom primjeru treba napisati nešto više, pa krenimo.

Na 1. kolu HONI-ja 2012. postavio sam zadatak Mars. U njemu je riječ o potpunom binarnom stablu u kojemu možemo proizvoljno zamijeniti lijevo i desno podstablo bilo kojeg vrha – ili, ekvivalentno, odabrati permutaciju listova u kojoj svako podstablo i dalje pokriva uzastopan podniz – tako da zbroj “odbojnosti” susjednih listova (koja je definirana za sve parove u ulaznim podatcima) bude što manji.

Zanimljivo je da sam poslije naišao na znanstvene radove koji rješavaju isti problem. Ovaj članak rješava isti problem za PQ-stablo i primjenjuje ga na poznati problem trgovačkog putnika (Travelling Salesman Problem ili TSP). U ovom članku problem se rješava za K-arna stabla (u binarnom stablu je K = 2) i primjenjuje u bioinformatici za sortiranje gena. Algoritmi i jednog i drugog članka svode se na za binarno stablo, što je i složenost mog rješenja u zadatku Mars.

Ali to nije najbolja moguća složenost! Kao što pokazuje ovaj članak Urlika Brandesa, problem za binarna stabla moguće je riješiti u . Zanimljivo je da je jedan natjecatelj na samom natjecanju pronašao takvo, brže rješenje (o kojem je, dakle, netko prethodno napisao znanstveni rad) – to je bio Luka Kalinovčić na COCI natjecanju. Nakon što sam proučio njegovo rješenje, opisao sam ga (uz vlastito) u službenim rješenjima, tada još ne znajući za cijelu ovu priču. Svaka čast Luki!

Spomenimo i da navedeni Brandesov članak navodi još neke primjene ovog problema kao što je sortiranje piksela u svrhu sažimanja slika, te je predloženi algoritam zbog memorijske složenosti od bolji od algoritma iz članka koji se izvorno bavi tim praktičnim problemom.

Real mathematics is almost wholly useless.

– G. H. Hardy, “A Mathematician’s Apology“

Teorija brojeva nekada je (u vrijeme gornjeg citata) bila praktično beskorisna, ali onda se pojavila kriptografija. Netko anoniman na internetu je napisao: “Mathematicians have had an exceedingly difficult time finding truly useless mathematics. And they’ve been trying for thousands of years.” Poanta nije u tome da velik dio matematike kad-tad nađe svoju primjenu, nego u tome da u početku ta primjena ne postoji – i zato je Hardyjev citat istinit. Ima nešto poetično, a mnogima i nejasno, u matematičaru koji proučava neka opskurna svojstva prirodnih brojeva ili tako nečega, dugo nakon što je prerastao natjecanja i nadmetanja s kolegama, ne zato, nego iz čiste želje i užitka. Iz istog razloga iz kojeg netko drugi rješava sudoku, skuplja salvete, čita hrvatsku poeziju ili proučava analitičke filozofe koji ne zanimaju nijednog od njegovih poznanika.

To ne razumiju oni ljudi (a ima ih mnogo) koji su uvijek goal-oriented, koji svemu traže svrhu i ne vide ljepotu suvišnog – onoga što uopće ne trebamo raditi. Takvi obično ne razumiju umjetnost i uvijek se pitaju što netko želi postići, koje su mu namjere, koja je poruka. Nema poruke! Nema drugih namjera! Takvi bi imali problema i s razumijevanjem ovog bloga. Jer on uza sve svoje korisne stvari, ruku na srce, obiluje i beskorisnim idejama o koječemu. Da budem potpuno jasan, one nemaju nikakvu svrhu, osim samih sebe, svoje potencijalne zanimljivosti i ljepote. Tako je, recimo, Igor Stravinski rekao da glazba nije sposobna izraziti ništa osim sebe same. Very true!

U duhu ovih odlomaka odlučio sam ovdje podijeliti jednu igru koju sam izmislio u snu. (Toliko je čudna da je i mogla nastati samo u snu.) Najprije valja spomenuti postojeću igru The Game koja se igra cijeli život i ima samo jedno pravilo: svaki put kada igrač pomisli na tu igru, on gubi. Cilj je, dakle, ne misliti na tu igru – igra se pobjeđuje misleći o drugim stvarima. Postoje majice na kojima piše “You lose The Game!” koje uzrokuju mnoge poraze u igri (onih igrača koji vide tu majicu).

E sad, igra koju sam izmislio nije naročito originalna u smislu da je potpuno ista kao The Game, samo ima drugačije ime: zove se The Game Too. Ovaj too dolazi kao igra riječima prema The Game 2, tj. The Game Two (druga verzija Gamea).

Odmah se postavlja vrlo opravdano pitanje jesu li dvije igre koje imaju potpuno ista pravila zapravo iste, je li riječ o plagijatu. No ovdje je situacija specifična. Poanta postojanja igre s drugačijim imenom leži u njezinom odnosu s prvom, standardnom igrom. Jer sada postoje igrači koji igraju obje igre. I svaki put kada netko od njih pomisli na The Game, postoji solidna šansa da pomisli i na The Game Too, i onda njegova izjava glasi: “I lost The Game, and I lost The Game Too!” (Vidite li sada svrhu igre riječima two -> too? :))

Postoje i druga zanimljiva pitanja vezana za odnos između ovih igara. Recimo, hoće li se nekome od igrača koji igraju obje igre dogoditi da se sjeti The Gamea, ali zaboravi na The Game Too? A je li moguće, je li ikako moguće, da se sjeti samo The Game Too? Hoće li postojati igrači koji će čuti samo za The Game Too i tako uvijek pobjeđivati u The Gameu, za koju nikada neće čuti? To će biti rijetki sretnici; njima moramo “prodati” neko drugo objašnjenje za ovaj Too da ih ostavimo u neznanju o postojanju standardne inačice igre.

Postoje prijepori oko toga igraju li The Game svi ljudi na svijetu ili samo oni koji znaju za tu igru. Kao autor i apsolutni gospodar igre The Game Too, odlučio sam definirati da tu igru igraju svi na svijetu. To znači da velika većina ljudi na svijetu stalno pobjeđuje u The Game Too (naravno i oni koji gube u The Game) i to je jako dobro. Širenjem glasa o novoj igri povećat će se broj njezinih gubitnika, što je s jedne strane loše (nitko ne voli gubiti), ali s druge strane dobro, jer povećava broj potencijalnih novih igara – novih inačica The Gamea – koje će ti ljudi izmisliti. Vidite, postoji vrlo razuman razlog zašto nisam otišao dalje i izmislio, recimo, The Game Three ili tako nešto – zato jer u takvoj igri onda ne bih pobjeđivao. Moj je cilj da drugi ljudi po uzoru na mene izmisle mnogo, što više novih inačica The Gamea u kojima ću onda ja (budući da ne znam za njih) uvijek pobjeđivati.