Algoritmi, coduri diverse

[Manu]

Da, asa cred ca sunt multi algoritmi, eu vroiam sa gasesc numere intregi pe baza valorii cartilor dintr-o mana.
O sa ma uit asa de curiozitate si la alti algoritmi, desi poate ca un cod Perl mi-ar fi mai greu de inteles, mai ales ca sunt obisnuit cu tipuri statice.

Pana la urma am ajuns la concluzia ca singura metoda eficienta in cazul de fata ar fi prin concatenarea numerelor rezultate in urma efectuarii unui radical pe fiecare, acestea rotunjite la o zecimala, apoi inmultite cu 10. Ar fi astfel toate valorile din doua cifre, iar pentru Full s-ar ajunge la o valoare din 4 cifre..

Un Full este o mana de carti cu trei valori egale si altele doua egale. De exemplu 3 septari si doi nouari dau un ful de septari.

Metoda de care ziceam, cu crearea unui numar din doua cifre pentru fiecare carte ar fi buna chiar si pentru compararea unor maini in care nu sunt nici macar perechi, si unde se ia ca fiind castigatoare cea cu valoarea mai mare. Daca acea valoare cea mai mare ar fi egala, se compara urmatoarea valoare etc.
Creand un numar intreg din toate cele 5 carti, de la mare la mic, din cate doua cifre pentru fiecare, ar iesi un int de 10 cifre. problema este insa ca nu ar fi de ajuns un simplu int de 32 de biti, numarul care reprezinta valoarea relativa a unei maini de 5 carti diferite fiind mai mare de doua miliarde. Ar trebui sa folosesc long-ul sau, ca sa raman in ceea ce am pana acum, int ca valoare finala, sa mai aplic un radical si pe numarul ala, astfel incat functia care calculeaza sa returneze tot un int in urma rotunjirilor.
Asadar, mana cu nimic in ea, cea numita si No-pair ramane cea problematica, aici fiind necesare in total 6 operatii de scoatere a radacinii patrate.

Am citit ca problema delimitarii mainilor de Poker este destul de complexa in general, se cauta tot timpul algoritmi buni, mai ales pentru serverele care au multi jucatori, conteaza acolo cat de rapid si compact se reusesc astfel de comparatii.
Ca sa nu mai citesc cine stie cate coduri, eu am decis sa fac sub o forma sau alta codul meu. Pana la urma, daca nu gasesc alta solutie, cea cu radicalii e ok.
Nu prea stiu matematica, decat pe cea elementara sau pe cea deductibila usor din cea elementara.

[IonPop]

A, da, acum imi aduc aminte ca era o mana cu 3 carti de un fel + altele doua, deci ala e full.
Oricum, nu mai stiu care tip de mana este mai "tare" si asta este important pentru conceperea unui algoritm.

Eu am preferat de asemenea de cateva ori sa creez proprii algoritmi, sa creez propriul sistem de procesat template-uri de exemplu, decat sa pierd timpul si sa studiez algoritmii facuti de altii, doar ca de fiecare data am ajuns ulterior la concluzia ca ar fi fost mai bine sa folosesc acele metode care au fost cu siguranta testate si imbunatatite de mult mai multi si asta fiindca uneori descopeream anumite limitari in modelele mele de care nu mai puteam trece. Probabil ca si altii au dat de acele limitari si au tot studiat si ajuns la algoritmii folositi in prezent chiar daca uneori la prima vedere uneori par a fi mai complicati decat este necesar.
Si absolut intotdeauna mi-am dat seama ca studierea unui algoritm deja existent ar fi luat mult mai putin timp. Atat doar ca pierderea timpului ca sa gandesti propriul algoritm este mult mai placuta decat sa iti bati capul ca sa intelegi cum s-au gandit altii sa rezolve problema.

Apropos de acele module, nu le-am studiat codul asa ca nu stiu cat de clare sunt, insa nu are nicio importanta ca se folosesc variabile netipizate. Probabil oricum toate variabilele importante sunt numere intregi cu care se fac calcule.

Daca ai gasit deja o solutie functionala atunci e OK si nu mai are rost sa cauti alta, fiindca nu cred ca are rost sa faci eforturi in plus pentru o performanta superioara. Daca insa nu va functiona in toate situatiile, cred ca ar fi utila studierea acelui site pe care este prezentat algoritmul pe care probabil il poti adapta mai usor in orice limbaj decat sa studiezi codul sursa Perl.

