Neočekivani graf u još dva zadatka sa stringovima

Javlja mi Kišić da se jučer na Open Cupu pojavio super zadatak za temu iz prethodnog posta. Zadatak možete pronaći ovdje, vrlo je lijep, i još jedan dokaz proročke snage Blogaritma.

A sjetio sam se onda i jednog svog zadatka iz iste “kategorije”, također sa stringovima, koji se neočekivano svodi na graf i koji sam začudo zaboravio u prethodnom postu. To je zadatak Wordplay sa Spoja, meni je dobar, a i ljudima se svidio.

Kad smo već kod Spoja, znate li što informatičar radi u subotu navečer? Pa na Spoju je! — A znate li što radi kad dobije WA (Wrong Answer)? Radi ovo.

Tema dana: neočekivani graf

Sanjao sam sfingu koja daje proročanstva i mogao sam postaviti jedno pitanje. Pitao sam: kada će Blogaritam ponovno biti o algoritmima? Sfinga je odgovorila: hokus pokus, bogovi su odlučili, to će biti danas!

Pa evo onda neka bude.

Znamo da se grafovi prirodno pojavljuju u mnogim zadacima, npr. kad je riječ o gradovima i cestama, poznanstvima, širenju virusa i slično. No postoji značajan broj zadataka koji se svode na graf a da to nije očito, nego se graf konstruira na netrivijalan i dosjetljiv način. Ti su zadatci često vrlo lijepi i vrijedi im posvetiti temu dana. O jednom takvom zadatku već sam pisao u postu Zadatak dana: kineski poštar.

Krenemo li od očitijeg prema manje očitom, počet ćemo od zadataka gdje treba pronaći najmanji broj nekakvih operacija da bismo nešto učinili. Shvatimo li operaciju kao prijelaz iz jednog stanja u drugo, prirodno se nameće graf čiji su vrhovi stanja, a bridovi operacije. Ovaj graf ne treba eksplicitno konstruirati, tj. pohraniti sve njegove
bridove, što možda ne bi bilo ni lako učiniti (možda ih je previše, a trebalo bi i nekako numerirati stanja). Dovoljno je pustiti npr. BFS i za pamćenje posjećenih vrhova koristiti npr. set:

U idućim zadatcima naivan BFS nije dovoljno efikasan pa je potrebna dodatna dosjetka:

I još jedan ovog tipa (preporuka Marina Kišića):

Drugu kategoriju čine zadatci gdje graf izvire iz neke tablice. O nekima od njih pisao sam u postu Tip of the day: tablica je bipartitan graf, gdje sam opisao dvije različite transformacije tablice u bipartitni graf. A malo drugačiji zadatak dao mi je Marin Kišić: Sorting a Grid.

Treću kategoriju čine zadatci gdje se konstruira graf na kojemu je rješenje neki flow. Lakši takav zadatak je A (Blokada) – Studentsko 2016., a teži je zadatak Orders (CEOI 2008.) – rješenje i testne primjere možete naći ovdje.

Naravno, najbolji su oni zadatci koji se ne mogu lako kategorizirati. Odlični zadatci s neočitim graf rješenjem pojavili su se u zadnjoj sezoni HONI-ja:

… kao i na zadnjem VRSIH-u:

Jedan teški za kraj (preporuka Patrika Pavića): Subset with zero sum. Ima ih još mnogo, slobodno dopišite u komentar.

Tip of the day: testiranje

Nekada na važnim natjecanjima nije bilo full feedbacka pa smo nervozno čekali rezultate tumarajući po hodnicima, koji su uglavnom dolazili isprintani (rezultati, ne hodnici) za svakog natjecatelja posebno – ishodi po pojedinim primjerima. I danas je slična situacija na županijskom i na HONI-ju gdje nema feedbacka, ali nekada je tako bilo i na državnom (koje se zvalo DMIH), na HIO-u, IOI-u i svugdje. Full feedback pojavio se, ako se ne varam, na IOI-u 2010. Na CEOI-u 2013. u Primoštenu još uvijek ga nije bilo, a na državnom je uveden 2015. gdje je ključnu ulogu odigrao Ante Đerek, između ostalog motiviran e-mail prepiskom nakon žalbi sa županijskog. U jednom od tih mailova Stjepan Glavina napisao je poznatu rečenicu: “Tradicionalni tip natjecanja mora nestati.”

