Verna Dorian-Alexandru Grupa 314CC Tema am ales sa o fac destul de modularizata. Am mai multe fisiere, cerinta1.c, cerinta2.c, cerinta3.c si bonus.c fiind fisierele sursa care contin implementarile fiecarui task in parte. Fisierele cerinta1.h, cerinta2.h, cerinta3.h, bonus.h contin semnaturile functiilor cerinta1(), cerinta2(), cerinta3() si bonus(). Fisierul sursa main.c contine functia main care este apelata prima, si care, in functie de parametrii dati, apeleaza una din functiile anterioare. fisierul file.h contine declararea structurii de arbore folosit Am optat pentru o scriere modularizata, deoarece pana acum nu am prea facut asta la teme si m-am gandit ca ar fi cazul sa incep sa scriu cod mai frumos si ordonat. Cu toate acestea, mi-am dat seama pe masura ce faceam tema ca modul in care am ales sa modularizez tema nu este prea bun, deoarece am multe functii ce au nume diferite dar fac acelasi lucru. Era bine sa fac un fisier .h care sa contina toate aceste functii (precum afisare_arbore sau generare_arbore) si pe care sa il includ in fiecare fisier .c mentionat de mine anterior, dar nu am mai apucat. Ideea de implementare a arborelui este similara celei care este denumita left-child, right-sibling. Ideea algoritmului meu consta in faptul ca un nod este legat doar de un copil al sau, copilul fiind cap de lista intr-o lista care contine toti ceilalti copii ai nodului. Asta a fost ideea mea initiala pe care ma apucasem sa o implementez, apoi am vazut pe forum o intrebare la care a fost mentionat tipul de implementare cu left si right si am descoperit analogia dintre ele in acest mod. Task 1 Aici mi s-a parut mai usor sa codific tabla de joc sub forma unei matrice de int-uri. Am facut acest lucru deoarece m-am gandit ca ar fi mai econom decat sa fac o matrice de char-uri, ar fi mai usor sa dictez jucatorul al carui rand este atunci cand apelez recursiv (unul este 1, iar celalalt este -1, deci doar pun un minus), si, pe de alta parte, imi e mie mai usor sa lucrez cu o matrice de numere (este mai intuitiv). 1 reprezinta B, -1 reprezinta R, iar 0 reprezinta -. La task-ul 1 am 11 functii: 1) init_root - Functie care imi initializeaza radacina arborelui, in functie de inputul dat din fisier 2) afisare_nod - Functie care, odata apelata, imi afiseaza un nod dat. Decodifica matricea si afiseaza cu char in loc de numere. 3) verificare_frunza - Functie care verifica daca un nod din arbore este un nod terminal (o frunza) - fie o stare in care nu se mai poate face nicio mutare, fie o stare in care un jucator a castigat. Functia reurneaza 1 daca este frunza si 0 daca nu 4) init_nod - Functie care initializeaza un nod oarecare de arbore. Este o functie ajutatoare pe care o apelez atunci cand generez recursiv arborele 5) generare_nod - Functie care imi genereaza nodul. aceasta functie returneaza un pointer la nodul generat, sau NULL daca nu se poate generea nod. 6) inserare_nod - Functie care imi insereaza nodul in lista, iar, in cazul in care vorbim de primul copil al parintelui, il legam pe parinte de el si pe nod il facem cap de lista. 7) generare_arbore - Functia de generare arbore care imi genereaza recursiv arborele 8) afisare_arbore - Functia care imi afiseaza recursiv arborele (in fisier). Aceasta functie apeleaza si functia afisare_nod. Se scrie arborele in fisier la apelul acesteia. 9) eliberare_nod - Functie ajutatoare, acesta elibereaza memoria unui nod 10) eliberare_memorie - Functie recursiva care are rolul de a elibera la sfarsit memoria alocata elementelor arborelui. Aceasta functie apeleaza de mai multe ori functia eliberare_nod 11) cerinta1 -Functie care este apelata in functia main din main.c Aceasta contine declaratii de variabile si apelurile functilor date anterior. Task 2 Functia cerinta2() se ocupa de rezolvarea task-ului 2. Aceasta, precum si functiile ajutatoare necesare se regasesc in fisierul sursa cerinta2.c Am considerat ca ar fi bine sa completez structura de la task-ul anterior cu inca o valoare int si anume value_min, aceasta reprezentand valoarea dintr-un nod in contextul algoritmului minimax. In rezolvarea cerintei am folosit 9 functii: 1) init_node2 - Aceasta functie imi initializeaza un nod oarecare. Functia este pe acelasi model cu cea de la cerinta 1. De notat este fapul ca initializez value_min cu un numar pe care l-am considerat putin probabil sa il intalnesc in fisierele de intrate: -100000. 2) inserare_noduri - Aceasta este o functie ajutatoare pentru functia de generare noduri. O folosesc pentru a insera un anumit numar nr (dat ca parametru) de fii unui nod de arbore root, dat si el ca parametru. 3) afisare_arbore_min - Functie de scriere in fisier a arborelui rezultat. Aceasta functie este similara celei de la primul task. 4) seek_aux - functie ajutatoare pentru cea de generare arbore. Aceasta functie imi returneaza un pointer la un element al arborelui. Acest element il actualizez la trecerea pe un alt nivel al arborelui atunci cand citesc valorile nodurilor sau numarul de fii al acestora. Basically, functia returneaza un pointer catre primul element de pe nivelul dat ca parametru din arbore, care sa nu fie frunza. Elementul va constitui valoarea initiala pe care o va lua iteratorul it in functia generare_arbore2. 5) generare_arbore2 - Aceasta este functia care imi genereaza arborele. Prima oara ma ocup de cazul in care trebuie sa introduc in arbore fiii radacinii, apoi, pe un else, ma ocup de restul nivelelor arborelui. Aici citesc pe rand un numar nr de valori, care reprezinta numarul de valori de pe linia din fisier corespunzatoare acelui nivel. Numarul nr il actualizez de fiecare data cand termin de citit o linie. Iteratorul it porneste de la valoarea aux descrisa la functia anterioara si, pe baza mai multor conditii, determina pozitia viitorului element pe care il voi citi in arbore. Am ales sa fac aceasta functie nerecursiv. Nu stiu daca se putea face recursiv. Pe moment chiar nu am stiut cum sa o fac si in cap imi venea doar ideea aceasta de implementare. Am incercat sa economisesc memorie si sa nu salvez dintr-o data o linie intr-un buffer, ci sa citesc pe rand fiecare valoare din fisier, lucru care s-a dovedit totusi foarte greu. Mi-a luat foarte mult sa gasesc toate cazurile pentru care a trebuit sa pun conditii. Functia poate fi greu de citit, dar pana la urma am reusit sa gasesc toate conditiile necesare. Am folosit chiar niste functii precum fseek, ftell si instructiunea goto. Fseek si ftell le-am folosit la un moment dat pentru a determina oprirea executiei functiei atunci cand se ajunge la sfarsitul fisierului, deoarece am suspectat ca unele erori pe care le aveam la valgrind veneau de la urmatoarele miscari pe care le faceam in functie, dar care erau redundante, fiind sfarsitul fisierului. Comanda goto am folosit-o deoarece multe conditii trebuiau repetate, iar eu am considerat in acel moment mai ok si mai intuitiv sa folosesc goto. 6) umple_arbore - functie recursiva care se ocupa de implementarea propriu-zisa a algoritmului minimax, punand in nodurile superioare ale arborelui elementele necesare, respectand regula Mini - Max. Functia aceasta a fost mul mai usor de implementat decat cea de generare arbore. 7) eliberare_nod_min - Functie de eliberare a memoriei unui nod - similara functiei de la cerinta 1 8) eliberare_memorie_min - Functie recursiva de eliberare a memoriei arborelui. Functie similara cu cea de la cerinta 1. 9) cerinta2 - Functie care contine apelurile functiilor anterioare si declarari de variabile. Task 3 Pentru acest task am introdus inca doua valori in structura de la cerintele anterioare, structura pe care o am implementata in tree.h. Am introdus, asadar, pe alpha si beta, doua int-uri. Cerinta contine 10 functii, noua dintre ele fiind identice sau aproape identice cu cele de la cerinta 2 si anume (le-am pus si nume sugestive): 1) init_node_task3 2) inserare_noduri_task3 3) seek_aux_task3 4) generare_arbore_task3 5) afisare_arbore_task3 6) eliberare_nod_task3 7) eliberare_memorie_task3 8) umple_arbore_task3 9) cerinta3 Functia cerinta3 difera putin prin diferitele apeluri de functie. A 10-a functie, alpha_beta_pruning este cea care face diferenta intre ce am implementat in cerinta2.c si ce am implementat in cerinta3.c. Aceasta este o functie recursiva care parcuge fiecare nod. Fiecare nod are doua valori alpha si beta pe care i le-am atribuit si care se modifica pe parcursul executiei programului, in functie de nivelul pe care ma aflu si de valorile alpha si beta ale copiilor si parintilor unde este cazul. Asa cum spune si algoritmul, ele determina si daca prezenta unui subarbore este reduntanta sau nu. Mi-a luat putin sa inteleg algoritmul, motiv pentru care primele 3 teste care au fost trimise de voi le-am facut prima oara pe hartie ca sa imi dau seama cum functioneaza. Task 4 Bonus Pentru bonus am folosit o noua structura de arbore (tree_node_para), aceasta continand pointerii next, prev, parent si child si un vector de valori int value (dat ca pointer deoarece acesta contine nr_players + 1 elemente, deci il aloc dinamic in functie de cati jucatori am). Vectorii sunt initializati cu calloc, iar daca un anume nod din arbore este frunza, atunci primul element al acestuia devine din 0 1. Asa am ales sa diferentiez frunzele de nodurile din interior. Functiile seamana ca idee cu cele de la task-urile 2 si 3, dar sunt adaptate pentru lucrul cu un vector de int pentru un nod si nu cu o valoare int pentru un nod In fisierul bonus.c am implementate 10 functii: 1) init_node_bonus - functie care contine initializarea unui nod de tipul tree_node_para (alocare nod si alocare vector cu nr_players + 1). De notat este ca vectorul este initializat cu zerouri. 2) inserare_noduri_bonus - Functie de inserare a unui numar de fii unui nod din arbore. Aceasta functie este apelata de functia de generare arbore. Ea similara cu functiile folosite anterior. 3) seek_aux_bonus - Functie asemanatoare cu cele de la task-urile anterioare, ajutatoare pentru generarea arborilor. Adaptata la problema de fata. 4) generare_arbore_bonus_helper - spre deosebire de task-ul 2 si 3, aici am spart functia de generare arbore in doua, una care sa se ocupe de generarea propriu-zisa si o alta care sa imi calculeze iteratorul it printre noduri pentru fiecare pas. Functia helper este cea care imi calculeaza acest iterator. Practic este o parte din codul de la functiile de generare de dinainte, numai ca introdusa in alta functie. 5) generare_arbore_bonus - functia propriu-zisa de generare a arborelui. Si in acest caz am citit fiecare element pe rand din fisier (triplet cand a fost cazul). Apoi am folosit strtok pentru elementele de tip frunza, pentru a introduce valorile necesare in vectorul value continut in nodul respectiv. In rest, functia seamana cu cele de la task-urile anterioare ca idee. 6) afisare_arbore_bonus - Functia de scriere a arborelui in fisier. 7) eliberare_nod_bonus - Functie de eliberare memorie a unui nod de arbore 8) eliberare_memorie_bonus - functie care se ocupa de eliberarea memoriei arborelui la sfarsit. Functie recursiva care apeleaza functia precedenta. 9) umple_arbore_bonus - Functia care umple arborele cu valorile cerute la bonus. Functia merge pe aceeasi idee ca cea de la minimax, doar ca de data, aceasta nu mai returneaza o simpla valoare int, ci un pointer la adresa unui vector de int-uri. Pentru comparare insa, nu folosesc acest vector, ci prima valoare a acestuia. Deoarece functia nu imi mai mergea atunci cand reveneam pe nivelurile superioare ale arborelui (trebuia sa retin in alt vector minimul sau maximul avut pana atunci pe ramura aceea de nivel). Astfel, vectorul copie este aux, pe acesta il folosesc in comparatiile pe care le fac. 10) bonus - functia care este apelata in main.c. Este functia care contine apelurile de pana acum. Aspecte suplimentare: - Am folosit la task-ul 2, 3 si bonus functiile fseek, ftell si rewind. Am facut aceasta deoarece primeam in generare_arbore o eroare si am considerat ca poate fi din aceasta cauza. Eroarea am considerat ca este atunci cand incerc sa caut un nou it atunci cand am ajuns la finalul fisierului, neavand unde sa mai pun o eventuala valoare noua. Deci, verific daca este finalul fisierului si ies din functie daca conditia este verificata. De asemenea, consider ca reprezinta si o mica eficientizare a codului, posibil neimportanta. - Legat de coding style, am intrebat si pe forum, mi s-a spus ca se va folosi un checker similar cu cel de la tema1. Eu am verificat cu acel checker si nu am nicio eroare. Sper sa fie ok, am pus si comentarii in cod acolo unde am considerat necesar. Am intrebat deoarece nu eram sigur asupra unei functii unde am multe conditii si am indentat mult, iar checker-ul imi dadea eroare pentru ca aveam prea multe niveluri de indentare, desi acestea erau corecte, asa ca am sters unele tab-uri, indentarea parandu-mi putin dubioasa mie, dar macar checker-ul nu mai dadea eroare. - Ca timp tema mi-a luat aproape o saptamana cu cateva ore de lucru in fiecare zi (3 - 4). - Cel mai greu task a fost task-ul 2 pentru ca acolo trebuia sa gasesc o modalitate sa citesc din fisier si sa fac arborele in acelasi timp. Pana la urma am gasit doar o modalitate iterativa. Toate celelalte task-uri de pe urma nu au mai fost asa de grele. - A fost o tema ok, la inceput nu am fost multumit pentru ca nu aveam checker si nici nu aveam toate testele trimise si era putin stresant, dar cred ca oricum am ramas cu un plus, deoarece am invatat pana la urma sa rezolv problemele chiar si in lipsa unor resurse pe care le consideram foarte importante. In rest a fost ok si mie mi-a placut. Multumesc si well done pt ideea temei Verna Dorian-Alexandru 314CC