[Manu]

Pana la urma am rezolvat complet problema compararii a doua maini de poker de acelasi tip.

Scriu si aici metoda mea care poate fi universal valabila, pentru orice tip de mana de carti.
Avand in vedere ca sunt 9 tipuri de maini:
Straight flush, Four of a kind, Full hhouse, Flush, Straight, Three of a kind, Two pair, One pair si No-pair, vor fi intai de toate valori de la 1 la 9, cea mai mare castigand din start. Pentru detectarea tipului de mana nu intru in detalii, fiecare face cum crede mai bine.

Problema era cand mainile sunt de acelasi tip, si trebuie facuta departajarea, de exemplu intr-o mana No-pair se ia cea mai mare carte, apoi daca acestea sunt egale se ia a doua ca valoare si tot asa.

Algoritmul meu pentru o astfel de mana No-pair din 5 carti este:
Cartile sunt sortate descendent. Vor fi valori de la 14 pentru as, pana la 2, cea mai mica valoare posibila.
Trebuie sa ajungem in final la doua numere intregi create din cartile din maini, numere pe care sa le comparam pentru a detecta castigatorul.
Daca pentru valorile cartilor avem numere si dintr-o cifra si din doua, trebuie cumva sa dam o valoare cu un numar egal de cifre pentru fiecare carte, dar care sa reflecte in ordine valoarea la comparatie.
Pentru asta am scos radical din valoarea fiecarei carti, pe acesta l-am inmultit cu 10, apoi am aplicat un floor, ajungand astfel la valori precum:
30 pentru cartea cu valoarea 9 - radical din 9 ori 10 = 30.
Pentru as, valoarea 14, radical este 3.7 ori 10 este 37.
Pentru popa, valoarea 13, radical din 13 este 3,6, ori 10 fiind 36.

Avand toate aceste valori din doua cifre, le-am concatenat, ajungand la un numar din 10 cifre, fapt pentru care spuneam ca e nevoie de un tip long., acesta reprezentand numere intregi pe 64 de biti, deci nefiind probleme cu marimea.

Numere atat de mari sunt necesare doar la carti No-pair si la Flush, unde daca toate sunt de aceeasi culoare se trece tot la departajare prin comparatie pe rand a cartilor.

La un careu e mai simplu, se ia ca prima valoare cea a uneia dintre cele patru carti si a doua valoare cea a cartii ramase singura.
De exemplu pentru un careu de asi cu nouar ar iesi numarul 3730 astfel:
radical din 14 este 3,7xxx, ori 10 este 37,xx, floor de 37,xx este 37. Radical din 9 este 3, ori 10 este 30; concatenand cele doua valori va fi 3730.
Numarul 3730 va fi mai mare decat cel dat de exemplu de un careu de nouari cu as, unde numarul de comparatie ar fi 3037, deci cele doua numere de cate doua cifre fiind inversate.

[Manu]

Revin in acest topic pentru ca am o problema legata de un algoritm.
Acum am cam terminat doua jocuri noi de adaugat in GameZone, doar ca la jocul de carti Scopa nu prea am gasit ceva eficient pentru luarea de pe masa a unei sume de carti.
Practic am sa zicem un array cu numere. Trebuie sa gasesc printr-un algoritm cat de cat eficient toate numerele din array care adunate dau un alt numar.
Sa zicem ca este array-ul de numere intregi:
int[] arr = new arr[] {1, 2, 3, 4, 5};
Am apoi
int N = 5;
Imi trebuie toate combinatiile care dau 5, in cazul de fata acestea fiind 3:
1+4; 2+3; 5.
Poate cei care mai programeaza reusesc sa faca in asa fel incat sa prezinte un algoritm care sa determine toate posibilitatile.

