Concurs Flood Wars 2014, clasele 7/8

From Algopedia
Jump to navigationJump to search

Concurs: jocul Flood Wars

Scrieți un program care să joace jocul Flood Wars (instalabil pe Android). Elevii care vor reuși să termine implementarea jocului vor intra în concurs. În cadrul concursului fiecare program va juca cu fiecare alt program două jocuri, unul "tur" și unul "retur".

Descriere joc

Jocul Flood Wars se joacă pe o tablă dreptunghiulară. Toate căsuțele sînt inițial colorate cu diferite culori, din totalul de cinci culori disponibile. Primul jucător pornește în colțul din stînga-jos, iar al doilea jucător din colțul din dreapta-sus. Cînd îi sosește rîndul jucătorul trebuie să își aleagă o culoare pe care vrea să o absoarbă. Culorile curente ale celor doi jucători nu pot fi selectate.

Odată aleasă, aria acelui jucător se schimbă în culoarea corespunzătoare, absorbind pătratele adiacente de aceeași culoare. Jucătorul care reușește să absoarbă mai multe pătrate cîștigă.

Ce se cere, pe scurt

Dată o tablă de joc și jucătorul care este la mutare, jos sau sus, trebuie să alegeți o culoare din cele cinci disponibile. Culorile actuale ale celor doi jucători nu pot fi alese. Voi și oponentul vostru jucați pe rînd, schimbînd culorile, pînă ce tabla nu mai poate fi modificată. La final jucătorul care are mai multe pătrate de culoarea sa cîștigă.

Programul vostru va citi o tablă de la intrarea standard (citire cu fgetc(stdin)) reprezentînd o configurație a tablei de Flood Wars, apoi va executa o mutare prin selectarea unei culori disponibile, o va aplica din colțul său și, în final, va scrie la ieșirea standard (scriere cu fputc(c, stdout)) o altă tablă, configurația tablei după executarea mutării. Fiecare program va muta pe rînd, avînd la dispoziție 0.1 secunde o secundă pentru mutare.

Tabla de start

Următorul exemplu arată o posibilă tablă de start:

.#+#.*.@.@
@.+*@.+*#+
**#++@**#@
#@#@.@@+@#
++@++@#.@.
**##*@*#++
#@@*.+*.*+

Sînt șapte linii și zece coloane pe fiecare linie. Culorile sînt codificate cu caracterele @ # + . *.

  1. Tabla de joc are cel puțin 10 linii și 10 coloane și cel mult 50 de linii și 50 de coloane.
  2. Colțurile celor doi jucători, stînga-jos și dreapta-sus au culori diferite.
  3. Odată început jocul jucătorii vor putea selecta una din trei culori: din cele cinci culori cele două culori ale jucătorilor nu vor fi disponibile.
  4. Datele de intrare și cele de ieșire nu vor conține spații sau alte caractere în afara grilei de culori și caracterul sfîrșit de linie ('\n') la finalul fiecărei linii (inclusiv ultima).

Tabla unui joc în desfășurare

.#+#.*.@.@
@.+*@.+*#+
**#++@**#@
#@#@.@@+@#
++@++@#.@.
**##*@*#++
*@@*.+*.*+

Această tablă arată o mostră de joc după ce primul jucător (stînga-jos) a selectat culoarea *. Remarcați că el nu putea să selecteze @, deși ar fi fost o mutare favorabilă, deoarece aceasta era culoarea jucătorului advers. Prin această mutare el a absorbit încă două căsuțe * care fac acum parte din culoarea lui.

Mutările (selecția unei culori valide) se vor face prin înlocuirea colțului vostru cu culoarea selectată, precum și a tuturor pătratelor de aceeași culoare cu culoarea originală care sînt accesibile din colțul vostru prin deplasare pe orizontală sau verticală (nu și pe diagonală).

.#+#.*.@.+
@.+*@.+*#+
**#++@**#@
#@#@.@@+@#
++@++@#.@.
**##*@*#++
*@@*.+*.*+

Această tablă arată o mostră de joc după ce al doilea jucător (dreapta-sus) a selectat culoarea +. El a absorbit încă un pătrat.

.#+#.*.@.+
@.+*@.+*#+
**#++@**#@
#@#@.@@+@#
++@++@#.@.
####*@*#++
#@@*.+*.*+

Această tablă arată o mostră de joc după ce primul jucător (stînga-jos) a selectat culoarea #. El a absorbit încă două pătrate.

Jocul se termină atunci cînd toate pătratele sînt absorbite sau înconjurate de unul din jucători, sau după ce au fost efectuate 150 de mutări.

Rîndul la mutare - Cine sînt eu?

