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.

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.

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.)

Kako organizirati natjecanje u doba korone

wallpaperflare.com_wallpaper

Kao što svi znate, uslijed epidemije nismo mogli održati Državno natjecanje na planirani način, ali to ne znači da ne razmišljamo o alternativnim mogućnostima.

Pojavio se prijedlog da se Državno održi online. Problem s tom idejom je mogućnost varanja u raznim oblicima i varijantama. Postoji, međutim, način da to varanje spriječimo. Mi ne možemo nadgledati natjecatelje za vrijeme online natjecanja, ali mogu ih nadgledati drugi natjecatelji – njihova konkurencija. 

Preciznije, svakom natjecatelju pridružit će se drugi natjecatelj koji će rješavati Državno natjecanje u istoj sobi i povremeno provjeravati dopisuje li se ovaj prvi s nekim i slično. To mu je u interesu jer su konkurencija. Naravno, provjera će biti obostrana. Na taj način nijedan od dvaju združenih natjecatelja neće smjeti varati jer će ga inače ovaj drugi prijaviti.

No prirodno se nameće očigledno pitanje – što ako obojica odluče varati, npr. pomagati jedan drugome, što im se u konačnici može isplatjeti? I to je rješiv problem, koji ćemo riješiti tako da im pridružimo trećeg natjecatelja, koji će rješavati u istoj sobi i paziti da ova dvojica ne varaju, a naravno da će i oni istovremeno nadgledati njega. Da bi se natjecatelji na prikladan način združili u trojke na odgovarajućim mjestima, svaki natjecatelj trebat će ispuniti obrazac (Google Form) u kojemu će napisati svoju adresu i veličinu svoje sobe u kvadratnim metrima.

Ako se krizni stožer ne složi s ovim prijedlogom, a možda i neće zbog opasnosti od širenja virusa među natjecateljima, pala mi je na pamet još jedna, pomalo neobična ali zapravo izvediva i inovativna mogućnost, koja će zbog svoje originalnosti (ako se ostvari) vjerojatno izazvati pažnju i domaćih i stranih medija. Smatra se da koronavirus ne može izdržati vrlo visoke temperature. Državno će se stoga moći bez problema održati u balonu na vrući zrak. To je nešto skuplja mogućnost, ali i dalje jeftinija od tjednog smještaja u hotelu. Veći baloni mogu ponijeti preko trideset ljudi, ovdje će zbog laptopa i potrebnog razmaka taj broj morati biti najviše dvadeset, pa će nam trebati nekoliko balona ili će se grupe izmjenjivati. 

U svakom slučaju, zaštitne maske i dalje će biti potrebne, ali one ne moraju biti obične kirurške maske kakvih ionako nedostaje na tržištu. Dovoljno učinkovite bit će i maske s fašnika (maskenbala) koje i više odgovaraju mlađahnim natjecateljima: Batman, Spiderman, James Bond, Severina, Mirko Fodor i drugi. Mogućnosti je i više nego dovoljno. Ok, toliko za sada, a službenu obavijest očekujte na neki drugi datum.

Algoritmi u Pythonu

Vrijeme je, napokon, da i ovdje reklamiram knjigu koju smo Nikola i ja ljetos objavili. Riječ je o priručniku Algoritmi u Pythonu, namijenjenom darovitim osnovnoškolcima i onim srednjoškolcima koji tek uče algoritme. Evo linka:

https://shop.skolskaknjiga.hr/algoritmi-u-pythonu-prirucnik-za-ucenje-racunalnog-razmisljanja.html

Za zainteresirane, evo sadržaja:

Screenshot

Od ljudi koji su nam se javili, povratne informacije su izvrsne i čini se da knjiga jako dobro ispunjava svoju svrhu. Jako cijenimo svaki komentar, a pogotovo primjedbu, budući da se nadamo da će priručnik doživjeti još koje izdanje. Tko god je čitao ili bude čitao knjigu, pozivamo ga da nam javi što god mu zapne za oko, bilo pozitivno bilo negativno. Listu ispravaka uočenih pogrešaka održavamo ovdje.

Knjiga sadrži pristupne podatke za evaluator (Pythor) koji je napravio i održava Matej Ferenčević. On zasad sadrži samo zadatke s HONI natjecanja, ali plan je da se dodaju i svi zadatci s novijih službenih informatičkih natjecanja u Hrvatskoj, kao i neki zadatci koji se pojavljuju samo u knjizi Algoritmi u Pythonu.

Ako imate kakvih pitanja o knjizi, napišite u komentar, rado ću odgovoriti. Za kraj, riječ-dvije o mojoj motivaciji za pisanje priručnika, kao i za ovu objavu: cilj je napraviti dobru stvar i proširiti znanje na najbolji mogući način. “Zarada” od ovakvih knjiga je takva da se, s obzirom na uloženo vrijeme i trud, pisanje uopće ne isplati (ako razmišljate na taj način). No gledajući pozitivan učinak kod čitatelja, itekako se isplati.