Mi-ar trebui cumva un algoritm care nu utilizeaza ceva functii existente in unele limbaje, ci ceva care sa se bazeze doar pe lucruri standard din orice limbaj: for-uri, array-uri, ArrayList-uri..
Eu in Java am facut ca aceste posibilitati sa fie introduse intr-un ArrayList de ArrayList-uri cu Integers.
Daca nu o sa gasesc ceva rapid si comod, voi merge pe o solutie pas cu pas, in care sa vad daca se indeplineste conditia de la toate la doar doua numere din sir. |Nu e neaparat sa mi se dea si varianta in care suma este realizata dintr-un singur numar, de acel pas programul trece in alt mod dinainte si nu mai ajunge la faza cu suma numerelor.

[IonPop]

Daca ar fi trebuit sa gasesti doua numere care inmultite dau un anumit numar, aproape ca ar fi trebuit sa gasesti un mod de a sparge algoritmul de criptare cu cheie publica.
Nu am avut nevoie de asa ceva, asa ca nu stiu daca exista un algoritm special pentru asa ceva sau eventual vreun modul Perl in care m-as fi putut uita cum procedeaza, insa banuiesc ca la baza trebuie folosita tot o metoda iterativa in care sa aduni numerele. Nu stiu cum e acel joc, insa presupun ca si atunci cand se joaca efectiv cu carti, trebuie facute astfel de calcule, nu cred sa existe in acel caz o varianta rapida prin care jucatorii sa stie care carti adunate dau acel numar dintr-o aruncare de privire. Dar totusi, parca nu as crede ca la acel joc jucatorii trebuie sa stea sa calculeze atat ce carti trebuie sa ia ca sa dea un anumit numar. Daca totusi asa fac insa de fapt pe masa nu sunt de obicei prea multe carti, probabil ca algoritmul va fi destul de rapid fiindca este vorba totusi de niste simple adunari cu numere intregi.

[Manu]

Da, daca sunt putine numere in array, nu dureaza mult, timpul creste insa exponential pe masura ce lungimea array-ului este mai mare.
Pana la urma nu conteaza asta, dar nu am un algoritm clar, unul care sa stie sa mearga cu calculele pe toate combinatiile in sirul de numere indiferent de lungimea acestuia.
Probabil ca voi face astfel incat sa implementez cate un algoritm pentru perechi de numere, pentru cate trei etc. Ar fi fost bun ceva sintetic, dar vad ca in general si altii se confrunta cu aceasta problema si nimeni nu da pe undeva ceva sintetic, ceva general valabil pentru orice sir de numere. Toti vorbesc de optimizari, cum ar trebui sa nu mai fie luat in calcul un numar dupa ce acesta a fost folosit etc.
Mi-a mai venit o idee acum, sa incerc sa fac adunari pe toate combinatiile posibile. Sunt practic doar 256 de posibilitati la 8 numere, adica exact ca posibilitatile valorice ale unui byte. Practic pe orice pozitie a acelui array sa fie considerat ori 1 ori 0, adica sa fie adunat numarul sau nu. Acum sa vad cum creez toate posibilitatile acestea. Pentru un sir fix de 8 as merge de la 1 la 255 si ar trebui sa fac in asa fel incat reprezentarea binara sa fie splituita intr-un array care sa se aplice pe array-ul cu numere astfel incat sa fie adunata sau nu o anume pozitie. La primul pas ar fi 7 de 0 si un 1 in capat, practic ar fi luat in calcul doar al optulea numar. La pasul 255, adica opt de 1, ar fi adunate toate numerele. Daca sirul nu ar fi de opt ci doar de 5 numere, s-ar merge pana la 2 la puterea 5, adica 32 de pasi, de la 0 la 31, unde 31 reprezinta cinci de 1 in binar.
Uite ca scriind aici am gasit solutia de care nu vorbea nimeni niciunde.
Pare prea simpla si ma gandesc sa nu imi scape ceva, trec acum la treaba si vad ce iese.

[Manu]

Pana la urma am rezolvat problema, merg repede lucrurile. Incerc toate combinatiile posibile, rezulta combinatii de carti ale caror suma dau un anumit numar, apoi din acele combinatii corecte se alege cea mai buna dupa alti algoritmi.

[IonPop]