Ovakvi incidenti su razlog zašto mislim da tradicionalni tip natjecanja (HONI, državno, CEOI, IOI prije 2010.) mora nestati. A nisam jedini koji tako misli [1]. Bodovanje je vrlo nepravedno. “Manje” kriva rješenja znaju dobivat više bodova od “više” krivih. Zna se desit i da točna rješenja s malim bugom dobiju manje bodova od potpuno krivih, ili čak nula bodova. Faktor (ne)sreće je prevelik. Drame s bugovima se događaju na svakom takvom natjecanju.

Prije full feedbacka, testiranje rješenja “s brutforsom i generatorom” bila je standardna stvar koju su jači natjecatelji tijekom natjecanja radili na svim zadatcima gdje je to imalo smisla. Jednom sam komentirao da nerado testiram jer volim misliti da sam riješio zadatak, barem tih nekoliko sati, umjesto da si testiranjem srušim rješenje. “Kurdija, to je i ideja”, odgovorio mi je Žužić odmahujući glavom u nevjerici.

Full feedback ima i određenih mana. Neki misle da je njime djelomično izgubljen važan dio natjecanja – spomenuto testiranje, te da rezultati dobiveni odmah “na pladnju” nisu nešto što je inače realno. S organizacijske strane ima više posla – zadatci moraju biti teži nego inače (jer natjecatelji zbog feedbacka troše manje vremena i manje griješe), s više parcijala da se dobije dobra disperzija bodova (koja se prije lakše dobivala zbog raznih neotkrivenih bugova), a greška u evaluaciji ili testnim primjerima košta više nego prije jer utječe na tijek natjecanja.

Osim na onim natjecanjima gdje još uvijek nema feedbacka (mislim da i Codeforces ulazi u tu kategoriju), danas testiranje koristimo i onda kada nam evaluator kaže da rješenje ne valja, ali ne znamo zašto pa moramo naći primjer na kojemu pada. Errichto dobro objašnjava kako se to radi:


Ugrubo i sažeto, evo bash skripte kakvu sam nekada koristio (njegova je malo drugačija):

echo > o1  # napravi prazan prvi output
echo > o2  # napravi prazan drugi output
while diff o1 o2; do     # dok su outputi jednaki
    ./gen.py > t         # generiraj random primjer t
    ./test.exe < t > o1  # o1 = rjesenje(t)
    ./brute.exe < t > o2 # o2 = brutfors(t)
    printf '.'           # ispisi tocku za svaki testirani primjer
done

Poziva se iz Linux terminala:

bash testiraj.sh

… ili (nakon postavljanja chmod +x testiraj.sh):

./testiraj.sh

Update: sad uočavam da sam riječ testiranje u dvama nedavnim postovima (ovom i ovom) koristio u značenju evaluacija tj. isprobavanje na službenim testnim primjerima, dok se u ovom postu testiranje odnosi na stress-testing rješenja za vrijeme natjecanja kada službeni testni primjeri još nisu dostupni. Tu dvoznačnost mogao bih otkloniti tako da u prethodnim postovima svugdje napišem evaluirati umjesto testirati, ali to mi se ne da i vjerojatno je i ovako jasno o čemu se radi.

Tip of the day: testiranje na pythonovski