Pentru a putea decide cine este la mutare trebuie să adăugăm această informație tablei de joc. Astfel, la intrare vom citi pe prima linie un singur caracter J (stînga-jos) sau S (dreapta-sus) care codifică jucătorul la mutare. De asemenea vom scrie la ieșire nu numai tabla rezultată în urma mutării ci și litera ce codifică jucătorul opus, pe prima linie, înaintea tablei. Folosind exemplul anterior, tabla de start va fi codificată astfel:

J
.#+#.*.@.@
@.+*@.+*#+
**#++@**#@
#@#@.@@+@#
++@++@#.@.
**##*@*#++
#@@*.+*.*+

După prima mutare programul va scrie la ieșire:

S
.#+#.*.@.@
@.+*@.+*#+
**#++@**#@
#@#@.@@+@#
++@++@#.@.
**##*@*#++
*@@*.+*.*+

Jucătorul J, cel din stînga-jos, începe jocul.

Punctarea

  1. Jocul se termină în una din situațiile:
    1. Nu mai există pătrate pe graniță. Aceasta se traduce prin faptul că toate pătratele fie aparțin unui jucător fie sînt într-un grup contiguu care are toate pătratele pe perimetru adiacente cu pătrate aparținînd unui singur jucător.
    2. Au fost efectuate 150 de mutări (75 de mutări pentru fiecare jucător). În teorie este posibil ca programele să nu avanseze. Dacă ele schimbă culoarea astfel încît să nu absoarbă noi căsuțe ele pot intra într-o buclă infinită. Pentru a preveni această situație vom pune o limită de 150 de semi-mutări, care este absolut suficientă pentru a termina un joc normal.
    Tabla care vă va fi dată la intrare nu conține o poziție finală - în mod sigur veți avea de efectuat o mutare.
  2. Scorul jocului se determină numărînd pătratele absorbite de fiecare jucător, precum și pătratele care pot fi absorbite numai de un jucător, respectiv cele care sînt într-un grup care are ca vecini numai pătrate ale unui jucător. Scorul total al unui jucător este numărul său de căsuțe minus numărul de căsuțe al adversarului.
  3. Exemplu
    J
    ..........
    .@.....*..
    .+@@+..#..
    @@.@+.....
    @@@@@@@@@@
    @@*@@@##@@
    @@@@@@@@@@
  4. Aici jocul s-a terminat fără ca toate culorile să fie absorbite, din cauza limitei de mutări. Scorul total pentru J este numărul de pătrățele absorbite de culoare @, adică 32, plus căsuțele înglobate ce pot fi absorbite numai de el, respectiv o căsuță de culoare *, una de culoare . și două de culoare #. Scorul total al lui J este 36. Observați că există un pătrațel de culoare @ care nu a fost absorbit și nu contează la scorul final. Scorul final al lui S este numărul de pătrățele de culoare ., adică 28, plus căsuțele înglobate ce pot fi absorbite numai de el, respectiv o căsuță de culoare * și una de culoare #. Scorul total al lui J este 30. Sînt patru căsuțe ce nu pot fi absorbite de nici unul din jucători, una de culoare @ si trei de culoare +.
  5. În acest exemplu J cîștigă cu 6 puncte (6 = 36 - 30).
  6. Programul care în timpul unui joc mută greşit sau depăşeşte timpul pierde acel joc, adversarul primind un număr de puncte egal cu aria tablei (ca şi cînd ar fi reuşit să absoarbă toată tabla). În felul acesta dacă programul joacă unele jocuri corect nu va rata concursul ci doar va pierde jocurile în care joacă incorect.
  7. Fiecare meci va consta din două jocuri, fiecare program va avea ocazia să înceapă. Cîștigătorul meciului va fi programul care acumulează mai multe puncte în ambele meciuri. Astfel, dacă A îl bate pe B cu 10 puncte diferență, apoi B îl bate pe A cu 25 de puncte diferență, atunci B va cîștiga meciul. Pentru un meci cîștigat se acordă 3 puncte, pentru un meci remiză 1 punct și pentru un meci pierdut zero puncte.

Programul vostru

  1. Limbajul folosit va fi limbajul C. Atenție! Nu se acceptă extensii C++! Fișierele vor fi denumite cu extensia .c
  2. Fiecare mutare trebuie executată în maxim 0.1 secunde (100 milisecunde) o secundă, pentru a putea desfășura un număr mare de jocuri.
  3. Limita de memorie este de 128MB. Nu aveţi limită de stivă în cadrul acestor 128MB.
  4. Programul vostru trebuie să citească de la intrarea standard și să scrie la ieșirea standard. Aceasta înseamnă să nu folosiți fișiere ci instrucțiunile scanf/printf sau fgetc/fputc cu parametri stdin/stdout în loc de fișiere.
  5. Programul vostru nu poate să citească din, sau să scrie în fișiere. Singura informație disponibilă este cea citită la intrare și anume starea actuală a tablei de joc.
  6. Datele de la intrare sînt corecte. Intrarea nu va conține spații sau alte caractere în afara jucătorului la rînd, a grilei de joc și '\n' la finalul fiecărei linii.
  7. Datele de la intrare se termină cu final de fişier (EOF).

