Srednješolsko tekmovanje ACM iz računalništva in informatike
Minolovec — tekmovanje programov
Minolovec (Minesweeper) je znana igra za enega igralca. Na karirasti mreži so postavljene mine, pri čemer so polja na začetku zakrita in ne vemo, kje se mine nahajajo. Če odpremo polje, na katerem ni mine, dobimo podatek o tem, koliko min je na sosednjih poljih. Če odpremo polje, na katerem je mina, igre ni konec (kot pri običajnem minolovcu), pač pa jo lahko nadaljujemo. Naloga je napisati program, ki odpre vsa polja, na katerih ni min, pri tem pa odpre čim manj takih polj, na katerih so mine.
Na tekmovanju bomo program vsakega tekmovalca preizkušali na več minskih poljih z različnim številom min (velikost mreže bo podana na začetku igre in bo predvidoma majhna, na njej bo največ 1000 celic), razvrstili pa jih bomo glede na skupno vsoto min, ki so jih pohodili, preden so odprli vsa polja, na katerih ni min.
Za vsa minska polja, na katerih bomo preizkušali tekmovalce velja, da v nobenem izmed štirih kotov (torej na koordinatah (0,0), (širina-1,0), (0, višina-1), (širina-1, višina-1)) mine zagotovo ni.
Program med igro ne sme odpreti že odprtega polja.
Funkcije, ki jih morajo napisati tekmovalci
Vsak tekmovalec mora v izbranem programskem jeziku implementirati spodaj naštete funkcije, ki so del razreda Igralec. Funkcije so na tem mestu deklarirane v nekakšnem metaprogramskem jeziku, ki je, upamo, razumljiv vsem; deklaracije v tvojem programskem jeziku pa bodo verjetno videti nekoliko drugače.zacni_igro(int sirina, int visina, int stevilo_min) — ocenjevalni program jo pokliče na začetku vsake igre in ji sporoči velikost igralnega polja in število min na njem.
(x,y) = naslednja_poteza() — sistem pokliče to funkcijo za vsak korak igre, funkcija pa mora vrniti koordinati polja, ki ga želi tvoj igralec v tem koraku odpreti. Koordinati sta od 0 pa do sirina-1 oziroma visina-1.
izid(int x, int y, boolean pohodil_mino, int stevilo_min_na_sosednjih_poljih) — sistem jo vedno pokliče takoj za funkcijo naslednja_poteza. Parametri:
- spremenljivki x in y vsebujeta koordinato polja, ki si ga želel odpreti v funkciji naslednja_poteza
- pohodil_mino pove, če je na tem polju mina,
- stevilo_min_na_sosednih_poljih pove, koliko min se skupaj nahaja na tistih poljih, ki si z (x,y) delijo stranico ali vogal. Ta podatek dobiš tudi v primeru, da si odprl polje, na katerem se nahaja mina.
konec_igre(string razlog) — sistem to funkcijo pokliče, ko je konec igre. Parameter razlog je le informativnega značaja.
(Primer igralca, ki igra trivialno strategijo (v pythonu).)
Za vsako izvedeno igro se naredi nov objekt razreda Igralec.
Vsaka zasnova za igralca vsebuje dve datoteki — datoteka mine.{cpp/cs/py/java/lua/pas/...} vsebuje vse potrebno za komunikacijo z ocenjevalnim programom in je ne spreminjaj. Datoteka igralec.{cpp/cs/py/java/lua/pas/...} pa vsebuje le en razred, Igralec, ki ga lahko spreminjaš. Ta razred ima tudi spremenljivko Ime, ki jo nastavi na svoje ime.
Omejitve
Program lahko za posamezno igro porabi vsega skupaj največ 10 minut procesorjevega časa (na enem jedru 3.3GHz Intel Xeon W3680); v kateremkoli trenutku lahko uporablja največ 2GB pomnilnika. Dovoljena je uporaba 64-bitnega naslavljanja in ostalih zmogljivosti novejših procesorjev (npr. ukazi SIMD), če izbrani programski jezik to omogoča. Prepovedana je uporaba sistemskih klicev (npr. spreminjanje sistemskih nastavitev, časovnikov, ...), dovoljena pa sta dostopanje do podatka o trenutnem/porabljenem času in izpis na zaslon.Razvojno okolje
Za razvoj boš potreboval ocenjevalni program in zasnovo za tekmovalca. Ocenjevalni program deluje kot strežnik, na katerega se poveže tekmovalec. Vse potrebno za komunikacijo je že priloženo v zasnovi za tekmovalca.
Ocenjevalni program poženeš iz ukazne vrstice (mine_test.exe oz. mine_test.py na Linuxu in Mac OS X-u), s parametri pa mu lahko poveš število iger, ki naj se izvedejo, velikost igralnega polja in število min na njem. Minska polja lahko tudi zapišeš in prebereš iz datotek, tako da lahko primerjaš obnašanje svoje rešitve na enakih minskih poljih večkrat, ali pa testiraš na svojih minskih poljih.
Ko ocenjevalni program teče, poženeš še svojo rešitev; če pa ga zaženeš brez parametrov, izpiše pomoč — vse možnosti.
Zasnova za tekmovalca je trenutno na voljo v naslednjih jezikih:
Lahko pa si preneseš tudi izvorno kodo za ocenjevalni program (napisan v pythonu); potreboval jo boš tudi, če ne programiraš na Windowsih.Če bi želel pisati v jeziku, ki ga ni na zgornjem spisku, ali pa imaš v zvezi s tekmovanjem programov kakršna koli vprašanja, pošlji e-mail na blaz.novak@ijs.si.
Pravila tekmovanja
Na to tekmovanje se ni treba posebej prijavljati. Tiste, ki vas sodelovanje v tem tekmovanju zanima, vabimo, da nam to sporočite po elektronski pošti (rtk-info@ijs.si). V sporočilu tudi navedite, v katerem programskem jeziku bi predvidoma napisali svoj program.
Programe sprejemamo do vključno 12. marca 2011, lahko pa nam jih pošljete tudi že prej. Izvorno kodo svojega programa nam pošljite po elektronski pošti na naslov rtk-info@ijs.si. Končni rezultati bodo objavljeni po zaključku 6. tekmovanja ACM in IJS v znanju računalništva (26. marca 2011).
Na tem tekmovanju programov lahko sodeluje kdorkoli, ne glede na starost, izobrazbo, itd. Objavili bomo rezultate vseh prejetih programov, najbolje uvrščeni dijak in najbolje uvrščeni študent pa bosta dobila tudi praktične nagrade.