Da, cam asta este idea, sa te folosesti de toate combinatiile posibile. ca in calculul combinatoric. Sti, ala cu permutari, combinatii, aranjamente. Pentru alea sigur exista biblioteci care usureaza munca de a gasi combinatiile, insa spuneai ca vrei sa eviti sa folosesti biblioteci.
Bibliotecile folosesc diverse optimizari de viteza si algoritmi mai eficienti, dar in final adunarea numerelor si compararea rezultatului cu un alt numar va trebui sa o faci tot tu, si probabil ca asta va lua cel mai mult timp de calcul oricum.
Cred ca nu este greu sa iti dai apoi seama de optimizarile care trebuie facute. Astea par mai interesante, de aceea ai gasit probabil mai multe sugestii despre optimizari decat despre algoritm.

[Manu]

Nu am cautat in Java un algoritm clar care sa imi faca toate combinatiile, dar merg pe toate posibilitatile, acestea fiind de 2 la puterea x, unde x e numarul de carti din mana.
Rezulta acel numar de posibilitati, iar for-ul cel mare se duce de la 1 la 2 la puterea x minus 1. In fiecare pas am transformat numarul in valoare binara reprezentata prin string. Pe acel string il fac un array de bytes in cele din urma, o valoare byte fiindu-mi suficienta pentru valorile 0 sau 1.
In fiecare combinatie atunci adun doar numerele de pe pozitiile array-ului unde valoarea este egala cu 1. Se verifica daca suma este egala cu valoarea cartii jucate in cazul Scopa Clasic, ori impreuna cu valoarea cartii din mana este egala cu 15 in cazul variantei Escoba.
In cazul fiecarei sume corecte, adica a fiecarei combinatii acceptate, se adauga obiectele de tip carte in cate un ArrayList. Aceste ArrayList-uri care reprezinta combinatii acceptate se introduc intr-un alt ArrayList, deci am un ArrayList de ArrayList-uri cu obiecte din clasa Card.
In cele din urma, o alta metoda alege cea mai buna combinatie dintre cele posibile, tinand cont de numarul de carti si daca sunt rombi sau septari. Am dat cate un punct pentru ca este o carte oarecare, deci nota initiala a combinatiei va fi egala cu numarul de carti din mana, apoi faptul ca e o carte de romb valoreaza inca doua puncte, un septar inca 3 puncte. Se alege astfel cea mai buna combinatie pe baza notei obtinute.
In acest fel, Pontes Scopa chiar joaca bine, practic stie oricand ce vrea si ma cam bate acum cand algoritmii au fost inclusi in joc.
Se misca totusi repede, dupa cum ai spus si tu, fiind vorba de calcule cu numere intregi si cu string-uri scurte cand e acea transformare in binar. Nu sta niciodata mai mult de o secunda.
Ma ingrijora si faptul ca in heap se creeaza atat de multe obiecte care raman acolo de izbeliste, dar, la memoriile actuale nu e o problema, am verificat si jocul nu trece decat rareori de 20 de mega cu tot cu sunete, faza cu algoritmul contand la nivel de cateva zeci de kilobytes. Intra oricum Garbage Collectorul si rezolva treburile.
Fata de acest tip de algoritm, desenarea cartilor pe ecran consuma mult mai multe resurse, o mana de carti fiind uneori si de unul sau doi mega, acolo se intampla multe procese la lucrul cu redimensionarile bitmap-urilor. Un PNG cu o carte are doar cativa kilobytes in memoria externa.

[IonPop]

Dar cum desenezi cartile? Se genereaza imaginea runtime sau folosesti imagini cu carti gata salvate?

[Manu]

Am un pachet de carti, poze PNG.
Dar ele se tot redimensioneaza in functie de ecran. Porneste de la marimea de baza pe care am facut-o in asa fel incat sa incapa 5 pe ecran. Am creat doua dimensiuni pentru fiecare carte, una pentru ecrane mai mici si una pentru ecrane mai mari, astfel incat Android sa ia cea mai apropiata de marimea care va fi afisata, cica consuma mai putine resurse la redimensionare daca nu e diferenta mare.
Toata povestea asta cu dimensiunile imaginilor, a scrisului e vasta in cazul Android, au o unitate de masura DP, independent pixel, astfel incat daca scriu ca textul are 16 DP, asta va insemna o dimensiune care sa fie proportionala cu marimea ecranului.

[Manu]

