Concurs Pah-tum 2019, 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 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 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 sîmbătă 8 iunie 2019, la ora 12:00. Vor fi acordate premii!

Părinții, familia, prietenii, sînt bine veniți să asiste, dacă doresc.

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. Campionatul se va desfășura pe cinci table ce vor fi dezvăluite la momentul începerii turneului. Î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 sîmbătă 8 iunie ora 9:00AM. 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ă.

Nr. Program Programatori Clasa
1 muteb-hapla Mircea Rebengiuc 5
2 pick-a-cow Remus Rughiniș 6
3 hawkeye Teodor Tatomir 6
4 creed Teodor Togan 6
5 pexy Ana Petcu 6
6 omicroncsi Tudor Grecu 5
7 pah-bum Alex Benescu & Tudor Mușat 6
8 supreme Luca Ilie 6
9 pahtum-pahboom Lucian Badea 6
10 error-404 David Stancu 6
11 marvel Yusuf Fares & Alex Nicu 6
12 bob Armin Asgari & Tudor Voicu 6
13 bog-tum Bogdan Petrescu 6
14 endgame Albert Aizic 6
15 dagwood Rareș Iordache 6
16 ttco Victor Nicola & Mihai Mocanu 6
17 robo-kiwi Andreea Chivu 6
18 procrastinator Elisa Ipate 6
19 destroyers Alex Hossu Vlad Burac 6
20 enigma Ecaterina Ștefănescu 6
21 newt-a5 Ilinca Marcu 6
22 π-soft The Tudors 6
23 play-for-fun Andrei Calotă 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 cîtorva programe de antrenament. Ele joacă mediu spre slab. Iată pagina:

Rugăminte: folosiți această pagină cît de rar puteți. Ea suprasolicită serverul algopedia. Salvați pagina cu rezultate, pentru consultări ulterioare, nu executați din nou programul în pagină.

Rezultate

Felicitări lui Luca Ilie care a cîștigat concursul cu programul supreme. Iată rezultatele complete aici: Clasa a VI-a lecția 39 - 8 iun 2019