Clasa VI/VII/VIII lecția 38 - 11 iun 2013

Lecție - toate clasele

Concurs: jocul Pah-tum

Scrieți un program care să joace jocul Pah-tum, descris mai jos. 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".

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 de urgență. Programul este cel care participă, el trebuie să aibă un nume, chiar dacă este creația voastră.

Program	Programatori
ahputatatam	Tudor Niculescu
beat-em-all	Alex Cioltan
minGW	Victor Ionescu, Anastasia Zloteanu
pet-al-doom	Alexandru Petrescu
pahtum101	Bogdan Mucenic
pahtum-az	Andreea Zaharia
worst-player	Răzvan Hărșan

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 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. 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). Adică extrem de repede, 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 marți 18 iunie 2013, orele 13:30-15:30. Vor fi acordate premii! Pot participa orice elevi de la clasele a 5-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. Î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 18 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.c.

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 și emailurile concurenților din echipă.

Temă

Participați la concurs. Accept rezolvări pe email de la orice elev de clasele 5-8 la liceul Tudor Vianu.