Revin în acest topic pentru că m-a rugat cineva să-i fac pentru o temă un algoritm de transformare a numerelor arabe în numbere romane.
Eu am găsit ca fiind cel mai scurt în C++ un cod care mi se pare ok, nu am vrut să scormonesc pe internet, luând-o ca pe un exerciţiu, îl pun la finalul mesajului.
Aş fi curios şi de alţi algoritmi, dacă cineva are întâmplător o altă idee..
Aş fi curios, dacă găseşte IonPop, care ar fi algoritmul din Perl considerat eficient, făcut de cei care tot postează module, să văd cum s-ar mai putea şi altfel. Pe limbalatina.ro în secţiunea Dicţionar Latin - Român unde chiar la începutul conţinutului se afişează data, ziua, luna anul de la întemeierea Romei ("Ab Urbe condita") am o treabă veche, pur şi simplu un array cu toate valorile de la 1 la 99, era suficient că suntem abia în 2769 de la întemeierea Romei, lipeam din acel array doar ce trebuie în plus faţă de MMDCC, adică 2700 - ajunge încă 30 de ani.


Pentru cine nu are chef să citească codul, explic în mare cam cum se întâmplă lucrurile:

Un fel de pseudocod:
Se dă un număr întreg;
Avem un string care va fi în final numărul roman;
Câtă vreme numărul întreg este mai mare sau egal cu 1000:
Adăugăm la string M şi scădem 1000;
Câtă vreme numărul este mai mare sau egal cu 900:
Adăugăm la string CM şi scădem 900;
Câtă vreme numărul este mai mare sau egal cu 500:
Adăugăm la string D şi scădem 500;
Câtă vreme numărul este mai mare sau egal cu 400:
Adăugăm la string CD şi scădem 400;
Câtă vreme numărul este mai mare sau egal cu 100:
Adăugăm la string C şi scădem 100;
Câtă vreme numărul este mai mare sau egal cu 90:
Adăugăm la string XC şi scădem 90;
Câtă vreme numărul este mai mare sau egal cu 50:
Adăugăm la string L şi scădem 50;
Câtă vreme numărul este mai mare sau egal cu 40:
Adăugăm la string XL şi scădem 40;
Câtă vreme numărul este mai mare sau egal cu 10:
Adăugăm la string X şi scădem 10;
Câtă vreme numărul este mai mare sau egal cu 9:
Adăugăm la string IX şi scădem 9;
Câtă vreme numărul este mai mare sau egal cu 5:
Adăugăm la string V şi scădem 5;
Câtă vreme numărul este mai mare sau egal cu 4:
Adăugăm la string IV şi scădem 4;
Câtă vreme numărul este mai mare sau egal cu 1:
Adăugăm la string I şi scădem 1;

Eu am pus valorile string şi cele întregi în două array-uri paralele, astfel încât să merg prin tot şirul de 13 valori cu un for făcând while-urile.


Mai jos e codul meu în C++, contează doar funcţia intToRoman() care este sub main-ul în care doar am testat. La final mai este şi fişierul .exe compilat:

Cod: Selectaţi tot

#include <iostream>
using namespace std;

string intToRoman(int n);
	
int main() {
	cout << "Write an integer: " << endl;
	int myInteger;
		cin >> myInteger;
		string roman = intToRoman(myInteger);
		cout << "" << myInteger << " converted is " << roman << endl;
		system("pause");
	return 0;
} // end main.

string intToRoman(int n) {
string ret = "";
		string arrRoman[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
		int arrArab[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
int arrsLength = sizeof(arrArab) / sizeof(int);
	for(int i=0; i<arrsLength; i++) {
while(n >= arrArab[i]) {
n -= arrArab[i];
ret += arrRoman[i];
}
}
return ret;
}

IntegerToRoman.exe

[IonPop]

Am gasit cateva module care transforma numerele romane in numere arabe si invers. In paginile de mai jos gasesti descrierea si sintaxa lor, dar si un link cu care poti descarca o arhiva .tar.gz cu codul modulului (care probabil se afla in directorul lib):

http://search.cpan.org/~chorny/Roman-1.24/lib/Roman.pm

http://search.cpan.org/~tels/Math-Roman ... h/Roman.pm

http://search.cpan.org/~syp/Text-Roman- ... t/Roman.pm

http://search.cpan.org/~dyacob/Convert- ... r/Roman.pm

http://search.cpan.org/~santos/Number-C ... t/Roman.pm