Modele de algoritmi in #Excel – Counting Elements (4)

Acest articol continuă seria de articole cu propuneri de rezolvare a algoritmilor clasici din informatică în Excel. În continuare voi explica și rezolva probleme specifice de la adresa: https://app.codility.com/programmers/lessons/4-counting_elements/

Algoritmii de pe Codility și poate de pe multe alte site-uri sunt adresați în special limbajelor de programare, Excelul nefiind un instrument dedicat rezolvării acestor tipuri de probleme, dar în versiunile de cloud Microsoft Excel 365 conține suficiente funcții care îmbinate pot rezolva probleme destul de complexe. În această serie de articole vreau și eu să văd până unde se poate ajunge.

Puțină teorie

În Excel sunt implementate foarte multe funcții de căutare, de la cele mai simple la combinații care permit abordarea vectorilor (celule de date) în diferite formate.

În primul rând pentru a răspund multor probleme de informatică trebuie să descompunem un șir de elemente în componentele sale, de cele mai multe ori pe baza unui delimitator.

În imagine câteva exemple de funcții de căutare și sortare uzuale în Excel 365:

Vă reamintesc că pentru apelarea dinamică a unui vector vom utiliza formatul Celula# în toate funcțiile din exemplu fiind referit vectorul A5# care presupune oricâte linii o fi având acesta, nefiind cunoscută din stard dimensiunea șirului de valori din A2.

Un aspect de noutate teoretică în abordarea acestui articol este generarea de tabele de date (matrici) cu ajutorul funcției MAKEARRAY():

în care avem parametrul 1 numărul de linii care să se genereze, parametrul 2, numărul de coloane și funcția LAMBDA aplicabilă, în care parametrul r este echivalent liniei curente din matrice iar c este echivalentul coloanei curente.

În acest articol referim algoritmul clasic Counting Elements care este o tehnică utilizată în informatică și în special în algoritmică pentru sortare și căutare. Acesta este utilizat pentru a număra numărul de apariții ale fiecărui element dintr-o colecție de date și pentru a efectua diverse operații pe baza acestor numărători. În primă lectură putem crede că ar fi vorba de un COUNTIF() pe un vector de valori pe baza unor valori unice.

În articolul Modele de algoritmi in #Excel – Vectori (2.2) am descris în ultimul update cum determinăm printr-o funcție numărul de apariții a fiecărui element.

Algoritmul Counting Elements este adesea utilizat ca parte a altor algoritmi mai complecși sau în combinație cu alte tehnici de algoritmă pentru a rezolva diverse probleme.

Să trecem la probleme!

Problema FrogRiverOne

Recunosc că până acum mi-a fost cel mai greu de înțeles ce ar dori să calculeze acest algoritm.

FrogRiverOne este o problemă clasică de algoritmă și este parte a algoritmului Counting Elements. Această problemă implică o broască care dorește să traverseze un râu folosind frunze care plutesc pe suprafața apei. Scopul nostru este să determinăm cea mai mică poziție pe malul râului (secunda) de unde broasca poate sări astfel încât să ajungă dincolo de râu într-un timp minim.

Mai specific, avem un râu cu o lățime dată (X) și un șir de numere (A) care reprezintă pozițiile frunzelor care plutesc pe suprafața râului. Fiecare număr din șir reprezintă o poziție pe malul râului, corespondent cu secunda / timpul necesar până când frunza ajunge la acea poziție. Broasca poate sări doar atunci când există cel puțin o frunză pe fiecare poziție a râului, de la 1 la X, unde X este lățimea râului.

De exemplu, având un râu de lățime 5 și șirul [1, 3, 1, 4, 2, 3, 5, 4], broasca poate traversa râul atunci când există frunze pe pozițiile 1, 2, 3, 4 și 5. Astfel, cel mai mic număr de pași necesari pentru ca broasca să traverseze râul este 5, iar aceasta poate sări de pe poziția 6 locul în care apare pentru prima dată valoarea 5, celelalte valori de la 1 la 5 fiind deja întâlnite până la acea secvență.

Pentru a realiza acest lucru, putem folosi un tabel de frecvență pentru a număra câte frunze avem pe fiecare poziție a râului. Apoi, parcurgem șirul de frunze și verificăm când toate pozițiile de pe malul râului sunt acoperite. Odată ce aceasta se întâmplă, găsim cea mai mică poziție de pe malul râului și returnăm acest rezultat.

Rezultate intermediare:

Propunere de rezolvare FrogRiverOne cu MAKEARRAY în Excel.

