Concurs Pah-tum 2014, clasa a 6-a

From Algopedia
Jump to navigationJump to search

Concurs: jocul Pah-tum

Scrieți un program care să joace jocul Pah-tum. 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 Pah-tum se joacă pe o tablă de 7x7 pătrate. Ca și ruda sa îndepărtată X și 0, jucătorii alternează în încercarea de a forma linii care acordă puncte. Table de Pah-tum au fost descoperite în Mesopotamia și Asiria, iar o tablă făcută din fildeș a fost descoperită în mormîntul lui Reny-Seneb, dinastia XII, și datat la aproximativ anul 1800 î.Hr.

Ce se cere, pe scurt

Dată o tablă de 7x7, trebuie să plasați piesa voastră (un X sau un O). Există cîteva pătrățele nedisponibile pe tablă. Voi și oponentul vostru jucați pe rînd, plasînd cîte o piesă, pînă ce toate pătratele disponibile se umplu. La final voi acorda scorul cuvenit fiecărui jucător și voi decide cine a învins examinînd lungimea liniilor orizontale și verticale.

Programul vostru va citi o tablă 7x7 de la intrarea standard (citire cu fgetc(stdin)) reprezentînd o configurație a tablei de Pah-tum, apoi va executa o mutare prin plasarea unei piese X sau O în unul din pătratele disponibile și, în final, va scrie la ieșirea standard (scriere cu fputc(c, stdout)) o altă tablă 7x7, 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ă 5 pătrățele nedisponibile pe tablă:

-------  rîndul A
------+  rîndul B
---+---  rîndul C
-------  rîndul D
--++---  rîndul E
-------  rîndul F
+------  rîndul G

Sînt șapte coloane pe fiecare rînd, în total 49 de pătrățele pe tabla de joc. Un pătrat cu un "-" în el este gol, unul cu un "+" în el nu poate fi folosit. În exemplul de mai sus 5 pătrățele sînt nedisponibile iar 44 sînt disponibile.

  1. Tabla de joc va fi întotdeauna de 7x7.
  2. Întotdeauna vor fi un număr impar de semne "+" pe tablă, lăsînd astfel un număr par de pătrățele de joc, marcate cu "-". Vor fi între 1 și 25 de pătrățele marcate cu "+".
  3. Semnele "+" pot apărea oriunde pe suprafața de joc.
  4. Odată început jocul orice pătrat marcat cu "-" poate fi înlocuit cu un "X" sau un "O" (litere mari).
  5. Datele de intrare și cele de ieșire nu vor conține spații sau alte caractere în afara grilei de 7x7 și caracterul sfîrșit de linie ("\n") la finalul fiecărei linii, formînd în total 56 de caractere.

Tabla unui joc în desfășurare

XO-OXX-  rîndul A
------+  rîndul B
---+-O-  rîndul C
O------  rîndul D
--++---  rîndul E
--XXXX-  rîndul F
+X-OOOO  rîndul G

Această tablă arată o mostră de joc după ce fiecare program a făcut opt mutări (sînt 8 X și 8 O pe tablă). Mai există 28 de mutări rămase din care putem alege următoarea mutare.

  1. Mutările (plasarea unui "X" sau unui "O") se vor face prin înlocuirea oricărei poziții "-" cu litera voastră.
  2. Întotdeauna va exista cel puțin o poziție "-" rămasă pe tabla de la intrare, așa încît întotdeauna va fi posibilă executarea unei mutări.

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

  1. Programul va muta fie cu "X" fie cu "O" pe parcursul unui joc.
  2. "X" începe. Dacă primiți la intrare o tablă fără nici un "X" sau "O" pe ea înseamnă că jucați cu "X" și începeți jocul punînd un "X" pe tablă.
  3. Dacă există deja niște "X" și "O" pe tablă va trebui să numărați cîți "X" și cîți "O" sînt, pentru a determina cu ce literă jucați. Dacă numărul de "X" este egal cu cel de "O" înseamnă că jucați cu "X", altfel înseamnă că avem un "X" în plus pe tablă și deci sînteți la mutare cu "O".

Punctarea

  1. După ce toate mutările au fost epuizate (nu mai există "-" pe tablă), poziția finală va fi punctată. Întotdeauna vor fi un număr egal de "X" și "O" la final.
  2. Scorurile se determină examinînd șirurile orizontale și verticale de X și O. Șirurile diagonale sau cele care se întorc circular peste limita tablei nu vor fi considerate.
  3. Pentru fiecare linie orizontală sau verticală formată din aceeași literă se va acorda un scor conform cu tabelul de mai jos:
    Litere consecutive identice 3 4 5 6 7
    Scor 3 10 25 56 119
  4. Șirurile de lungime 1 sau 2 nu vor conta la punctare. Observați că aceste punctaje includ punctajele oricăror subșiruri incluse: scor(n) = 2 * scor(n-1) + n.
  5. Exemplu (O-urile au fost eliminate în acest exemplu):
    XXXXXXX  rîndul A     Rîndul A se punctează cu 119 pentru 7 la rînd.
    XX-XXX+  rîndul B     Rîndul B se punctează cu 3 pentru un șir de 3.
    X-X+XX-  rîndul C     Rîndurile C/D/E au scor 0.
    ----X--  rîndul D     Rîndul F se punctează cu 10 pentru un șir de 4.
    --++X--  rîndul E     Coloana 1 se punctează cu 3 pentru un șir de 3
    ---XXXX  rîndul F     Coloana 5 se punctează cu 56 pentru un șir de 6
    +------  rîndul G     Coloana 6 se punctează cu 3 pentru un șir de 3
  6. Scorul total pentru X este, astfel 119+3+10+3+56+3=194. În mod similar, punctajul lui "O" atunci cînd toate caracterele "-" sînt înlocuite cu "O" în tabla anterioară, este 10+3+56+3+25+3=100. În acest exemplu X cîștigă cu 94 de puncte (94 = 194 - 100).
  7. Programul care în timpul unui joc mută greşit sau depăşeşte timpul pierde acel joc, adversarul primind 1666 puncte (echivalentul unei table pline cu aceeaşi piesă). În felul acesta dacă programul joacă unele jocuri corect nu va rata concursul ci doar va pierde jocurile în care joacă incorect.
  8. 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.
  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 grilei de 7x7 și "\n" la finalul fiecărei linii.

Desfășurarea concursului

Concursul se va desfășura în timpul orelor de cerc de luni 16 iunie 2014, orele 13:30-15:30. Vor fi acordate premii! Pot participa orice elevi de la clasele a 5a și a 6a 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 16 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.

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   : alpah-betum.c
   Nume concurent : Cristian Francu
   E-mail         : cristian@francu.com
*/

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

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
alphaAIM Magan Alexandru Iulian 6
brainiac Nițu Ștefan, Mohanu Herbert 6
FTL2 Păcurar Alexandru, Ulmeanu Vlad 6
gamebomb Sachelarie David 6
its-working Trițescu Marcu, Iorgoveanu Christian 6
Mario_Forever Căutiș Rareș 6
NoName Timofte Alexandra, Florescu Cella 6
Pah-RS Priboi Radu 6
Pahy-Tumy Rusu Rareș 6
Slow-and-Furious Coman Andrei, Popovici Robert 6
unknown Icleanu Ruxandra 6
void-votum Diaconu Andrei-Calin, Manea Ioana 6

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 Andrei Coman și Robert Popovici care au cîștigat concursul cu programul Slow and Furious. Iată rezultatele complete aici: Clasa a VI-a lecția 41 - 15 iun 2014