Top pet novogodišnjih optimizacija

Hello friends. The year is almost over so I have prepared the top 10 optimizations of 2017 for your viewing pleasure. Without forthor ado, let us begin.

—bukefala, 7.7.2017.

Godina se bliži kraju. Po uzoru na nenadmašni post gospodina V. K. o najboljim optimizacijama 2017., ovdje objavljujemo top pet (n)ovogodišnjih optimizacija. No budući da je ovaj blog odavno zastranio u meta vode, riječ je nažalost samo o metaoptimizacijama, tj. optimizacijama informatičke produktivnosti. Jebiga. Bez daljnjeg odugovlačenja, počnimo.

  1. Zadatak dana. Izvrsna novogodišnja odluka: svaki dan riješiti jedan zadatak. Za motivaciju si naručite npr. dnevnik navika koji, između ostalog, ima mjesečnu stranicu u koju upisujete jedan redak za svaki dan tekućeg mjeseca (line per day). Naravno, tko bi pisao cijelu rečenicu – puna rečenica u ovo doba instant komunikacije krupan je zalogaj – ali dovoljno je da u redak zapišete ime zadatka koji ste toga dana riješili. Dakle, ne u neki elektronički dokument, nego pravom olovkom u pravu bilježnicu, u tome je ljepota. Vaša navika tako postaje materijalna i vaša vas draga bilježnica svakodnevno poziva da je ne ostavite neispunjenu.linePerDay
    ——–
  2. Never miss twice. Za praćenje navike rješavanja zadatka dnevno, ili bilo koje druge navike koju želimo usvojiti, možemo koristiti i jednostavniju stvar od line per day iz prethodne točke. Napravimo papirnatu tablicu (habit tracker) u koju za svaki dan stavljamo iksić ako smo toga dana odradili naviku. Cilj je ne prekinuti niz iksića ili, ako se on prekine (a hoće jer nismo savršeni), da onda to ne bude dva dana zaredom. Ja sam si svoje tri tablice (za tri navike, nije važno koje) za 2020. godinu već pripremio i jedva čekaju da ih počnem ispunjavati:imag0949
    Ponovno, važno je da ovo ispunjavate olovkom u bilježnicu, a ne na ekranu. Ako ne razumijete zašto, isprobajte jedno i drugo i bit će vam sasvim jasno koji iksić vam je veći gušt napisati.
    ——–
  3. Natjecateljski dnevnik. O upsolvingu već sam pisao, ali evo dodatnog savjeta: u bilježnici/dnevniku analizirajte svoj performans na svakom natjecanju (ili simulaciji) na kojemu se nađete. Znamo da su važna natjecanja blizu pa je ovo možda dobar čas za takav savjet. Ne mislim na dojmove tipa “bilo je teško, nisam imao koncentracije”, nego na preciznu, objektivnu analizu što ste i zašto napravili na kojem zadatku. To su olimpijci ispunjavali na IOI pripremama u online dokumentu nazvanom Dnevnik simulacija. Evo primjera jednog takvog zapisa (Adrian Beker na jednoj simulaciji 2017. godine):

    Procitao sam sve zadatke te krenuo od drugog jer mi se cinio najjednostavnijim. Nakon nekog vremena uspio sam smisliti cijelo rjesenje te sam ga bez vecih problema nakodirao, tako da je acc pao za nesto manje od sat vremena. Zatim sam presao na treci zadatak, smislio prve dvije parcijale i odlucio ih nakodirati. To se nepotrebno oduljilo zbog glupog buga, tako da mi je ostalo manje vremena nego sto sam predvidjao. Ucinilo mi se da je predzadnja parcijala dosta laksa od cijelog rjesenja pa sam ju pokusao smisliti, ali sam negdje u toku odlucio ipak nakodirati prve dvije parcijale na prvom jer su se cinile trivijalnima. Na kraju sam na tome dobio TLEove, vjerojatno zbog prevelike konstante. Zadnjih nesto manje od sat vremena proveo sam dovrsavajuci ideju za treci i kodirajuci rjesenje koje je trebalo dobiti 80%, no bilo je preruzno da bih stigao u tom vremenu.

    Poanta je u tome da razvijete natjecateljske metavještine: taktičnost, bistriji um i da u svakom trenutku točno znate što, kako i zašto rješavate. A i psihološki će vam biti lakše ako nakon neuspjeha precizno zapišete što, kako i u kojem trenutku je pošlo krivo, umjesto da ostanete u onom nejasnom, maglovitom i muljevitom osjećaju “sjebo sam, ne vrijedim” i tugaljivo bauljate hodnicima u potrazi za smislom života.

  4. Metaoptimizacije iz arhive Blogaritma. Svašta sam nadrobio u ove nepune dvije godine (od prvog aprila 2018. otkad blog postoji), od čega ima i korisnih stvari. (Iako su one druge, beskorisne stvari ono što me više veseli.) Na primjer, opširnije o navici zadatak dnevno govori ovaj post od prije godinu dana. Ako ste baš hard core, pročitajte i knjigu koju u njemu preporučujem.
    ——–
  5. Teina radna bilježnica za novogodišnje odluke. Zgodna i korisna poveznica s bloga koji toplo preporučujem. Inače, Tea je vrlo uspješna diplomirana FER-ovka koja je, tko bi rekao, programiranju “dala nogu” i odlučila raditi stvari koje više voli. Spomenimo za kraj, eto, i takvu novogodišnju mogućnost.