în C6: =SEQUENCE(;B1) am generat secvența de pași (1, X) care reprezintă lățimea râului.

în B7: =TRANSPOSE(B3#) am returnat șirul de numere (frunzele) în ordinea lor de apariție.

în C7 am realizat un tabel în care verific fiecare valoare din B7# și poziția sa în zona C6#. Fiecare linie din tabel reprezintă o secundă în acest algoritm.

Funcția pentru generare dinamică tabel:

=MAKEARRAY(COLUMNS($B$3#);$B$1;
     LAMBDA(r;c;
		LET(valc; INDEX($C$6#;;c);
		    valr; INDEX($B$7#;r);
			IF(valr=valc;1;0))))

în care folosesc funcția INDEX() pentru a aduce valoarea de pe linie și de pe coloană pentru a le compara ulterior. Dacă cele două valori X și frunza sunt egale atunci returnez 1, dacă nu 0.
În imagine un exemplu vizual:

Pasul următor este să determin numărul de apariții pe fiecare coloană în așa fel încât odată apărută valoarea 1 pe linia 1 să fie vizibilă și pe linia 2, ar dacă apare de două ori să se adune.

Practic pentru am mers pe abordarea de a folosi funcția BYCOL() cu SCAN() doar că cele două funcții nu se pot utiliza împreună în cadrul unui LET() cu alte valori dinamice. Și de aici au pornit exporările pentru a găsi o soluție. Salvarea a venit din articolul: Unable to use BYCOL and SCAN in the same formula

Așadar pentru a calcula pe coloană numărul de apariții a fiecărei valori, am folosit în M7: funcția:

=LET(n; ROWS(C7#);
     m; COLUMNS(C7#);
     rows; MAKEARRAY(n; m; LAMBDA(r;c; r));
     cols; MAKEARRAY(n; m; LAMBDA(r;c; c));
     MAP(rows; cols;
         LAMBDA(r;c;
            SUM(INDEX(C7#; 1; c):INDEX(C7#; r; c)) ))
   )

în care: n este numărul de linii ale tabelului inițial și m, numărul de coloane. După care realizez două tabele independente unul cu liniile și altul cu coloanele în așa fel încât să le pot parcurge cu MAP(). În partea de calcul fac o sumă pe două rezultate din INDEX() până la celălalt INDEX().

Din păcare versiunea aceasta este prea abstractă pentru a fi integrată mai tarziu într-o funcție finală, așa că am folosit mai jos versiunea un pic mai complexă.

Ca să pot determina linia (secunda) în care sunt acoperite toate pozițiile râului (X-urile), am folosit în V7 funcția: =BYROW(M7#;LAMBDA(r;IF(COUNTIF(r;0)=0;”x”;0))) în care identific linie cu linie dacă numărul de 0-uri (poziții neacoperite) este egal cu 0. Atunci marchez cu „x”. Poziția lui x pe această coloană rezultat este de fapt numărul secundei în care broasca poate traversa râul. În W7 determin secunda: =LET(poz; IFNA(MATCH(„x”;V7#;0);-1); IF(poz=-1;-1;poz-1)) în care MATCH() caută primul x în rezultatul din V7 apoi dacă nu se găsește nici un X înseamnă că problema este fără soluție de aceea trebuie să returneze, conform algoritmului, valoarea -1.

Alternativa la funcția din M7 este:

=LET(set; C7#; 
	m; COLUMNS(set); 
	seq; SEQUENCE(m;1);
	CUMULATE; LAMBDA(x; SCAN(0; x; LAMBDA(acc;item; acc+item)));
	DROP(REDUCE(0;seq; LAMBDA(acc;idx; HSTACK(acc; CUMULATE(INDEX(set;;idx)))));;1)
)

Având în vedere că funcția nu-mi aparține am lăsat întocmai numele variabilelor. În această funcție determinăm setul de valori ca rezultat din C7# după care calculăm în m numărul de coloane apoi generăm o secvență seq cu numărul de coloane m. Cheia este în variabila CUMULATE care declară un fel de funcție recursivă de scanare, utilizată în DROP-ul cu REDUCE din partea finală a LET-ului.

În mod cumulat funcția finală de rezolvare a problemei este:

=LET(Xs; SEQUENCE(;B1);
sir; TRANSPOSE(--TEXTSPLIT(B2;","));
tabi; MAKEARRAY(ROWS(sir);$B$1;LAMBDA(r;c;LET(valc; INDEX(Xs;;c);valr; INDEX(sir;r);IF(valr=valc;1;0))));
tabfin; LET(set; tabi;
m; COLUMNS(set);
seq; SEQUENCE(m;1);
CUMULATE; LAMBDA(x; SCAN(0; x; LAMBDA(acc;item; acc+item)));
DROP(REDUCE(0;seq; LAMBDA(acc;idx; HSTACK(acc; CUMULATE(INDEX(set;;idx)))));;1)
);
verif; BYROW(tabfin; LAMBDA(r; COUNT(FILTER(r;r=0))));
rezfin; LET(poz; IFNA(MATCH(0;verif;0);-1); IF(poz=-1;-1;poz-1));
rezfin)

în care:

Xs este lățimea râului din B1;
sir este A-ul, lista de valori / poziții în care cad frunzele în fiecare secundă;
tabi este primul tabel de tip matrice în care avem fiecare frunză cu poziția ei, echivalentul tabelului din C7#;
tabfin este matricea de calcul cumulativă a aparițiilor frunzelor la fiecare salt, echivalentul tabelului din M7;
verif este variabila care calculează numărul de apariții ale lui 0 pentru fiecare linie din tabfin;
rezfin este valoarea cea mai mică a secundei in care broasca poate traversa râul. Rezfin întoarce valoarea -1 în cazul în care nu sunt frunze pentru toate pozițiile în șirul specificat.

Problema PermCheck

Avem la dispoziție un șir A format din N numere întregi. Scopul este să determinăm dacă acest șir reprezintă o permutare validă a numerelor de la 1 la N.

O permutare validă înseamnă că șirul conține exact o dată fiecare număr întreg de la 1 la N, fără a exista duplicări și fără a lipsi vreun număr. În plus, ordinea numerelor în șir nu contează, astfel că o permutare validă poate avea numerele în orice ordine.

Pentru a rezolva această problemă, putem folosi o abordare simplă și eficientă. Vom construi un set care să conțină numerele de la 1 la N și vom parcurge șirul A, verificând dacă fiecare număr întreg este prezent în set. Dacă toate numerele de la 1 la N sunt prezente în șirul dat și nu există duplicări, atunci considerăm că șirul este o permutare validă și returnăm 1. În caz contrar, returnăm 0 pentru a indica că șirul nu este o permutare validă.

Această abordare are o complexitate a timpului de O(N), unde N reprezintă lungimea șirului dat A, deoarece trebuie să parcurgem șirul o singură dată și să verificăm fiecare element în set.

Personal am ales să rezolv problema prin includerea duplicatelor și în șirul original și în șirul de comparare, pentru a o face puțin mai complicată.

În exemplul meu, sir2 este o permutare (aceleași elemente ca și valoare și număr de apariții) a șirului 1. Șir 3 nu este o permutare pentru că lipsește valoarea 2, iar șir 3 nu are același număr de elemente ca Sir1.

Pentru a rezolva problema de permutări pentru două șiruri date folosind o singură funcție atunci putem folosi:

=LET(so; SORT(--TEXTSPLIT(A2;;","));
     sc; SORT(--TEXTSPLIT(A5;;","));
     IFS(SUM(--IFNA(so=sc;0))<>ROWS(so);0;SUM(--(so=sc))=ROWS(so);1))

în care so este șirul original iar sc este șirul de comparare. Ca funcție de verificare am folosit funcția IFS() pentru a determina în primă fază daca nummărul de linii a celor două șiruri este egal, apoi a doua condiție este de a verifica dacă fiecare linie a șirurilor, sortate crescător este identic. După cum observăm din imagine, în comparația S1 vs S3 vedem că valoarea 2 este lispă în Sir 3 ceea ce rezultă că S3 nu este o permutare de S1.

În practică PermCheck poate fi folosit pentru a verifica dacă un utilizator a ales dintr-o listă de valori toate opțiunile disponibile indiferent de ordinea lor. Rezolvarea mea corespunde și șirurilor cu valori unice.

Problema MaxCounters

MaxCounters este foarte asemănătoare cu FrogRiverOne doar că de data aceasta ni se solicită calcularea numărului maxim de apariții a unui element într-un total într-un anumit număr de iterații (N).

Pentru rezolvarea pas cu pas am descompus A-ul în C2# apoi am generat două secvențe pe orizontală și verticală, după care compar coloanele din rezultatele intermediare după care adaug valoarea 1 la cea anterioară.

Problema solicită determinarea maximului de apariții ale unui număr ceea ce în cazul nostru este de 4.

Funcția adaptată după același algormitm ca la FrogRiverOne este:

=LET(Xs; SEQUENCE(;B1);
    sir; TRANSPOSE(C2#);
    tabi; MAKEARRAY(ROWS(sir);$B$1;LAMBDA(r;c;LET(valc; INDEX(Xs;;c);valr;        INDEX(sir;r);IF(valr=valc;1;0))));
    tabfin; LET(set; tabi;
                m; COLUMNS(set);
                seq; SEQUENCE(m;1);
                CUMULATE; LAMBDA(x; SCAN(0; x; LAMBDA(acc;item; acc+item)));
                DROP(REDUCE(0;seq; LAMBDA(acc;idx; HSTACK(acc; CUMULATE(INDEX(set;;idx)))));;1)
);
 MAX(tabfin))

în care tabfin calculează tabelul echivalent din C5.

Problema MissingInteger

Problema MissingInteger implică găsirea celui mai mic număr întreg pozitiv care lipsește dintr-un șir dat de numere întregi. În cazul în care șirul este consecutiv, atunci va returna următoarea valoare întreagă consecutivă.

În rezolvarea pas cu pas:

în B2: am descompus șirul original și l-am sortat creascător: =SORT(UNIQUE((–TEXTSPLIT(B1;;”,”))))

În C2: am generat șirul cu valorile întregi cuprinse între minimul și maximul din B2: =SEQUENCE(MAX(B2#);;MIN(B2#))

În D2: am calculat dacă există sau nu fiecare număr din C2# în B2# =IFNA(XMATCH(C2#;B2#;0);”x”)

Rezolvarea dintr-o singură funcție este foarte asemănătoare problemei PermMissingElem explicată în articolul: Modele de algoritmi in #Excel – Time complexity (3)

Funcția finală este:

=LET(arr; SORT(--TRIM(TEXTSPLIT(B1;;",")));
	  all; SEQUENCE(MAX(arr)-MIN(arr)+1; ;MIN(arr); 1);
      vCheck; IFNA(XMATCH(all; arr;0 ); "x");
TEXTJOIN(", ";;FILTER(all;vCheck="x"; IF(MIN(all)<0;1;MAX(all)+1))))

în care:

arr este valoarea șirului A specificat, sortat ascendent, echivalentul lui B2;
all este valoarea șirului întreg, echivalentul lui C2;
vCheck este vectorul de comparație șiruri, prin returnare valoare „x” în cazul în care unul sau mai multe numere întregi sunt lipsă.
funcția TEXTJOIN() este folosită pentru a afișa toate numerele întregi lipsă dintr-un șir dat.

Această metodă este foarte utilă în practică pentru a determina de exemplu dacă avem numere lipsă dintr-un șir dat (exemplu coduri, sau zile calendaristice, etc)

Cam asta a fost pentru acest algoritm. Sper să fie util cuiva!

Nu uitați să folosiți secțiunea de comentarii dacă aveți opinii legate de subiect sau propuneri de îmbunătățire.

03/05/2024 1

Modele de algoritmi in #Excel – Time complexity (3)

În acest articol propun un set de metode de rezolvare pentru algoritmul Time complexity, descris la adresa: https://app.codility.com/programmers/lessons/3-time_complexity/

Un pic de teorie

Este o metodă de a arăta în cât timp se execută un set de operații / calcule asupra unui set de date. Odată cu creșterea valorilor de prelucrat crește în mod liniar și timpul de execuție (linear time). Contant time, îl întâlnim în cazul în care timpul de execuție nu se modifică odată cu creșterea setului de date, iar quadratic time apare în momentul în care timpul de execuție crește (pătratic – n²) odată cu creșterea setului de date.

Time Complexity este exprimat adesea în notație Big O (O()), care indică limita superioară a timpului de execuție în funcție de dimensiunea intrării.

Bog O presupune o metodă de notație a timpului de execuție în care:

O(n) este folosit pentru linear time
O(1) este folosit pentru contant time
O(n²) este folosit pentru quadratic time

În care n este numărul de elemente dintr-un șir.

Logica algoritmului este de a determina tipul timpului de execuție prin determinarea expresiei cu cea mai mare creștere dintr-o ecuație.

Exemplu: a*n+b rezultă că termenul care crește cel mai repede este a*n ceea ce înseamnă că este o funcție liniară O(n).

Dacă am avea o funcție de tipul: a*n²+b*n+v, cea mai rapidă creștere este la a*n² ceea ce înseamnă că este o funcție pătratică.

Un videoclip care explică și demonstrează foarte fain terminologia poate fi vizionat aici: https://www.youtube.com/watch?v=D6xkbGLQesk&ab_channel=CSDojo

Legat de performanțele de execuție în Excel cu referință la câteva tehnici de optimizare puteți găsi explicații detaliate aici: https://learn.microsoft.com/en-us/office/vba/excel/concepts/excel-performance/excel-improving-calculation-performance

Problema FrogJmp

În această problemă se demonstrează un algoritm de tip O(1) în care avem o singură execuție pentru că setul de date este tot timpul la fel (X, Y, D) , în seturile de test fiind diferite doar valorile acestora. În specificații ni se spune că o broască pornește de la poziția 10 presupunem pe o axă 2D. Dacă ea sare pe o distanță (D) de 30 unități, câte sărituri trebuie să facă pentru a ajunge la poziția 85. Ca idee se presupune că broasca nu sare cu virgulă :) ci sunt doar sărituri întregi.

Rezolvarea este destul de simplă în celula C5: avem formula: =ROUNDUP((C2-C1)/C3;0)

FrogJmp în Excel pentru demosntrare Time Complexity

în care funcția ROUNDUP() se folosește pentru rotunjirea în sus a rezultatului obținut. Ca să putem împărți corect distanța de parcurs (D, C3) ar trebui să scădem din destinație (Y, C2) valoarea poziției de start (X, C1).

În partea a doua am realizat un interval cu valori care să specifice unde ajunge broasca la fiecare săritură (jump). Ca să pot realiza dinamic valorile pentru săritură am folosit un scan pe coloana E, în care adun valoare acumulată anterior la valoarea distanței D.

Problema PermMissingElem

Această problemă este din categoria O(n) pentru că numărul de prelucrări depunde de numărul elementelor din șirul propus spre rezolvare.

Problema presupune un șir de numere întregi care ar fi teoretic un șir. Scopul este de a obține numărul elementelor (numerelor lipsă) din intervalul dat.

Se dă șirul {8, 3, 2, 5, 7} în celula A4.

Problema PermMissingElem din algoritmul Time Complexity

În care:

celula A7: avem descompunerea șirului cu TEXTSPLIT(), eliminarea spațiilor din șir cu TRIM() și sortare ascendentă cu SORT();
în B7: calculez valoarea minimă din șir: =MIN(A7#)
în B8: calculez valoarea maximă din șir: =MAX(A7#)
în D7: generez secvența completă de la numărul cel mai mic la cel mai mare: =SEQUENCE(C7-B7+1;;B7;1). Numărul de elemente va fi numărul maxim din șir minus numărul minim +1.
În celula E7 am calculat dacă numărul din secvența completă (D7#) este în secvența propusă. Pentru aceasta folosesc: =IFNA(XMATCH(D7#;A7#);”x”) în care XMATCH() face căutarea între cei doi vectori iari IFNA() pune valoarea X în căsuța numărului lipsă.
Rezultatul final l-am trecut în celula G7: =TEXTJOIN(„, „;;FILTER(D7#;E7#=”x”; „-„)) în care am unificat toate valorile lipsă din șir prin filtrarea secvenței complete (D7#) pentru care rezultatul căutării este egal cu valoarea „x”. Am folosit TEXTJOIN pentru a unifica rezultatele din FILTER.

Unificate toate coloanele intermediare într-o singură formulă aceasta ar fi:

=LET(arr; SORT(--TRIM(TEXTSPLIT(A4;;",")));
          all; SEQUENCE(MAX(arr)-MIN(arr)+1; ;MIN(arr); 1);
          vCheck; IFNA(XMATCH(all; arr;0 ); "x");

TEXTJOIN(", ";;FILTER(all;vCheck="x"; "-")))

Aplicabilitatea practică a acestui model poate fi destul de interesantă.

Un exemplu ar fi acela în care avem un interval de date și vrem să identificăm dacă lipsește una din ele. Alt exemplu, avem un exemplu de litere (coduri, etc) și dorim să identificăm literele care lipsesc.

Model de solutii din viata reala pentru PermMissingElem

Funcția din D3 este:

=LET(arr; SORT(A3:A22);
          all; SEQUENCE(MAX(arr)-MIN(arr)+1; ;MIN(arr); 1);
          vCheck; IFNA(XMATCH(all; arr;0 ); "x");

FILTER(all;vCheck="x"; "-"))

Funcționarea algoritmului este posibilă datorită faptului că datele în Excel sunt de fapt numere.

În celula K3 am folosit funcția:

=LET(arr; SORT(CODE(I3:I21));
          all; SEQUENCE(MAX(arr)-MIN(arr)+1; ;MIN(arr); 1);
          vCheck; IFNA(XMATCH(all; arr;0 ); "x");

TEXTJOIN(", ";;CHAR(FILTER(all;vCheck="x"; "-"))))

Funcția nu poate lucra la propriu cu litere, de aceea a trebuit să folosesc funcția CODE() în variabila arr pentru a le transforma în coduri ascii. Apoi la final am transformat din coduri ascii în caractere cu funcția CHAR().

Problema TapeEquilibrium

Problema TapeEquilibrium este următoarea: se dă un vector de numere întregi. Vectorul trebuie să împărțit în două sub-șiruri, calculând suma fiecărui sub-șir și găsind diferența absolută dintre sumele lor. Scopul este de a minimiza această diferență absolută.

Algoritmul care rezolvă această problemă are o complexitate de timp O(n), unde n este lungimea vectorului de intrare. Acesta parcurge vectorul o singură dată pentru a calcula suma tuturor elementelor și, apoi, utilizează această sumă pentru a găsi diferența minimă dintre sumele sub-șirurilor.

Într-o abordare simplă problema este foarte ușor de rezolvat:

Se dă șirul {3, 1, 2, 4, 3}. Aflați cea mai mică valoare sau mai bine spus valoarea de echilibru pe șirul de valori.

Soluția simplă la problema: TapeEquilibrium

Pentru rezolvarea simplistă la B2 nu am introdus nici o valoare, apoi am compus suma celor de deasupra până în poziția anterioară minus suma celor rămase. Funcția ABS() transformă numerele negative în pozitive.

Doar că unificarea într-o singură formulă mi-a dat ceva bătăi de cap. Unul din principiile de bază în lucrul, nu numai în Excel, este KISS – Keep It Simple and Stupid.

În prima versiune:

Abordare complexă pe coloane diferite TapeEquilibrium

Am creat un tabel intermediar cu numerele și ordinea de la 0.

Apoi am aplicat o ditamai funcția pentru a face diferența. Scopul era de a le unifica într-una singură.

Formula din F2 pentru obținerea tabelului:

=LET(arr; --TRIM(TEXTSPLIT(C2;;", "));
          poz; SEQUENCE(ROWS(arr);;0);
          tabi; HSTACK(arr; poz);
   tabi)

în care arr este lista de numere, poziția este o secvență începând de la 0 iar tabi este variabila pentru a le unifica pe cele două. Scopul era de a traversa tabelul linie cu linie și extragerea valorilor de sus și jos pe baza poziției.

Formula din H2 este cam alambicată:

=LET(arr; F2#;
cc; ROWS(arr);
pc; TAKE(arr;;1);
dc; TAKE(arr;;-1);
BYROW(arr;
LAMBDA(rr;
LET(pv; TAKE(rr;;1);
dv; TAKE(rr;;-1);
pp; TAKE(pc;dv);
dp; TAKE(pc;-(cc-dv));
sum; ABS(SUM(pp)-SUM(dp)); rez; IFERROR(sum;""); rez))))

în care:

arr – preia tabelul rezultat din funcția anterioatră;
cc – determină numărul de rânduri al șirului;
pc – extrage prima coloană din tabelul arr;
dc – extrage a doua coloană din tabelul arr;
BYROW() parsează tabelul linie cu linie;
LAMBDA() face referire la linia curentă prin variabila rr
În LET() definesc un alt set de variabile pentru valorile de pe linie: pv (prima valoare), dv, valoarea de pe coloana 2, pp este prima parte din prima coloana din pozitia curenta (dv)-1, dp este a doua parte a primei coloane, apoi determin suma primei părți (pp) cu a doua parte (dp).

Iese dar la unificarea celor două funcții obțin niște rezultate dubioase, în loc de 7, 5, 1, 7 obțin 2, 1, 1, 0 ceea ce înseamnă că undeva fac o greșeală. Cu cât este mai complexă abordarea cu atât este mai greu de controlat rezultatul intermediar.

Așa că am ales o abordare diferită și am ales să folosesc funcția INDEX în mod dinamic în detrimentul funcției TAKE din varianta anterioară:

Minusul acestei rezolvări este că nu pot folosi o variabilă de descompunere direct în LET() ci trebuie să refer un set de celule deja transformate în valori.

Primul pas a fost descompunerea șirului în celula A7 cu: =–TRIM(TEXTSPLIT(A2;;”,”))

Funcția din D2 care îmi calculează valoarea minimă este:

=LET(arr; A7#; poz; SEQUENCE(ROWS(arr));
pp; MAP(poz; LAMBDA(v; SUM(INDEX(arr;1):INDEX(arr;v))));
dp; MAP(poz; LAMBDA(v; IFERROR(SUM(INDEX(arr;v+1):INDEX(arr;ROWS(arr)));"")));
diff; IFERROR(ABS(pp-dp);""); MIN(diff))

în care:

arr – preia vectorul rezultat din split;
poz – determină șirul de valori de lungimea vectorului, începând cu 1 de această dată (implicit);
pp – preia valorile din prima parte a lui arr prin declararea variabilei v în LAMBDA în așa fel încât să construiesc un idex dinamic de la poziția 1 la poziția v curent în care v este poziția curentă din pozițe;
dp – a doua parte preia în același stil cu INDEX() valorile de la poziția curentă a lui v de pe secvență până la finalul lui arr ROWS(arr).
diff – calculează diferența absolută dintre cele două numere rezultate din însumare.

Ca să pot face depanare în această funcție mi-am făcut un tabel de rezultate intermediare, utilizând o combinație de HSTACK cu VSTACK.

vCheck; HSTACK(VSTACK("Sirul"; arr);VSTACK("Pozitia"; poz);VSTACK("Partea de sus"; pp);VSTACK("Partea de jos"; dp); VSTACK("Diferenta"; diff));

Un exemplu de problemă din viața reală unde algoritmul TapeEquilibrium ar putea fi util este în domeniul financiar, în special în gestionarea portofoliilor de investiții.

Să presupunem că aveți un portofoliu de investiții format din acțiuni și alte active financiare. Diferitele active pot fluctua în valoare în timp, iar obiectivul dumneavoastră este să gestionați aceste fluctuații și să minimizați riscul. O abordare comună este să împărțiți portofoliul în două părți și să încercați să mențineți echilibrul între ele.

Algoritmul TapeEquilibrium ar putea fi utilizat pentru a determina cea mai bună modalitate de a distribui activele între cele două părți ale portofoliului într-un mod echilibrat, astfel încât să se minimizeze riscul general. Calculând diferența absolută între sumele valorilor active din cele două părți, puteți ajusta distribuția pentru a obține o diferență minimă și, implicit, un portofoliu mai stabil și mai echilibrat din punct de vedere financiar.

Cam asta este pentru astăzi. Dacă ceva este greșit vă rog să nu ezitați să-mi scrieți în comentarii.

Sper să fie util cuiva!

25/04/2024 1

Modele de algoritmi in #Excel – Vectori (2.2)

Pentru acest articol am continuat partea de vectori din articolul trecut și propun o rezolvare a problemei
OddOccurrencesInArray.

În această problemă ni se propune un vector cu un set de numere naturale, unele dintre ele se repetă. Scopul este de a identifica câte din numerele respectivă se repetă de un număr impar de ori.

Nu mai detaliez mica parte de teorie din articolul precedent ci detaliez direct problema și explic soluțiile.

Se dă șirul {9, 3, 9, 3, 9, 7, 9, 1}. În acest șir sunt unice valorile {1, 3, 7, 9}. Dintre acestea, 1 și 7 apar de un număr impar de ori (o singură dată).

OddOccurrencesInArray propunere rezolvare în Excel.

Rezolvarea pas cu pas

Șirul de numere este trecut în celula A2.

Pentru a descompune șirul în A5 folosesc funcția =–TEXTSPLIT(A2;;”, „) , caracterele – vor transforma rezolvatul text al funcției de split într-un număr.

Pentru a determina valorile unice în C5 folosesc funcția: =SORT(UNIQUE(A5#)) prin care determin valorile unice de pe array A5#, cu funcția UNIQUE() și apoi le sortez în ordine crescătoare cu funcția SORT(). Tendința în Excel este de a transforma cât mai mult operațiile în funcții. Avantajul acestei abordări este că operațiunile nu sunt replicabile, sau pot fi oarecum replicate prin înregistrare și editare de macro. Funcțiile în schimb pot fi replicate și copiate.

Tehnica de apelare cu # este utilă când nu știm câte numere sunt în șir, ceea ce face dinamic rezultatul dar și apelarea sa.

Ca să determin câte valori sunt de fiecare număr folosesc în D5 un simplu COUNTIF() pentru numărarea condiționată a valorilor de pe array A5# cu condiția ca ele să fie egale cu cele din unicele de pe array C5#.

Ca să pot compara dacă valoarea rezultată pe coloana D este un număr impar folosesc funcția ISODD(). Ca să preiau valoarea impară de pe coloana din dreapta folosesc funcția TAKE() cu parametrul -1. Ca să afișez în IF() valoarea de pe coloana din stânga folosesc un TAKE cu valoarea 1. Pentru a scana tot tabelul rezultat din array C5#:D5# linie cu linie folosim funcția BYROW() care are nevoie de un tabel ca input și o funcție LAMBDA() cu parametrul de input r (echivalentul liniei) pentru interpretare.

Pentru a afișa rezultatul final al prelucrării folosesc funcția TEXTJOIN() cu delimitator „, „.

Rezolvarea dintr-o singură funcție

Rezolvarea pas cu pas a fost aproape o nimica toată, cheia fiind BYROW()-ul descris anterior.

Ca să rezolvi problema într-o singură funcție, ai aproape întotdeauna pentru probleme puțin mai complexe de funcția LET() în care poți compune gradual variabilele pe care pot fiu folosite în alte funcții din același LET(). LET()-urile se pot combina între ele cu alte funcții. Doar că una din funcții nu funcționează corect în context de LET(). Minumata funcție COUNTIF() returnează eroare de fiecare dată când încerci să o incluzi în LET().

Într-o abordare conform scenariului anterior, funcția intermediară de determinare a fiecărei apariții a numărului ar fi trebuit să arate ca în imagine:

Încercare de rezolvare OddOccurrencesInArray prin utilizare COUNTIF() în LET()

în care funcția MAP() ar trebui să parcurgă element cu element din valorile unice, iar LAMBDA() ar trebui să execute operațiunea de numărare condiționată a vectorului rezultat arr, pentru fiecare valore. Doar că nici COUNTIF() nici COUNTIFS() nu returnează valori corecte în acest context. Am încercat să realizez o funcție personalizată ca să includă COUNTIF()-ul și MAP() nu funcționează.

În acest context a trebuit să schimb funcția și în loc de un COUNTIF() să fac un COUNT() de un FILTER().

Funcția finală:

=LET( arr;--TEXTSPLIT(A2;;", ");
unice; SORT(UNIQUE(arr));
cate; MAP(unice;
LAMBDA(v; COUNT(FILTER(arr; arr=v))));
interm; HSTACK(unice;cate);
TEXTJOIN(", ";TRUE;
BYROW(interm;
LAMBDA(r;IF(ISODD(TAKE(r;;-1));TAKE(r;;1);""))))
)

în care aplic tehnicile descrise anterior pentru a obține un șir cu valorile care apar într-un număr impar de ori într-un șir de numere naturale.

Descrierea variabilelor:

arr – preia șirul și-l descompune apoi îl tranformă în număr;
unice – sortează valorile unice de pe arr;
cate – pentru fiecare valoare (v) din unice (MAP), aplică o funcție LAMBDA pentru a număra rezultatul fintrării arr după v curentă. Unice și Cate sunt variabile de o singură coloană care au același număr de rânduri.
interm – este variabila prin care realizez o matrice din cele două variabile;
matricea interm este parcursă de BYROW() prin care aplic o funcție LAMBDA() pentru fiecare linie (r) în așa fel încât să determin dacă valoarea de pe coloana din dreapta (TAKE cu -1) este număr impar (funcția ISODD).

Update 24.04.2024

În cazul în care vrem totuși să optimizăm execuția în loc să folosim funcția COUNT() de FILTER() ar fi mai util să folosim SUMPRODUCT() un fel de substitut pentru COUNTIF() și care funcționează atât în LET cât și în MAP().

Pentru a determina numărul de apariții a ficărui număr atunci putem folosi funcția:

=LET( arr;--TEXTSPLIT(A2;;", ");
unice; SORT(UNIQUE(arr));
cate; MAP(unice;
LAMBDA(v; SUMPRODUCT(--(arr=v)))); cate)

Cam asta este. Nu sunt sigur că este cea mai optimă variantă. Dacă aveți alte modele de rezolvare inclusiv în alte limbaje (Phyton de exemplu, sau VBA) sau vă rog să le partajați în comentarii dacă doriți.

Sper să fie util cuiva.

23/04/2024 1