Kao nastavak prethodnog posta Tip of the day: testiranje zadataka sa HSIN-a, ovdje ću testiranje rješenja napisati u Pythonu (a ne u Bashu), i to s dodatnim funkcionalnostima kao što su automatsko preuzimanje testnih primjera, mjerenje vremena izvođenja i paralelizacija. Ipak preporučujem da najprije pročitate navedeni post radi razumijevanja načina pozivanja programa, preusmjeravanja inputa/outputa i diff-anja, što ćemo koristiti i ovdje. Osim samih skripti, ideja je i pokazati neke mogućnosti Pythona.

Želimo, za početak, zaobići ručno preuzimanje zip datoteke i ručno extractanje odgovarajućih testnih primjera iz nje. Nema problema! Evo skripte download.py, koja kao argumente prima ime zadatka i URL zip datoteke s njegovim testnim primjerima:

#!/usr/bin/python3
from io import BytesIO
from zipfile import ZipFile
from urllib.request import urlopen
from sys import argv

ime_zadatka = argv[1]
url = argv[2]

resp = urlopen(url)
zipfile = ZipFile(BytesIO(resp.read()))
for filename in zipfile.namelist():
    if filename.startswith(ime_zadatka):
        zipfile.extract(filename, '.')

Primjer preuzimanja testnih primjera za zadatak Modulo s 1. kola HONI-ja 2006.:

./download.py modulo https://hsin.hr/honi/arhiva/2006_2007/kolo1_testpodaci.zip

Ishod će biti stvaranje datoteka modulo/modulo.in.1, modulo/modulo.out.1 i tako dalje, gledajući iz direktorija u kojem je skripta pokrenuta. Izmjenu skripte po vlastitim željama ostavljamo čitateljici za vježbu.

Ako se nalazimo unutar direktorija u kojemu je naše rješenje i testni primjeri, skripta koja testira sve primjere, usput mjereći vrijeme izvođenja za svaki primjer, izgledala bi primjerice ovako:

#!/usr/bin/python3
from os import listdir, popen
from time import time
from sys import argv

ime_zadatka = argv[1]
rjesenje = argv[2]

for filename in listdir('.'):
    if '.in.' in filename:
        print('\nTestiram {}...'.format(filename))
        start_time = time()
        popen('./{} < {} > tmp.out'.format(rjesenje, filename)).read()
        print('Vrijeme = {:.3f} sekundi'.format(time() - start_time))
        p = popen('diff -w tmp.out {}'.format(filename.replace('.in.', '.out.')))
        print(p.read() or '---------- OK ----------\n')

Dakle, za svaku *.in.* datoteku (ulazni primjer),  unutar popen-a kao novi proces pokrećemo naše rješenje, preusmjeravamo taj primjer na ulaz, a naš izlaz u datoteku tmp.out koju potom uspoređujemo (diff) sa službenim *.out.* izlazom. Ako je diff prazan, ispisujemo OK. Za mjerenje izvođenja ključna je funkcija time.time() koja daje trenutačno vrijeme u sekundama. Poziv skripte za zadatak Herman izgledao bi npr. ovako:

./test.py herman herman.exe

Nedostatci? Primjeri se neće nužno izvesti prirodnim redoslijedom i možda je moguće usporedno provjeravati više primjera (na više jezgri procesora) radi bržeg testiranja. Obje stvari možemo riješiti tako da napravimo četiri procesa (multiprocessing.Pool(4)) od kojih svaki paralelno testira svoj dio testnih primjera i vraća ishod kao string (npr. “Primjer 1OK, 0.1 sekundi“), koje onda na kraju možemo sortirati abecedno pa će primjer 1 biti prvi.

#!/usr/bin/python3
from os import listdir, popen
from time import time
from sys import argv
from multiprocessing import Pool

ime_zadatka = argv[1]
rjesenje = argv[2]

def testiraj(filename):
    output = '\nTestiram {}...\n'.format(filename)
    ekstenzija = filename.split('.')[-1]
    start_time = time()
    popen('./{} < {} > tmp{}.out'.format(rjesenje, filename, ekstenzija)).read()
    output += 'Vrijeme = {:.3f} sekundi\n'.format(time() - start_time)
    p = popen('diff -w tmp{}.out {}'.format(ekstenzija, filename.replace('.in.', '.out.')))
    output += p.read() or '---------- OK ----------\n'
    return output