Informatika i dopamini

Postoji nekoliko razloga zašto se bolje baviti informatičkim natjecanjima nego bilo kojim drugima. (Ja sam jedne godine odustao od IMO-a, iako sam bio prošao, da bih se usredotočio na IOI.) Zabavnije je. Djeluje kao igrica, riješiš zadatak i dobiješ ACCEPTED. Dopamin fiks!

Malo ću pojasniti. Dopamin je hormon koji se javlja, između ostalog, kao osjećaj nagrade. Svi smo manje ili više ovisnici o njemu ako koristimo pametne telefone na kojima dobivamo notifikacije. Mobitel zavibrira, netko nam je poslao poruku! Ili nas je lajkao! Ili je objavljen novi post na Blogaritmu! Svaki taj signal ispušta malu količinu dopamina u mozgu. Pa onda počinjemo provjeravati mobitel i bez osobitog razloga, očekujući notifikaciju tj. “nagradu”. Kao rezultat, sve se teže usredotočiti na bilo što, teško je čitati dugu lektiru, teško je mirno pratiti predavanje od sat vremena. Sve je dosadno ako je sporo. A zapravo je sporost smisao života.

Rješavanje informatičkih zadataka na pozitivan način iskorištava našu želju za instant gratifikacijom. Najbolji natjecatelji mojega vremena – Goran Žužić, Stjepan Glavina i Ivan Katanić – imali su periode kada su tjednima toliko divljački rješavali zadatke na online judgevima (Goran na starom UVA judgeu, a ova dvojica na Spoju) da su nerado išli spavati. (Jeste li ikada vježbali toliko intenzivno da vam se u glavi totalno promijenio film i život kao da je postao nešto drugo? Slično zaljubljenosti nekakvoj.) Ovisnost o onom trenutku kad submission pozeleni donijela im je mnogo dobroga.

spojstatus

U matematici toga nema. Tamo ste doma riješili zadatak i to po defaultu nitko osim vas ne zna, a ni vi niste uvijek sigurni je li vam rješenje ispravno. Nema potvrde i nema zelene nagrade koja stimulira mozak i kemikalijom vas motivira da to ponavljate. Postoji i filozofska razlika. U matematici je nešto “ispravno” jer se pretpostavlja postojanje apsolutne istine (ovisne o aksiomima) do koje se dolazi zaključivanjem. U informatici, s druge strane, rješenje je ispravno ako daje rezultate koji se poklapaju s očekivanim rezultatima. To je sve, u evaluaciji nema zaključivanja, gledanja koda, nema nikakve suštine, esencije, sve je result-based. Tako je i u znanosti: teorija nije točna jer je netko do nje došao nekakvom mudrošću, nego je točna ako odgovara podatcima i mjerenjima. Ta razlika (racionalizam vs. empirizam, platonizam vs. pozitivizam) vidljiva je i u tipu ljudi koje sam, u svom vrlo ograničenom uzorku, upoznao na PMF-u (matematici) i na FER-u. Čini mi se da je među matematičarima veći postotak apstraktnih i religioznih duša nego među informatičarima.

Znam, ovo je još jedan meta post: ne govori ni o kakvom algoritmu ni zadatku, nego filozofira okolo. Rekli ste mi, znam, da bi bilo dobro objavljivati više tehničkih savjeta, a manje savjeta o savjetima. Slažem se: pozivam one koji divljački vježbaju da napišu post o, recimo, najboljem zadatku koji su riješili toga tjedna, poznatim ili nepoznatim algoritamskim trikovima, forama koje su koristili u nekom kodu, bilo što, pa da i ovaj blog postane “by Adrian i prijatelji”. Jer ja sam malo usporio s rješavanjem zadataka, ne fiksam se accovima u zadnje vrijeme. Kao što bi rekla stanovita pjevačica: plači zemljo!