Desfășurarea concursului

Concursul se va desfășura în timpul orelor de cerc de luni 17 iunie 2014, orele 13:30-15:30. Vor fi acordate premii! Pot participa orice elevi de la clasele 6/7/8 de la Tudor Vianu.

Concursul se va desfășura în sistem campionat. Fiecare program va juca un meci cu fiecare alt program. Un meci constă din două jocuri pe aceeași tablă, în care fiecare din programe începe, pe rînd. Suma punctajelor in cele două jocuri determină cine cîștigă. Cîștigul acordă trei puncte, remiza un punct, iar pierderea zero puncte. În final clasamentul programelor se stabilește pe baza numărului de puncte acumulate. Dacă vor fi mai mult de 30 de participanți s-ar putea să schimb puțin regulile de desfășurare din criză de timp.

Trimiterea codului sursă

Momentul limită al acceptării unui program pentru concurs este la începutul cercului din 17 iunie. Cu toate acestea vă încurajez să-mi trimiteți variante intermediare pe email (numai programul C vă rog, nu și proiectul). Voi încerca să vă returnez cum s-a comportat programul vostru contra celorlalte programe trimise. De asemenea vă voi raporta erorile de execuție (depășire de timp, mutare eronată, depășire de memorie). Vă rog să-mi trimiteți sursele ca atașamente, nu direct în mesaj.

Fiecare program C care participă va fi denumit cu o denumire de cod ce va fi folosită în tabelele de rezultate drept identificare. Primele linii ale programului C vor avea următorul antet, drept comentariu, care conține numele programului și datele concurentului:

/*
   Nume program   : noe.c
   Nume concurent : Cristian Francu
   E-mail         : cristian@francu.com
*/

În acest exemplu numele fișierului C este noe.c, iar programul va fi referit în tabelele de rezultate ca noe.

Atenție: Puteți forma echipe de maxim doi oameni, dar premiul se va împărți la doi.

Atenție: Trimiteți-mi cît mai repede un email de confirmare a participării, ca să știu cîte programe vor fi. Emailul trebuie să conțină numele programului, numele și emailurile concurenților din echipă precum și clasa în care se află ei.

Reguli anti-copiere

Pentru a mă asigura că programul este scris de voi îmi voi rezerva dreptul de a vă pune întrebări în legatură cu părţi din codul vostru C. Dacă nu sînteţi în măsură să explicaţi satisfăcător ce calculează propriul vostru program, sau nu aveţi idee ce face o parte din el veţi fi descalificaţi din concurs.

Atenţie: aceasta nu înseamnă că sînt împotriva surselor de inspiraţie. Este chiar foarte lăudabil dacă învăţaţi ceva nou pentru acest concurs, învăţatul fiind în spiritul acestui cerc de informatică. Dar nu este în regulă să copiaţi o metodă sau bucăţi de cod de pe diverse pagini de web, fără să înţelegeţi exact ce face, doar în ideea că funcţionează. Aceasta nu înseamnă că aţi învăţat ceva nou, ci doar că aţi utilizat munca altora. Intenţia acestui concurs şi a acestui cerc este să aveţi o înţelegere profundă a ceea ce programaţi.

Echipe înscrise pînă acum

Următoarele programe sînt înscrise la concurs. Cei nu mi-ați trimis un nume pentru programul vostru vă rog să-mi trimiteți unul. Programul este cel care participă, el trebuie să aibă un nume, chiar dacă este creația voastră.

Program Programatori Clasa
aegir Zaharia Andreea 8
prophet Mucenic Bogdan 8
swamp Hărşan Răzvan 7

Testare

Aţi scris un program şi vreţi să ştiţi dacă funcţionează corect. Cum procedaţi? Puteţi să scrieţi voi un program care să execute programul vostru. Sau puteţi adăuga funcţii programului vostru care să vă permită să jucaţi între diverse variante, pentru a şti care este mai puternică.

Aceasta este cea mai bună soluţie. Totuşi, pentru a vă uşura verificarea, am creat o pagină unde vă puteţi testa programele punîndu-le să joace contra a două programe de antrenament. Programele de antrenament joacă mediu spre slab. Iată pagina:

Rezultate

Felicitări lui Bogdan Mucenic care a cîștigat concursul cu programul prophet. Iată rezultatele complete aici: Clasa VII/VIII lecția 32 - 14 iun 2014