with Pool(4) as p:
    ishodi = p.map(testiraj, [filename for filename in listdir('.') if '.in.' in filename])
for i in sorted(ishodi):
    print(i)

I ovdje se neke stvari mogu doraditi, može se dodati timeout tj. ograničiti vrijeme izvođenja, a moguće se i pobrinuti da herman.in.10 ne dođe prije herman.in.2 iako je prije po abecedi. Sve to i mnogo više ostavljamo… znate već.

Kampovske igre – članak iz 2011.

U pretprošloj objavi bila je riječ o igrama botova i AISportsu. Ovdje se prisjećam HSIN-ove Zimske škole informatike u Krapini 2011. godine kada smo Ivica Kičić i ja organizirali jednu takvu igru. Nije to bio prvi put da se na kampu radi igra botova, Kalinovčić i ekipa organizirali su nešto slično na nekim još davnijim kampovima, mislim da je u pitanju bila neka inačica igre Achtung, die Kurve!. Naša je igra bila drugačija, jednostavnija i možda manje zanimljiva za gledanje sa strane. Na turniru je pobijedio Tomislav Tunković.

O toj igri napisao sam članak za Matematičko-fizički list koji možete pronaći ovdje. Taj članak i nije naročito stručan jer tada nisam znao za teoriju igara, miješane strategije, strojno učenje i slično. Vjerojatno postoje i bolje strategije od navedenih.

Zadatak dana: Easter eggs ili Čudnovate permutacije uskršnjih jaja

Izvor: https://www.nsa.gov/News-Features/News-Stories/Article-View/Article/1627299/september-2015-puzzle-periodical/

Alice has a dozen cartons, arranged in a 3×4 grid, which for convenience we have labeled A through L:

A B C D
E F G H
I J K L

She has randomly chosen two of the cartons and hidden an Easter egg inside each of them, leaving the remaining ten cartons empty. She gives the dozen cartons to Bob, who opens them in the order A, B, C, D, E, F, G, H, I, J, K, L until he finds one of the Easter eggs, whereupon he stops. The number of cartons that he opens is his score. Alice then reseals the cartons, keeping the eggs where they are, and presents the cartons to Chris, who opens the cartons in the order A, E, I, B, F, J, C, G, K, D, H, L, again stopping as soon as one of the Easter eggs is found, and scoring the number of opened cartons. Whoever scores lower wins the game; if they score the same then it’s a tie.

For example, suppose Alice hides the Easter eggs in cartons H and K.
Then Bob will stop after reaching the egg in carton H and will score 8, while Chris will stop after reaching the egg in carton K and will score 9. So Bob wins in this case.

Who is more likely to win this game, Bob or Chris? Or are they equally likely to win?

Pokušajte riješiti zadatak, a tek onda čitajte dalje.

Rješenje možete naći na gornjoj poveznici, ili malo ljepše napisano na http://datagenetics.com/blog/march12017/index.html.

Rezultat je vrlo neobičan jer se protivi mojoj, a možda i vašoj intuiciji, koja kaže da poredak ne bi smio igrati nikakvu ulogu. Riječ je o običnim permutacijama; po čemu je ABCDEFGHIJKL bolja (i uopće drugačija) od AEIBFJCGKDHL? U čemu je fora?

Ovaj zadatak vidio sam kada ga je shareao docent Vedran Čačić s PMF-a na (bivšoj) društvenoj mreži Google+, gdje je dao i dobar uvid u odgovor na ovu neobičnost, te postavio dodatni zadatak koji će osobito informatičarima biti zanimljiv:

Of course, it’s completely obvious that there are no absolutely better/worse strategies, as long as you stick to bijections between [1..12] and [A..L] (after all, that’s why S12 is called the symmetry group), so there must be some intransitivity in the “order” of strategies. Can you find a permutation that beats Bob’s ABCDEFGHIJKL, yet is beaten by Charlie’s AEIBFJCGKDHL? 🙂

AISports i zaigrani botovi

Ovaj post napisan je u suradnji s mojim prijateljem Joelom Mislavom Kunstom.

Na Blogaritmu je uglavnom riječ o natjecateljskom programiranju koje se većinom orijentira na determinističke algoritamske zadatke. Ti su nam zadatci svima poznati i zabavni, ali postoje i drugi oblici programiranja koji su i kompetitivni i jako zabavni. Jedan je od njih natjecanje botova u igranju igara. Bot je samo drugo ime za program koji odrađuje neki zadatak automatski, umjesto čovjeka. Programiranje botova koji igraju igre razlikuje se od klasičnog natjecateljskog programiranja:

  • Programi koje isprogramiramo mogu se natjecati međusobno – protivnik nije statičan.
  • Uglavnom nema optimalnog ili očekivanog rješenja.
  • Program može krenuti jednostavno, te ga konstantno možemo poboljšavati dok se natječemo s drugima i dobivamo povratnu informaciju o tome koliko je dobar.

Takvi zadatci, koji su zapravo igre, mogu zahtijevati mnogo više vremena od standardnih zadataka s natjecanja, ali početna rješenja mogu se napraviti relativno brzo. Kod ovakvih se zadataka u manjoj ili većoj mjeri koriste algoritmi iz područja umjetne inteligencije. Oni su ponekad drugačiji od onih egzaktnih koje koristimo u zadatcima standardnog natjecateljskog programiranja, ali ne toliko koliko se može na prvi pogled činiti: ne postoji jasna granica između “umjetne inteligencije” i ostalih algoritama. U umjetnoj inteligenciji itekako vam može pomoći poznavanje pohlepnih algoritama, rekurzije i backtrackinga, dinamičkog programiranja, traženja što boljih putova u grafovima te ostalih optimizacijskih i heurističkih algoritama, iako će se ovdje naći i algoritama strojnog učenja koji vam možda još nisu poznati. Umjetna inteligencija široko je i zanimljivo područje i sve je veća potražnja za ljudima koji su u njemu vješti.

Neka od natjecanja ovog tipa organizira poznati Kaggle, ali on nije primarno posvećen natjecanju botova, nego više strojnom učenju. Poznata natjecanja botova koji igraju igre su studentsko timsko natjecanje u Starcraftu koji igraju botovi, Halite koji se održava jednom godišnje, te jedna od novijih platformi, AISports, koja najavljuje veći broj igara i konstantna natjecanja. OpenAI nudi mnogo starih igara s igraćih konzola za koje možete napraviti bota, no infrastruktura za natjecanja te jednostavan početak nisu na visokoj razini. 

Jedan od osnivača AISports-a moj je prijatelj Joel Mislav Kunst. Na toj platformi možete se baviti samo logikom svog bota, a infrastruktura za simulaciju, debugiranje i natjecanja napravljena je za vas. Postoji biblioteka za Python i Typescript, ali to je samo wrapper za vrlo jednostavan API, te možete koristiti bilo koji jezik. Kod se trenutačno izvršava lokalno na vašem računalu. Zasad je na raspolaganju jedna igra – dame tj. checkers – a u planu je dodavanje barem jedne nove igre mjesečno. Želite li malo začiniti svoj karantensko-natjecateljsko-programerski život, okušajte se u izradi bota koji pobjeđuje druge botova. Dojmove, ideje, primjedbe i komentare javite ekipi na Discordu, jako su pristupačni, pažljivo slušaju i trude se unaprijediti platformu.

(P.S. U jednom od idućih postova bit će riječ o igri botova koja se igrala na jednom davnom HSIN-ovom kampu.)